链接：

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

题解：坐标型动态规划

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];}
};