LC 1269 [H] Number of Ways to Stay in the Same Place After Some Steps - ALawliet/algorithms GitHub Wiki

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        @cache # cache[steps,idx] = tmp % MOD
        def dfs(steps, idx):
            # pruning: not enough remaining steps to get back to 0
            if idx - 0 > steps:
                return 0
            
            # out of bounds caching
            if idx >= arrLen or idx < 0:
                return 0
            
            if steps == 0:
                if idx == 0:
                    return 1
                return 0
            
            tmp = 0
            tmp += dfs(steps-1, idx-1) # left
            tmp += dfs(steps-1, idx) # stay
            tmp += dfs(steps-1, idx+1) # right
            
            return tmp % MOD
        
        MOD = 10**9+7 # mod too big answer indicated by problem statement
        return dfs(steps, 0)