⚡Flashcard Drill➔
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

  1. Let dp[pos] be the number of ways to be at position pos after the current number of steps; the base is dp[0] = 1.
  2. Each step updates nxt[pos] = dp[pos] + dp[pos-1] + dp[pos+1], corresponding to staying, moving left, and moving right.
  3. A position beyond min(arrLen - 1, steps // 2) can never be part of a round trip, so the array can be truncated dramatically.
  4. The answer is dp[0] after steps iterations.

💻 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 arrLen array: arrLen can be 10^6 while steps is only 500, so the reachable range is min(arrLen - 1, steps // 2).
  • Ignoring the steps // 2 bound: to return to 0, each right move needs a matching left move, so no valid round trip goes beyond steps // 2.
  • Forgetting the right boundary: moving right from max_pos would 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems