What pattern does 'Number of Ways to Stay in the Same Place After Some Steps' use?

It uses state transition dynamic programming, tracking the number of ways to reach each index per step.

How do I optimize memory for large arrays in this problem?

Use a single array of length min(steps+1, arrLen) and update iteratively per step instead of a full 2D DP table.

Why do we need modulo 10^9 + 7 in this problem?

The number of sequences can grow extremely large, and modulo arithmetic prevents integer overflow.

Can the pointer move outside the array boundaries?

No, all moves must stay within index 0 to arrLen-1, and any out-of-bounds move is invalid.

How does GhostInterview approach the step-by-step DP solution?

It automatically generates the DP transitions for each step and enforces staying within bounds to compute the correct count.

#1269

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

停在原地的方案数

有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。由…

动态规划

题目描述

有一个长度为 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 <= 10⁶

lightbulb

解题思路

方法一：记忆化搜索

我们观察题目的数据范围，可以发现 $steps$ 最大不超过 $500$ ，这意味着我们最远只能往右走 $500$ 步。

我们可以设计一个函数 $dfs(i, j)$ ，表示当前在位置 $i$ ，并且剩余步数为 $j$ 的方案数。那么答案就是 $dfs(0, steps)$ 。

函数 $dfs(i, j)$ 的执行过程如下：

如果 $i \gt j$ 或者 $i \geq arrLen$ 或者 $i \lt 0$ 或者 $j \lt 0$ ，那么返回 $0$ 。
如果 $i = 0$ 且 $j = 0$ ，那么此时指针已经停在原地，并且没有剩余步数，所以返回 $1$ 。
否则，我们可以选择向左走一步，向右走一步，或者不动，所以返回 $dfs(i - 1, j - 1) + dfs(i + 1, j - 1) + dfs(i, j - 1)$ 。注意答案的取模操作。

过程中，我们可以使用记忆化搜索避免重复计算。

时间复杂度 $O(steps \times steps)$ ，空间复杂度 $O(steps \times steps)$ 。其中 $steps$ 是题目给定的步数。

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:
        @cache
        def dfs(i, j):
            if i > j or i >= arrLen or i < 0 or j < 0:
                return 0
            if i == 0 and j == 0:
                return 1
            ans = 0
            for k in range(-1, 2):
                ans += dfs(i + k, j - 1)
                ans %= mod
            return ans

        mod = 10**9 + 7
        return dfs(0, steps)

speed

复杂度分析

指标	值
时间	complexity is O(steps * min(steps, arrLen)) because each step only updates positions reachable within steps. Space complexity is O(min(steps, arrLen)) using optimized DP storage for current and previous step counts.
空间	O(\min{(n, m)})

psychology

面试官常问的追问

外企场景

question_mark
Asks about handling large array lengths and step counts.
question_mark
Checks understanding of dynamic programming state transitions.
question_mark
Looks for optimization from O(steps _arrLen) to O(steps_ min(steps,arrLen)) space.

warning

常见陷阱

外企场景

error
Failing to limit positions beyond steps leads to unnecessary computation.
error
Forgetting modulo operations causes incorrect large-number results.
error
Using full 2D DP without space optimization can exceed memory limits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the number of ways to reach any target index instead of index 0.
arrow_right_alt
Allow only left or right moves, excluding staying in place.
arrow_right_alt
Compute the number of ways with obstacles at certain indices, preventing moves onto them.

help

常见问题

外企场景

继续练习

#1262 可被三整除的最大和 #1277 统计全为 1 的正方形子矩阵 #1278 分割回文串 III