NeetCode #751LC-1269Hard2-D Dynamic Programming
← Back to All Problems#751 · #1269 · Number of Ways to Stay in the Same Place After Some Steps(停在原地的方案数)
📌 Problem Statement & Constraints
An array has length
arrLen and a pointer starts at index 0. Each step the pointer moves left, right, or stays put, and it must remain within [0, arrLen - 1]. Return the number of ways to be back at index 0 after exactly steps steps, modulo 1e9+7. Constraints: 1 <= steps <= 500, 1 <= arrLen <= 10^6.💡 Core Algorithmic Approaches
- Let
dp[pos]be the number of ways to be at positionposafter the current number of steps; the base isdp[0] = 1. - Each step updates
nxt[pos] = dp[pos] + dp[pos-1] + dp[pos+1], corresponding to staying, moving left, and moving right. - A position beyond
min(arrLen - 1, steps // 2)can never be part of a round trip, so the array can be truncated dramatically. - The answer is
dp[0]afterstepsiterations.
💻 Benchmark Python3 Implementation
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
MOD = 10**9 + 7
max_pos = min(arrLen - 1, steps // 2) # farther positions are unreachable in time
dp = [0] * (max_pos + 1)
dp[0] = 1
for _ in range(steps):
nxt = [0] * (max_pos + 1)
for pos in range(max_pos + 1):
ways = dp[pos] # stay
if pos > 0:
ways += dp[pos - 1] # move left
if pos < max_pos:
ways += dp[pos + 1] # move right
nxt[pos] = ways % MOD
dp = nxt
return dp[0] % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(steps * min(arrLen, steps)): the reachable range is capped at steps // 2.
💾 Space Complexity
O(min(arrLen, steps)): two rolling arrays.
⚠️ Interview Pitfalls & Follow-ups
- Allocating the full
arrLenarray:arrLencan be 10^6 whilestepsis only 500, so the reachable range ismin(arrLen - 1, steps // 2). - Ignoring the
steps // 2bound: to return to 0, each right move needs a matching left move, so no valid round trip goes beyondsteps // 2. - Forgetting the right boundary: moving right from
max_poswould exceed the array, so the transition must be guarded. - Dropping the stay option: staying is always allowed, so
dp[pos]itself is a term in the recurrence.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.