LeetCode 1269. Number of Ways to Stay in the Same Place After Some Steps

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int MOD = 1000000007;
        int maxCol = min(steps / 2 + 1, arrLen);
        vector<vector<int>> dp(steps + 1, vector<int>(maxCol));
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++i) {
            for (int j = 0; j < maxCol; ++j) {
                int &x = dp[i][j];
                x = dp[i - 1][j];
                if (j)
                    x = (x + dp[i - 1][j - 1]) % MOD;
                if (j < maxCol - 1)
                    x = (x + dp[i - 1][j + 1]) % MOD;
            }
        }
        return dp[steps][0]; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int MOD = 1000000007;
        int maxCol = min(steps / 2 + 1, arrLen);
        vector<vector<int>> dp(2, vector<int>(maxCol));
        int curr = 0, next;
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++i) {
            next = 1 - curr;
            for (int j = 0; j < maxCol; ++j) {
                int &x = dp[next][j];
                x = dp[curr][j];
                if (j)
                    x = (x + dp[curr][j - 1]) % MOD;
                if (j < maxCol - 1)
                    x = (x + dp[curr][j + 1]) % MOD;
            }
            curr = next;
        }
        return dp[curr][0]; 
    }
};