Number of Ways to Stay in the Same Place After Some Steps

Number of Ways to Stay in the Same Place After Some Steps looks intimidating — the numbers explode and there is a modulo — but it is a clean little dynamic programming problem once you see the move set. You start at index 0 of an array and, on each step, go left, go right, or stay. Count the ways to be back at index 0 after exactly steps moves.

The slow way first

The brute force is to recursively try all three moves at every step: ways(step, pos) branches into stay, left, and right. That is O(3^steps) — for steps = 500 it is hopelessly slow, and it re-solves the same (step, pos) pair over and over.

The question to ask: what state actually determines the rest of the count? Only two things — how many steps remain and which position you are at. Everything else is irrelevant. That small state is the signal to switch to DP.

The idea: build up step by step

Let dp[pos] be the number of ways to be at pos right now. To get the counts for the next step, each position collects from the three places that can land on it: itself (stay), its left neighbor moving right, and its right neighbor moving left.

The crucial optimization: you can never wander further right than steps lets you, so reachable positions are capped at max_pos = min(steps, arrLen - 1). That keeps each row tiny even when arrLen is a billion.

Walk through it

Step through the animation with steps = 3, arrLen = 2, so max_pos = 1 and we track only positions 0 and 1. Start at dp = [1, 0]. Each step rebuilds the row with stay + left + right. After three steps dp = [4, 4], and the answer is dp[0] = 4.

Pseudocode

MOD = 10^9 + 7
max_pos = min(steps, arrLen - 1)      # cannot reach further than steps allow
dp = array of zeros over 0..max_pos
dp[0] = 1                              # one way to start at position 0
repeat steps times:
    nxt = array of zeros
    for each position p in 0..max_pos:
        stay  = dp[p]
        left  = dp[p-1] if p > 0 else 0
        right = dp[p+1] if p < max_pos else 0
        nxt[p] = (stay + left + right) mod MOD
    dp = nxt
return dp[0]

The Python solution

def num_ways(steps, arr_len):
    MOD = 10**9 + 7
    max_pos = min(steps, arr_len - 1)
    dp = [0] * (max_pos + 1)
    dp[0] = 1
    for _ in range(steps):
        nxt = [0] * (max_pos + 1)
        for p in range(max_pos + 1):
            stay = dp[p]
            left = dp[p - 1] if p > 0 else 0
            right = dp[p + 1] if p < max_pos else 0
            nxt[p] = (stay + left + right) % MOD
        dp = nxt
    return dp[0]

• max_pos = min(steps, arr_len - 1) caps the positions — this is what makes a huge arr_len cheap.
• dp[0] = 1 seeds the base case: one way to be at position 0 before any move.
• For each step we build a fresh nxt row so we read the previous step cleanly.
• Lines 9-12 are the recurrence: stay + left + right, with the edges guarded so we never index out of bounds.
• We take % MOD on every addition to keep the numbers from overflowing the intended range.

Complexity

Because positions are capped at min(steps, arrLen), each row has at most that many entries, so the work is bounded even when arrLen is enormous.

When this pattern shows up

Practice