# Number of Ways to Stay in the Same Place After Some Steps
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
---
## Problem
You have a pointer at index `0` in an array of size `arrLen`. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers `steps` and `arrLen`, return the number of ways such that your pointer is still at index `0` after **exactly** `steps` steps. Since the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** steps = 3, arrLen = 2
**Output:** 4
**Explanation:** There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

**Example 2:**

**Input:** steps = 2, arrLen = 4
**Output:** 2
**Explanation:** There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

**Example 3:**

**Input:** steps = 4, arrLen = 2
**Output:** 8

**Constraints:**

* `1 <= steps <= 500`
* `1 <= arrLen <= 106`

# Approaches
## Top-Down Dynamic Programming (Recursion with Memoization)
This approach uses recursion with memoization, a top-down dynamic programming technique. We define a function that calculates the number of ways to reach a certain position with a certain number of steps remaining. The problem has overlapping subproblems (e.g., the ways to reach position `p` in `s` steps is needed by multiple future states), which makes it a perfect candidate for memoization to store and reuse results of subproblems.
**Time:** O(steps * min(arrLen, steps)). Each state `(stepsLeft, pos)` is computed only once. The number of states is `steps * maxPos`, where `maxPos` is `min(arrLen, steps + 1)`. · **Space:** O(steps * min(arrLen, steps)). This is for the memoization table `memo` which stores the result for each state `(steps, pos)`. The recursion depth can also go up to `steps`, contributing to stack space.
**Pros:** Intuitive and closely follows the problem's recursive definition.; Handles the state space pruning (`pos > stepsLeft`) naturally.
**Cons:** May lead to stack overflow for very large `steps` (not an issue with the given constraints).; Generally has higher overhead than iterative bottom-up approaches due to function calls.
### Explanation
The core idea is to define a function `solve(stepsLeft, pos)` that computes the number of ways to end up at `pos` given `stepsLeft` moves. The state is defined by `(stepsLeft, pos)`. The transitions are based on the three allowed moves: stay, move left, or move right. We call the function recursively for `stepsLeft - 1` and the corresponding new positions.

To make this efficient, we store the results for each state `(stepsLeft, pos)` in a 2D memoization table. This prevents redundant calculations for the same state, drastically reducing the time complexity from exponential to polynomial.

The maximum possible index we can reach is limited by the number of steps. For instance, with `s` steps, we can't reach an index greater than `s`. Therefore, we can effectively cap the array length to `min(arrLen, steps + 1)` for our state space.

```java
class Solution {
    int MOD = 1_000_000_007;
    int maxPos;
    Integer[][] memo;

    public int numWays(int steps, int arrLen) {
        this.maxPos = Math.min(arrLen, steps + 1);
        this.memo = new Integer[steps + 1][this.maxPos];
        return solve(steps, 0);
    }

    private int solve(int stepsLeft, int pos) {
        if (pos < 0 || pos >= maxPos) {
            return 0;
        }
        if (stepsLeft == 0) {
            return pos == 0 ? 1 : 0;
        }
        // Optimization: if we are further from 0 than steps left, we can't return.
        if (pos > stepsLeft) {
            return 0;
        }

        if (memo[stepsLeft][pos] != null) {
            return memo[stepsLeft][pos];
        }

        long res = 0;
        // Stay
        res = (res + solve(stepsLeft - 1, pos)) % MOD;
        // Move Left
        res = (res + solve(stepsLeft - 1, pos - 1)) % MOD;
        // Move Right
        res = (res + solve(stepsLeft - 1, pos + 1)) % MOD;

        memo[stepsLeft][pos] = (int) res;
        return (int) res;
    }
}
```
### Algorithm
- Define a recursive function, let's call it `solve(stepsLeft, pos)`, which returns the number of ways to get to `pos` with `stepsLeft` remaining.
- The base cases for the recursion are:
  - If `pos` is out of bounds (`< 0` or `>= arrLen`), there are 0 ways. Return 0.
  - If `stepsLeft` is 0, there is 1 way if `pos` is 0, and 0 ways otherwise.
  - An important optimization: if `pos > stepsLeft`, it's impossible to return to index 0, so we can return 0.
