1269-停在原地的方案数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。

每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。

给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。

由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。

示例 1：

**输入：** steps = 3, arrLen = 2
**输出：** 4
**解释：** 3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动

示例 2：

**输入：** steps = 2, arrLen = 4
**输出：** 2
**解释：** 2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动

示例 3：

**输入：** steps = 4, arrLen = 2
**输出：** 8

提示：

  • 1 <= steps <= 500
  • 1 <= arrLen <= 106

方法一：动态规划

对于计算方案数的题目，常用的方法是动态规划。对于这道题，需要计算在 steps 步操作之后，指针位于下标 0 的方案数。

用 dp}[i][j] 表示在 i 步操作之后，指针位于下标 j 的方案数。其中，i 的取值范围是 0 \le i \le \textit{steps，j 的取值范围是 0 \le j \le \textit{arrLen}-1。

由于一共执行 steps 步操作，因此指针所在下标一定不会超过 steps，可以将 j 的取值范围进一步缩小到 0 \le j \le \min(\textit{arrLen}-1, \textit{steps})。

当没有进行任何操作时，指针一定位于下标 0，因此动态规划的边界条件是 dp}[0][0]=1，当 1 \le j \le \min(\textit{arrLen}-1, \textit{steps}) 时有 dp}[0][j]=0。

每一步操作中，指针可以向左或向右移动 1 步，或者停在原地。因此，当 1 \le i \le \textit{steps 时，状态 dp}[i][j] 可以从 dp}[i-1][j-1]、dp}[i-1][j] 和 dp}[i-1][j+1] 这三个状态转移得到。状态转移方程如下：

\textit{dp}[i][j] = \textit{dp}[i-1][j-1]+\textit{dp}[i-1][j]+\textit{dp}[i-1][j+1]

由于指针不能移动到数组范围外，因此对于上述状态转移方程，需要注意下标边界情况。当 j=0 时，dp}[i-1][j-1]=0；当 j=\min(\textit{arrLen}-1, \textit{steps}) 时，dp}[i-1][j+1]=0。具体实现时，需要对下标进行判断，避免下标越界。

计算过程中需要对每个状态的值计算模 10^9+7 后的结果。最终得到 dp}[\textit{steps}][0] 的值即为答案。

[sol11-Java]
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) {
        final int MODULO = 1000000007;
        int maxColumn = Math.min(arrLen - 1, steps);
        int[][] dp = new int[steps + 1][maxColumn + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= maxColumn; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - 1 >= 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO;
                }
            }
        }
        return dp[steps][0];
    }
}
[sol11-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int NumWays(int steps, int arrLen) {
        const int MODULO = 1000000007;
        int maxColumn = Math.Min(arrLen - 1, steps);
        int[,] dp = new int[steps + 1, maxColumn + 1];
        dp[0, 0] = 1;
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= maxColumn; j++) {
                dp[i, j] = dp[i - 1, j];
                if (j - 1 >= 0) {
                    dp[i, j] = (dp[i, j] + dp[i - 1, j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dp[i, j] = (dp[i, j] + dp[i - 1, j + 1]) % MODULO;
                }
            }
        }
        return dp[steps, 0];
    }
}
[sol11-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func numWays(steps, arrLen int) int {
    const mod = 1e9 + 7
    maxColumn := min(arrLen-1, steps)
    dp := make([][]int, steps+1)
    for i := range dp {
        dp[i] = make([]int, maxColumn+1)
    }
    dp[0][0] = 1
    for i := 1; i <= steps; i++ {
        for j := 0; j <= maxColumn; 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 <= maxColumn {
                dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod
            }
        }
    }
    return dp[steps][0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
[sol11-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    const int MODULO = 1000000007;

    int numWays(int steps, int arrLen) {
        int maxColumn = min(arrLen - 1, steps);
        vector<vector<int>> dp(steps + 1, vector<int>(maxColumn + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= maxColumn; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - 1 >= 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO;
                }
            }
        }
        return dp[steps][0];
    }
};
[sol11-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MODULO = 1000000007;

int numWays(int steps, int arrLen) {
    int maxColumn = fmin(arrLen - 1, steps);
    int dp[steps + 1][maxColumn + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= steps; i++) {
        for (int j = 0; j <= maxColumn; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - 1 >= 0) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO;
            }
            if (j + 1 <= maxColumn) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO;
            }
        }
    }
    return dp[steps][0];
}
[sol11-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        maxColumn = min(arrLen - 1, steps)

        dp = [[0] * (maxColumn + 1) for _ in range(steps + 1)]
        dp[0][0] = 1

        for i in range(1, steps + 1):
            for j in range(0, maxColumn + 1):
                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 <= maxColumn:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod
        
        return dp[steps][0]
[sol11-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var numWays = function(steps, arrLen) {
    const MODULO = 1000000007;
    let maxColumn = Math.min(arrLen - 1, steps);
    const dp = new Array(steps + 1).fill(0).map(() => new Array(maxColumn + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= steps; i++) {
        for (let j = 0; j <= maxColumn; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - 1 >= 0) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO;
            }
            if (j + 1 <= maxColumn) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO;
            }
        }
    }
    return dp[steps][0];
};

上述实现的时间复杂度是 O(\textit{steps} \times \min(\textit{arrLen}, \textit{steps}))，空间复杂度是 O(\textit{steps} \times \min(\textit{arrLen}, \textit{steps}))。

注意到 dp 的每一行只和上一行有关，因此可以将空间复杂度降低到 O(\min(\textit{arrLen}, \textit{steps}))。

[sol12-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numWays(int steps, int arrLen) {
        final int MODULO = 1000000007;
        int maxColumn = Math.min(arrLen - 1, steps);
        int[] dp = new int[maxColumn + 1];
        dp[0] = 1;
        for (int i = 1; i <= steps; i++) {
            int[] dpNext = new int[maxColumn + 1];
            for (int j = 0; j <= maxColumn; j++) {
                dpNext[j] = dp[j];
                if (j - 1 >= 0) {
                    dpNext[j] = (dpNext[j] + dp[j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dpNext[j] = (dpNext[j] + dp[j + 1]) % MODULO;
                }
            }
            dp = dpNext;
        }
        return dp[0];
    }
}
[sol12-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int NumWays(int steps, int arrLen) {
        const int MODULO = 1000000007;
        int maxColumn = Math.Min(arrLen - 1, steps);
        int[] dp = new int[maxColumn + 1];
        dp[0] = 1;
        for (int i = 1; i <= steps; i++) {
            int[] dpNext = new int[maxColumn + 1];
            for (int j = 0; j <= maxColumn; j++) {
                dpNext[j] = dp[j];
                if (j - 1 >= 0) {
                    dpNext[j] = (dpNext[j] + dp[j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dpNext[j] = (dpNext[j] + dp[j + 1]) % MODULO;
                }
            }
            dp = dpNext;
        }
        return dp[0];
    }
}
[sol12-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func numWays(steps, arrLen int) int {
    const mod = 1e9 + 7
    maxColumn := min(arrLen-1, steps)
    dp := make([]int, maxColumn+1)
    dp[0] = 1
    for i := 1; i <= steps; i++ {
        dpNext := make([]int, maxColumn+1)
        for j := 0; j <= maxColumn; j++ {
            dpNext[j] = dp[j]
            if j-1 >= 0 {
                dpNext[j] = (dpNext[j] + dp[j-1]) % mod
            }
            if j+1 <= maxColumn {
                dpNext[j] = (dpNext[j] + dp[j+1]) % mod
            }
        }
        dp = dpNext
    }
    return dp[0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
[sol12-C++]
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:
    const int MODULO = 1000000007;

    int numWays(int steps, int arrLen) {
        int maxColumn = min(arrLen - 1, steps);
        vector<int> dp(maxColumn + 1);
        dp[0] = 1;
        for (int i = 1; i <= steps; i++) {
            vector<int> dpNext(maxColumn + 1);
            for (int j = 0; j <= maxColumn; j++) {
                dpNext[j] = dp[j];
                if (j - 1 >= 0) {
                    dpNext[j] = (dpNext[j] + dp[j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dpNext[j] = (dpNext[j] + dp[j + 1]) % MODULO;
                }
            }
            dp = dpNext;
        }
        return dp[0];
    }
};
[sol12-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MODULO = 1000000007;

int numWays(int steps, int arrLen) {
    int maxColumn = fmin(arrLen - 1, steps);
    int dp[maxColumn + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 1; i <= steps; i++) {
        int dpNext[maxColumn + 1];
        for (int j = 0; j <= maxColumn; j++) {
            dpNext[j] = dp[j];
            if (j - 1 >= 0) {
                dpNext[j] = (dpNext[j] + dp[j - 1]) % MODULO;
            }
            if (j + 1 <= maxColumn) {
                dpNext[j] = (dpNext[j] + dp[j + 1]) % MODULO;
            }
        }
        memcpy(dp, dpNext, sizeof(dp));
    }
    return dp[0];
}
[sol12-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        maxColumn = min(arrLen - 1, steps)

        dp = [0] * (maxColumn + 1)
        dp[0] = 1

        for i in range(1, steps + 1):
            dpNext = [0] * (maxColumn + 1)
            for j in range(0, maxColumn + 1):
                dpNext[j] = dp[j]
                if j - 1 >= 0:
                    dpNext[j] = (dpNext[j] + dp[j - 1]) % mod
                if j + 1 <= maxColumn:
                    dpNext[j] = (dpNext[j] + dp[j + 1]) % mod
            dp = dpNext
        
        return dp[0]
[sol12-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var numWays = function(steps, arrLen) {
    const MODULO = 1000000007;
    let maxColumn = Math.min(arrLen - 1, steps);
    let dp = new Array(maxColumn + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= steps; i++) {
        const dpNext = new Array(maxColumn + 1).fill(0);
        for (let j = 0; j <= maxColumn; j++) {
            dpNext[j] = dp[j];
            if (j - 1 >= 0) {
                dpNext[j] = (dpNext[j] + dp[j - 1]) % MODULO;
            }
            if (j + 1 <= maxColumn) {
                dpNext[j] = (dpNext[j] + dp[j + 1]) % MODULO;
            }
        }
        dp = dpNext;
    }
    return dp[0];
};

复杂度分析

  • 时间复杂度：O(\textit{steps} \times \min(\textit{arrLen}, \textit{steps}))。动态规划需要计算每个状态的值。

  • 空间复杂度：O(\min(\textit{arrLen}, \textit{steps}))。使用空间优化的做法，可以将空间复杂度降低到 O(\min(\textit{arrLen}, \textit{steps}))。

 Comments
On this page
1269-停在原地的方案数