Leetcode 1269: Number of Ways to Stay in the Same Place After Some Steps

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/description/

Notes:

This question can be solved by dp, or dynamic programming.

Let us use dp[i][j] represents the number of ways reaching the position i after j steps, then

dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + dp[i+1][j-1]

So we can use a rolling array to reduce the dimension from 2D to 1D.

dp[i] = dp[i-1] + dp[i] + dp[i+1], or

dp[i] += dp[i-1] + dp[i+1]

Since we need to use the previous value from both sides (left and right of the i position), we cannot directly scan the array from one side to the other.

This can be solved by two ways:

one is that we use two arrays: pre and cur. In this way, we can use pre and cur alternatively: pre record the results from the previous steps; and cur is the current results.

the other is use a temporary variable to record the dp[i-1] from the previous step. Then we can update  the array from the left to right.

Now let us look at the time complexity: it should be O(M*N), where M is the length of the steps, and N is the length of the array.

But N can be very large in this question (1 million), and M is small (<= 100). Do we really need to have an array of 10^6 for a step only of 100?

The boundary case is that: we can only reach the position of 99 if we start from the position of 0, with 100 steps. (It is easy to see this. If not, please take a deep breath and then rethink, :))

Thus, we just need to have an array with a size of <= 100.

Please see the code below:

class Solution {
public:
    int numWays(int steps, int arrLen) {
        int len = min(steps, arrLen);
        vector<long> dp(len, 0);
        dp[0] = 1;
        int mod = 1e9+7;
        for(int i=0; i<steps; ++i) {
            long p = 0, c = 0;
            for(int j=0; j<len; ++j) {
                c = dp[j];
                dp[j] += p + (j+1<len ? dp[j+1] : 0);
                dp[j] %= mod;
                p = c;
            }
        }
        return dp[0];
    }
};