- To avoid recomputing the same state `(stepsLeft, pos)` multiple times, use a 2D array `memo` for memoization. Before computing, check if the result is already in `memo`.
- The recursive step calculates the result by summing the ways from the three possible previous moves: `solve(stepsLeft - 1, pos)` (stay), `solve(stepsLeft - 1, pos - 1)` (move left), and `solve(stepsLeft - 1, pos + 1)` (move right).
- The maximum position that needs to be considered is limited by `steps`. Any `arrLen` greater than `steps + 1` behaves the same as `arrLen = steps + 1`. So, we can cap the array length at `steps + 1`.

## Bottom-Up Dynamic Programming (2D DP Table)
This approach uses bottom-up dynamic programming. Instead of recursion, we build the solution iteratively. We use a 2D array, `dp[s][p]`, to store the number of ways to reach position `p` after `s` steps. We start from the base case (`s=0`) and iteratively compute the values for each subsequent step up to the target `steps`.
**Time:** O(steps * min(arrLen, steps)). We iterate through each state `(s, p)` once with two nested loops. · **Space:** O(steps * min(arrLen, steps)). The 2D `dp` table of size `(steps + 1) x maxPos` dominates the space usage.
**Pros:** Avoids recursion overhead and the risk of stack overflow.; The logic is often more straightforward to reason about for tabulation-based DP.
**Cons:** Requires a large amount of memory, O(steps * min(arrLen, steps)), which can be inefficient.
### Explanation
We build a table of solutions for all subproblems, starting from the smallest. The state `dp[s][p]` represents the number of ways to be at index `p` after `s` steps. The value of `dp[s][p]` is derived from the states at the previous step, `s-1`. Specifically, to reach `p` at step `s`, one could have been at `p-1`, `p`, or `p+1` at step `s-1`.

By filling the `dp` table row by row (for each step), we ensure that when we calculate `dp[s][p]`, the required values from `dp[s-1]` have already been computed. The final answer is simply the value at `dp[steps][0]`, which represents the number of ways to be at index 0 after exactly `steps` moves.

```java
class Solution {
    public int numWays(int steps, int arrLen) {
        int MOD = 1_000_000_007;
        int maxPos = Math.min(arrLen, steps + 1);
        
        long[][] dp = new long[steps + 1][maxPos];
        dp[0][0] = 1;

        for (int s = 1; s <= steps; s++) {
            for (int p = 0; p < maxPos; p++) {
                // 1. Stay at the same position
                dp[s][p] = dp[s - 1][p];
                
                // 2. Move from the left (p-1 to p)
                if (p > 0) {
                    dp[s][p] = (dp[s][p] + dp[s - 1][p - 1]) % MOD;
                }
                
                // 3. Move from the right (p+1 to p)
                if (p < maxPos - 1) {
                    dp[s][p] = (dp[s][p] + dp[s - 1][p + 1]) % MOD;
                }
            }
        }
        
        return (int) dp[steps][0];
    }
}
```
### Algorithm
- Create a 2D DP array, `dp[s][p]`, to store the number of ways to be at position `p` after exactly `s` steps.
- The size of the DP table will be `(steps + 1) x maxPos`, where `maxPos = min(arrLen, steps + 1)`.
- Initialize the base case: `dp[0][0] = 1`, as there is one way to be at position 0 with 0 steps (by starting there).
- Iterate from `s = 1` to `steps`.
- For each step `s`, iterate through each possible position `p` from `0` to `maxPos - 1`.
- The transition formula is: `dp[s][p] = (dp[s-1][p] + dp[s-1][p-1] + dp[s-1][p+1]) % MOD`. Care must be taken to handle boundary conditions for `p-1` and `p+1`.
- The final answer is the value at `dp[steps][0]`.

