★ FEATURED ARTICLE 链接字节跳动高频题——圆环回原点问题题解#include vector using namespace std; const int MOD 1000000007; class Solution { public: int calc(int steps) { // dp[剩余步数][当前位置] 方案数-1 表示未计算 vectorvectorint dp(steps 1, vectorint(10, -1)); return dfs(0, steps, dp); } private: int dfs(int begin, int steps, vectorvectorint dp) { if (steps 0) { return begin 0 ? 1 : 0; } if (dp[steps][begin] ! -1) { return dp[steps][begin]; } int right_node (begin 9) ? 0 : begin 1; int left_node (begin 0) ? 9 : begin - 1; long long count 0; count dfs(right_node, steps - 1, dp); count dfs(left_node, steps - 1, dp); dp[steps][begin] count % MOD; return dp[steps][begin]; } };#include iostream #include vector using namespace std; int func(int n) { int length 10; std::vectorstd::vectorint dp(n1, std::vectorint(length, 0)); dp[0][0] 1; for (int step 1; step n; step) { for (int j 0; j length; j) { dp[step][j] dp[step-1][(j-1length)%length] dp[step-1][(j1)%length]; } } return dp[n][0]; } int main() { int n 2; cout func(n) endl; }#include iostream using namespace std; class Solution { public: int backToOrigin(int n) { // 点的个数为 10 int length 10; vectorvectorint dp(n 1, vectorint(length, 0)); dp[0][0] 1; // 初始化0步到达0点的方案数为1 for (int i 1; i n; i) { for (int j 0; j length; j) { // dp[i][j] 表示从0出发走i步到j的方案数 dp[i][j] dp[i - 1][(j - 1 length) % length] dp[i - 1][(j 1) % length]; } } return dp[n][0]; // 返回走n步回到0点的方案数 } }; int func(int cur, int n, int rest, std::vectorstd::vectorint dp) { if (dp[cur][rest] ! -1) { return dp[cur][rest]; } if (rest 0) { dp[cur][rest] cur 0 ? 1 : 0; return cur 0 ? 1 : 0; } int left 0; if (cur 0) { left func(9, n, rest-1, dp); } else { left func(cur-1, n, rest-1, dp); } int right 0; if (cur 9) { right func(0, n, rest-1, dp); } else { right func(cur1, n, rest-1, dp); } dp[cur][rest] left right; return left right; } int main() { Solution sol; for (int i 1; i 100; i) { std::vectorstd::vectorint dp(10, std::vectorint(i1, -1)); if (func(0, i, i, dp) sol.backToOrigin(i)) { cout Yes i: i func(0, i, i, dp) sol.backToOrigin(i) endl; } else { cout No i: i func(0, i, i, dp) sol.backToOrigin(i) endl; } } }暴力递归里面有重复计算加一个缓存记忆搜索下一遇到一样问题直接返回解由简单状态推复杂状态
阅读完成 · 觉得有帮助？
)
