Number of Ways to Stay in the Same Place

lcpy gen -n 1269   # by problem number
lcpy gen -s number_of_ways_to_stay_in_the_same_place_after_some_steps   # by problem name

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

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

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

class Solution:
    def num_ways(self, steps: int, arr_len: int) -> int:
        mod = 1_000_000_007
        limit = min(steps // 2 + 1, arr_len)
        dp = [0] * limit
        dp[0] = 1
        for _ in range(steps):
            ndp = [0] * limit
            for i in range(limit):
                ndp[i] = dp[i]
                if i > 0:
                    ndp[i] += dp[i - 1]
                if i + 1 < limit:
                    ndp[i] += dp[i + 1]
                ndp[i] %= mod
            dp = ndp
        return dp[0]