## Space-Optimized Bottom-Up DP (1D DP Array)
This is the most efficient approach, optimizing the space complexity of the bottom-up DP. By analyzing the state transition, we notice that to compute the number of ways for the current step `s`, we only need the results from the immediate previous step `s-1`. This means we don't need to store the entire 2D DP table. We can use just two 1D arrays: one to hold the results of the previous step and one to compute the results for the current step.
**Time:** O(steps * min(arrLen, steps)). The nested loop structure remains the same as the 2D DP approach. · **Space:** O(min(arrLen, steps)). We only need two arrays of size `maxPos`, which is `min(arrLen, steps + 1)`. This is a significant improvement.
**Pros:** Highly space-efficient, using only O(min(arrLen, steps)) space.; Maintains the same optimal time complexity as the 2D DP approach.
**Cons:** The implementation can be slightly more complex due to managing and swapping two arrays.
### Explanation
We maintain two arrays, `prevDp` for the state at step `s-1` and `dp` for the state at step `s`. We iterate from `s=1` to `steps`. In each iteration, we compute `dp[p]` for all `p` using the values in `prevDp`. Once the `dp` array is fully computed for step `s`, it becomes the `prevDp` for the next step, `s+1`. This is efficiently handled by swapping the references of the two arrays.

This optimization reduces the space complexity significantly, from quadratic to linear with respect to the number of steps, without affecting the time complexity. This makes it the most suitable approach given the problem constraints.

```java
class Solution {
    public int numWays(int steps, int arrLen) {
        int MOD = 1_000_000_007;
        int maxPos = Math.min(arrLen, steps + 1);
        
        long[] dp = new long[maxPos];
        long[] prevDp = new long[maxPos];
        prevDp[0] = 1;

        for (int s = 1; s <= steps; s++) {
            for (int p = 0; p < maxPos; p++) {
                // 1. Stay
                dp[p] = prevDp[p];
                
                // 2. Move from left
                if (p > 0) {
                    dp[p] = (dp[p] + prevDp[p - 1]) % MOD;
                }
                
                // 3. Move from right
                if (p < maxPos - 1) {
                    dp[p] = (dp[p] + prevDp[p + 1]) % MOD;
                }
            }
            // Swap arrays for the next iteration
            long[] temp = dp;
            dp = prevDp;
            prevDp = temp;
        }
        
        return (int) prevDp[0];
    }
}
```
### Algorithm
- Observe that the calculation for step `s` only depends on the results from step `s-1`. This allows for space optimization.
- Instead of a 2D table, use two 1D arrays, `dp` (for the current step) and `prevDp` (for the previous step), each of size `maxPos = min(arrLen, steps + 1)`.
- Initialize `prevDp[0] = 1`.
- Iterate from `s = 1` to `steps`.
- In each iteration, calculate the values for the `dp` array using the values from `prevDp` based on the same transition formula.
- After computing all positions for step `s`, update `prevDp` with the values from `dp` for the next iteration. This can be done by swapping the array references.
- The final answer is `prevDp[0]` after the loop finishes.

# Solutions
### Java

```java
class Solution {
private
  Integer[][] f;
private
  int n;
public
  int numWays(int steps, int arrLen) {
    f = new Integer[steps][steps + 1];
    n = arrLen;
    return dfs(0, steps);
  }
private
  int dfs(int i, int j) {
    if (i > j || i >= n || i < 0 || j < 0) {
      return 0;
    }
    if (i == 0 && j == 0) {
      return 1;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = 0;
    final int mod = (int)1 e9 + 7;
    for (int k = -1; k <= 1; ++k) {
      ans = (ans + dfs(i + k, j - 1)) % mod;
    }
    return f[i][j] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numWays(int steps, int arrLen) {
    int f[steps][steps + 1];
    memset(f, -1, sizeof f);
    const int mod = 1e9 + 7;
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i > j || i >= arrLen || i < 0 || j < 0) {
        return 0;
      }
      if (i == 0 && j == 0) {
        return 1;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      int ans = 0;
      for (int k = -1; k <= 1; ++k) {
        ans = (ans + dfs(i + k, j - 1)) % mod;
      }
      return f[i][j] = ans;
    };
    return dfs(0, steps);
  }
};

```

### Python

```python
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)

```