1269. 停在原地的方案数

ITCharge大约 4 分钟

---

1269. 停在原地的方案数

标签：动态规划
难度：困难

题目链接

1269. 停在原地的方案数 - 力扣

题目大意

描述：有一个长度为 $arrLen$ 的数组，开始时指针位于下标 $0$ 处。每一步操作中，你可以将指针向左或向右移动 $1$ 步，或者停在原地不动。

要求：在恰好执行 $steps$ 次操作后，指针仍然指向下标 $0$ 的方案数。答案可能很大，返回对 $10^9 + 7$ 取模的结果。

说明：

$1 \le steps \le 500$ 。
$1 \le arrLen \le 10^{6}$ 。

示例：

示例 1：

输入：steps = 3, arrLen = 2
输出：4
解释：3 步后停在原地的方案有 4 种：原地→原地→原地、原地→右→左、右→原地→左、右→左→原地。

示例 2：

输入：steps = 2, arrLen = 4
输出：2
解释：2 步后停在原地的方案有 2 种：原地→原地、右→左。

解题思路

思路 1：动态规划

1. 阶段划分

按操作步数划分阶段。每一步后，指针的位置可能改变，也可能不变。我们关心的是第 $steps$ 步后指针回到位置 $0$ 的方案数。

2. 定义状态

定义 $dp[i][j]$ 表示执行 $i$ 步操作后，指针位于位置 $j$ 的方案数。

3. 状态转移方程

第 $i$ 步的操作决定了第 $i$ 步结束时的位置。从第 $i-1$ 步的位置 $j$ 出发，第 $i$ 步有三种选择：

不动：新位置仍是 $j$ 。
向右：新位置为 $j+1$ 。
向左：新位置为 $j-1$ 。

反过来，要到达第 $i$ 步的位置 $j$ ，前一步的位置可以是 $j$ 、 $j-1$ 或 $j+1$ ：

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

4. 边界条件和优化

$dp[0][0] = 1$ ，其余 $dp[0][j] = 0$ 。
指针不能越界： $0 \le j < arrLen$ 。
关键优化： $steps \le 500$ ，所以指针不可能走到超过 $steps$ 的位置（一步最多移动一格， $steps$ 步最多 $steps$ 格远）。因此实际需要考虑的位置范围是 $0$ 到 $\min(arrLen-1, steps)$ 。

5. 最终结果

$dp[steps][0]$ 。

6. 空间优化

$dp[i]$ 只依赖于 $dp[i-1]$ ，可以用滚动数组（两个一维数组）优化空间。

7. 结合示例走一遍

$steps = 3, arrLen = 2$

实际最大位置： $\min(1, 3) = 1$ ，所以只有位置 $0$ 和 $1$ 。

初始化： $dp[0][0] = 1$

i=1: dp[1][0] = dp[0][0] + dp[0][1] = 1 + 0 = 1  (不动或从1左移,但1不可达)
     dp[1][1] = dp[0][1] + dp[0][0] = 0 + 1 = 1  (不动或从0右移)
     等等，正确答案中 steps=3,arrLen=2 时结果是4。让我仔细推。

重新递推：
     dp[0][0]=1
i=1: dp[1][0] = dp[0][0] + dp[0][1] = 1+0 = 1  (原地不动)
     dp[1][1] = dp[0][1] + dp[0][0] = 0+1 = 1  (向右)
     → [1, 1]
i=2: dp[2][0] = dp[1][0] + dp[1][1] = 1+1 = 2  (原地/从1左移)
     dp[2][1] = dp[1][1] + dp[1][0] = 1+1 = 2  (原地/从0右移)
     → [2, 2]
i=3: dp[3][0] = dp[2][0] + dp[2][1] = 2+2 = 4  (原地/从1左移)
     dp[3][1] = dp[2][1] + dp[2][0] = 2+2 = 4
     → [4, 4]

结果为 $4$ 。

思路 1：代码

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        # 实际需要计算的最大位置
        max_pos = min(arrLen - 1, steps)

        # dp[j] 表示当前步数下位于位置 j 的方案数
        dp = [0] * (max_pos + 1)
        dp[0] = 1

        for i in range(1, steps + 1):
            # 每步更新，需要前一行的数据，用滚动数组
            nxt = [0] * (max_pos + 1)
            for j in range(max_pos + 1):
                # 不动
                nxt[j] = dp[j]
                # 从左边来
                if j > 0:
                    nxt[j] = (nxt[j] + dp[j - 1]) % mod
                # 从右边来
                if j < max_pos:
                    nxt[j] = (nxt[j] + dp[j + 1]) % mod
            dp = nxt

        return dp[0]

思路 1：复杂度分析

时间复杂度： $O(steps \times \min(steps, arrLen))$ ，外层循环 $steps$ 次，内层循环 $\min(steps, arrLen)$ 次。 $steps \le 500$ ，计算量最多 $500 \times 500 = 25$ 万，轻松通过。
空间复杂度： $O(\min(steps, arrLen))$ ，滚动数组优化后的空间。