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

Problem statement

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/

Solution

Just do dp with state (index, steps done). Note, that on each step we can have 3 possible options, and also that it does no matter that m be quite big, we never need to traverse more than half of n.

Complexity

Time complexity is O(n*min(n, m)), where n = steps and m = arrLen

Code

class Solution:
    def numWays(self, steps, arrLen):
        @lru_cache(None)
        def dp(ind, s):
            if not 0 <= ind < arrLen: return 0
            if s == 0: return ind == 0
            return (dp(ind-1, s-1) + dp(ind, s-1) + dp(ind+1, s-1)) % MOD
        
        MOD = 10**9 + 7
        return dp(0, steps)