企业官网建设流程全解析

链接：

​​​​​​1269. 停在原地的方案数

题解：坐标型动态规划

坐标就是当前位置

1.初始化是当前在开始位置就是dp[0][0]存在1种情况

2.求解一下数组长度，最多能走step/2步，素以数组下标是0，1，2，... step/2所以数组长度是step/2+1，n=min(step/2+1, arrLen)

3.结果是要回到原点所以结果是dp[steps][0];

class Solution { public: int numWays(int steps, int arrLen) { if (arrLen <= 0) { return 0; } // 因为需要返回到0下标位置所以，最远也就是一半 int len = std::min(steps/2+1, arrLen); // 走了多少步，到达当前下标dp[step][j]，有多少种 std::vector<std::vector<int>> dp(steps+1, std::vector<int>(len, 0)); // 从上一步得来， std::vector<std::vector<int>> direction{{-1, 0}, {-1, -1}, {-1, 1}}; dp[0][0] = 1; int MOD = 1000000007; for (int i = 1; i <= steps; ++i) { for (int j = 0; j < len; ++j) { for (auto& direc : direction) { int prev_row = i + direc[0]; int prev_col = j + direc[1]; if (prev_row < 0 || prev_col < 0 || prev_col >= len) { continue; } dp[i][j] = (dp[i][j] + dp[prev_row][prev_col]) % MOD; } } } return dp[steps][0]; } };

class Solution { public: int numWays(int steps, int arrLen) { if (arrLen <= 1) { return 1; } int MOD = 1000000007; int len = std::min(steps/2+1, arrLen); std::vector<std::vector<int>> dp(steps+1, std::vector<int>(len, 0)); dp[0][0] = 1; for (int step = 1; step <= steps; ++step) { dp[step][0] = (dp[step-1][0] + dp[step-1][1])%MOD; dp[step][len-1] = (dp[step-1][len-1] + dp[step-1][len-2])%MOD; for (int i = 1; i < len-1; ++i) { dp[step][i] = ((dp[step-1][i-1] + dp[step-1][i])%MOD + dp[step-1][i+1])%MOD; } } return dp[steps][0]; } };