Hard

题目描述

你有一个指针指向数组中的索引 0，数组的大小为 arrLen。在每一步中，你可以将指针向左移动 1 个位置、向右移动 1 个位置或停留在原地（指针不应该被放在数组外的任何位置）。

给定两个整数 steps 和 arrLen，返回在恰好 steps 步之后，你的指针仍然位于索引 0 的方案数。由于答案可能太大，请返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：steps = 3, arrLen = 2
输出：4
解释：在 3 步后停留在索引 0 有 4 种不同的方法。
右，左，停留
停留，右，左
右，停留，左
停留，停留，停留

示例 2：

输入：steps = 2, arrLen = 4
输出：2
解释：在 2 步后停留在索引 0 有 2 种不同的方法。
右，左
停留，停留

示例 3：

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

约束：

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

解题思路

这是一个经典的动态规划问题。我们需要找到恰好经过 steps 步后回到位置 0 的方案数。

核心思路：

定义 dp[i][j] 表示经过 i 步后，指针位于位置 j 的方案数。目标是求 dp[steps][0]。

状态转移： 对于位置 j，我们可以从三个位置转移过来：

  • 从位置 j-1 向右移动一步
  • 从位置 j 停留不动
  • 从位置 j+1 向左移动一步

因此状态转移方程为：

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

优化关键：

  1. 由于指针最远只能走到位置 steps（来回走），所以实际有效位置范围是 min(arrLen, steps + 1)
  2. 可以使用滚动数组优化空间复杂度，因为当前状态只依赖于前一步的状态

边界条件：

  • dp[0][0] = 1（初始位置）
  • 越界位置的值为 0

时间复杂度主要取决于步数和有效位置数，与原数组长度无关，这正是题目提示中提到的重要观察。

代码实现

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int MOD = 1e9 + 7;
        int maxPos = min(arrLen, steps + 1);
        
        vector<vector<int>> dp(steps + 1, vector<int>(maxPos, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j < maxPos; j++) {
                dp[i][j] = dp[i-1][j];
                if (j > 0) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
                }
                if (j < maxPos - 1) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % MOD;
                }
            }
        }
        
        return dp[steps][0];
    }
};

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9 + 7
        maxPos = min(arrLen, steps + 1)
        
        dp = [[0] * maxPos for _ in range(steps + 1)]
        dp[0][0] = 1
        
        for i in range(1, steps + 1):
            for j in range(maxPos):
                dp[i][j] = dp[i-1][j]
                if j > 0:
                    dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD
                if j < maxPos - 1:
                    dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % MOD
        
        return dp[steps][0]

public class Solution {
    public int NumWays(int steps, int arrLen) {
        const int MOD = 1000000007;
        int maxPos = Math.Min(arrLen, steps + 1);
        
        int[,] dp = new int[steps + 1, maxPos];
        dp[0, 0] = 1;
        
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j < maxPos; j++) {
                dp[i, j] = dp[i-1, j];
                if (j > 0) {
                    dp[i, j] = (dp[i, j] + dp[i-1, j-1]) % MOD;
                }
                if (j < maxPos - 1) {
                    dp[i, j] = (dp[i, j] + dp[i-1, j+1]) % MOD;
                }
            }
        }
        
        return dp[steps, 0];
    }
}

var numWays = function(steps, arrLen) {
    const MOD = 1e9 + 7;
    const maxPos = Math.min(arrLen, steps + 1);
    
    const dp = Array(steps + 1).fill().map(() => Array(maxPos).fill(0));
    dp[0][0] = 1;
    
    for (let i = 1; i <= steps; i++) {
        for (let j = 0; j < maxPos; j++) {
            dp[i][j] = dp[i-1][j];
            if (j > 0) {
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
            }
            if (j < maxPos - 1) {
                dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % MOD;
            }
        }
    }
    
    return dp[steps][0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(steps × min(arrLen, steps))需要填充二维DP表，有效位置数为min(arrLen, steps+1)
空间复杂度O(steps × min(arrLen, steps))DP表的空间开销，可优化为O(min(arrLen, steps))

相关题目