Teaching Kids Programming – Number of Ways to Stay in the Same Place After Some Steps (Top Down Dynamic Programming Algorithm, Recursion with Memoization)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 <= 10^6

Number of Ways to Stay in the Same Place After Some Steps (Top Down Dynamic Programming Algorithm, Recursion with Memoization)

We can solve this problem intuitively by Recursion. Let f(x, r) be the number of different ways for the position x with r remaining steps to reach to zero. So, we can easily get that there are three choices: left, right or stay.

The terminal conditions: When we have made r steps, so we need to check the position. Also, if at any point, the position is outside the window: beyond the left, or beyong the right boundary, then we need to immediately return zero.

Another optimisation: when we are at position x, and there is r steps remaining but r is smaller than p, then we can simply return zero because even we perform all these r steps turning left, we still cannot make it to zero position.

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:
        MOD = 1_000_000_007
 
        @cache
        def f(x, r):
            if r == 0:
                return x == 0            
            if x > r or x < 0 or x >= arrLen:
                return 0
 
            a = f(x, r - 1) % MOD
            b = f(x - 1, r - 1) % MOD
            c = f(x + 1, r - 1) % MOD
            return (a + b + c) % MOD
 
        return f(0, steps)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 1_000_000_007

        @cache
        def f(x, r):
            if r == 0:
                return x == 0            
            if x > r or x < 0 or x >= arrLen:
                return 0

            a = f(x, r - 1) % MOD
            b = f(x - 1, r - 1) % MOD
            c = f(x + 1, r - 1) % MOD
            return (a + b + c) % MOD

        return f(0, steps)

The @cache makes it a Top Down Dynamic Programming Algorithm aka Recursion with Memoization. The intermediate values are cached and only computed once. Therefore time/space complexity is bounded by O(LS) where L is the length of the array and S is the number of steps.

–EOF (The Ultimate Computing & Technology Blog) —