LeetCode1269(2021.5.13)

LC1269. 停在原地的方案数

class Solution {
public:
    const int mod = 1e9 + 7;

    int numWays(int steps, int arrLen) {
        int n = min(arrLen - 1, steps);
        vector<vector<int>> dp(steps + 1, vector<int>(n + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
                if (j + 1 <= n) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
            }
        }
        return dp[steps][0];
    }
};

发表评论