LeetCode 5274. Number of Ways to Stay in the Same Place After Some Steps - Java - DP

题目链接：5274. 停在原地的方案数

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo $10^9 + 7$109+7.

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Constraints:

• 1 <= steps <= 500
• 1 <= arrLen <= 10^6

题解

要想在第 n 步到达 0 点，那么第 n-1 步必须在 0 点或者 1 点，
要想第 n-1 步在 0 点，那么第 n-2 步必须在 0 点或者 1 点。
要想第 n-1 步在 1 点，那么第 n-2 步必须在 0 点，1 点，2 点。
…
…

由此看出这是动态规划的问题。

定义 int 型二维数组 dp[501][252]，dp[i][j] 表示第 i 步到达 j 点的方案数。

因为 steps 最大为 500，下标从 0 开始，所以大小为 501，
因为 500 步之内想要回到 0 点，向右走最多 250 步，通过上面的步骤中第三行所示，需要向右多出一位，用来计算后面的值，所以要加 1，又因为下标从 0 开始，所以加 2。故大小为 252。

公式如下：$dp[i][j]=\begin{cases}1&\text{}i=j=0\\dp[i-1][j]+dp[i-1][j+1]&\text{}i>0且j=0\\dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]&\text{}i>0且j>0\end{cases}$dp[i][j]=⎩⎪⎨⎪⎧​1dp[i−1][j]+dp[i−1][j+1]dp[i−1][j−1]+dp[i−1][j]+dp[i−1][j+1]​i=j=0i>0且j=0i>0且j>0​

Example 1 计算步骤如下：

时间复杂度：$O(m*min(\frac{m}{2}, n))$O(m∗min(2m​,n))，m 表示 steps，n 表示 arrLen。
空间复杂度：$O(1)$O(1)，因为大小固定，与 steps，arrLen 无关。

Java代码（第6次提交）

我发现最里面的判断执行的次数太多，而且好像可以提出来。

// 执行时间：7ms
class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        int[][] dp = new int[501][252];
        dp[0][0] = 1;
        int right = 0;
        for (int i = 1; i <= steps; ++i) {
            right = Math.min(Math.min(i, steps - i), arrLen - 1);
            // 第0列只能加正上方和右上方，左上方出界了
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            for (int j = 1; j <= right; ++j) {// 从1开始
                // 左上方和正上方
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;// 右上方
            }
        }
        return dp[steps][0];
    }
}

Java代码（第5次提交）

// 执行时间：9ms
class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        int[][] dp = new int[501][252];
        dp[0][0] = 1;
        int right = 0;
        for (int i = 1; i <= steps; ++i) {
            // 将这里直接用一行表示
            right = Math.min(Math.min(i, steps - i), arrLen - 1);
            for (int j = 0; j <= right; ++j) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;// 两行合为一行
                if (j > 0) {
                    // 两行合为一行
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
                }
                // 两行合为一行
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
            }
        }
        return dp[steps][0];
    }
}

Java代码（第4次提交）

// 执行时间：11ms
class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        // 第3次太啰嗦，直接固定为最大范围更节省时间，快6ms，
        // 这说明计算比申请内存（这里申请的空间也不大）更耗时
        int[][] dp = new int[501][252];
        dp[0][0] = 1;
        int right = 0;
        for (int i = 1; i <= steps; ++i) {
            right = Math.min(i, steps - i);
            right = Math.min(right, arrLen - 1);
            for (int j = 0; j <= right; ++j) {
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= mod;
                if (j > 0) {
                    dp[i][j] += dp[i - 1][j - 1];
                    dp[i][j] %= mod;
                }
                dp[i][j] += dp[i - 1][j + 1];
                dp[i][j] %= mod;
            }
        }
        return dp[steps][0];
    }
}

Java代码（第3次提交）

其实步数最多为 500 步，所以最多向右走 250 步，如果继续向右走 1 步，那么就无法回到原点。所以 steps >> 1，又因为需要计算 dp[i][steps >> 1]，所以右边还需要 1 位，因此要加 1，又因为这是下标（从 0 开始），所以最终是 (steps >> 1) + 2，但是又不能超过限定的范围。所以就变成了下面写的那样。

// 执行用时：17ms
class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        // 如此啰嗦
        int[][] dp = new int[steps + 1][Math.min((steps >> 1) + 2, arrLen + 1)];
        dp[0][0] = 1;
        int right = 0;
        for (int i = 1; i <= steps; ++i) {
            right = Math.min(i, steps - i);
            right = Math.min(right, arrLen - 1);
            for (int j = 0; j <= right; ++j) {
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= mod;
                if (j > 0) {
                    dp[i][j] += dp[i - 1][j - 1];
                    dp[i][j] %= mod;
                }
                dp[i][j] += dp[i - 1][j + 1];
                dp[i][j] %= mod;
            }
        }
        return dp[steps][0];
    }
}

Java代码（第2次提交）

第1次提交的时候忘记将输出删掉，，，结果超时了。
第2次提交，内存超出限制。原因是 arrLen 达到 $10^6$106，导致数组过大。

class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        int[][] dp = new int[steps + 1][arrLen + 1];// 这里超出内存限制
        dp[0][0] = 1;
        int right = 0;
        for (int i = 1; i <= steps; ++i) {
            right = Math.min(i, steps - i);
            right = Math.min(right, arrLen - 1);
            for (int j = 0; j <= right; ++j) {
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= mod;
                if (j > 0) {
                    dp[i][j] += dp[i - 1][j - 1];
                    dp[i][j] %= mod;
                }
                dp[i][j] += dp[i - 1][j + 1];
                dp[i][j] %= mod;
            }
        }
        return dp[steps][0];
    }
    // private void print(int[][] dp) {
    //     for (int i = 0; i < dp.length; ++i) {
    //         for (int j = 0; j < dp[i].length; ++j) {
    //             System.out.print(dp[i][j] + " ");
    //         }
    //         System.out.println();
    //     }
    //     System.out.println();
    // }
}

原文链接：https://www.cnblogs.com/wowpH/p/11924796.html

- End - wowpH - cnblogs -