1269. Number of Ways to Stay in the Same Place After Some Steps - Explanation

1. Dynamic Programming (Top-Down)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(arrLen, steps)
        dp = {}

        def dfs(i, steps):
            if steps == 0:
                return i == 0
            if (i, steps) in dp:
                return dp[(i, steps)]

            res = dfs(i, steps - 1)
            if i > 0:
                res = (res + dfs(i - 1, steps - 1)) % mod
            if i < arrLen - 1:
                res = (res + dfs(i + 1, steps - 1)) % mod

            dp[(i, steps)] = res
            return res

        return dfs(0, steps)

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(n * min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.

2. Dynamic Programming (Bottom-Up)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(arrLen, steps)
        dp = [[0] * (arrLen + 1) for _ in range(steps + 1)]
        dp[0][0] = 1

        for step in range(1, steps + 1):
            for i in range(arrLen):
                res = dp[step - 1][i]
                if i > 0:
                    res = (res + dp[step - 1][i - 1]) % mod
                if i < arrLen - 1:
                    res = (res + dp[step - 1][i + 1]) % mod
                dp[step][i] = res

        return dp[steps][0]

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(n * min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.

3. Dynamic Programming (Space Optimized)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(steps, arrLen)
        dp = [0] * arrLen
        dp[0] = 1

        for _ in range(steps):
            next_dp = [0] * arrLen
            for i in range(arrLen):
                next_dp[i] = dp[i]
                if i > 0:
                    next_dp[i] = (next_dp[i] + dp[i - 1]) % mod
                if i < arrLen - 1:
                    next_dp[i] = (next_dp[i] + dp[i + 1]) % mod
            dp = next_dp

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.

4. Dynamic Programming (Optimal)

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(steps, arrLen)
        dp = [0] * arrLen
        dp[0] = 1

        for _ in range(steps):
            prev = 0
            for i in range(arrLen):
                cur = dp[i]
                if i > 0:
                    dp[i] = (dp[i] + prev) % mod
                if i < arrLen - 1:
                    dp[i] = (dp[i] + dp[i + 1]) % mod
                prev = cur

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.