top_down.py

"""
DP top down
dp(pos, step) = sum(dp(pos+1, step-1), dp(pos-1, step-1), dp(pos, step-1))
"""
from functools import lru_cache
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9 + 7
        @lru_cache(None)
        def dp(pos, steps):
            if pos < 0 or pos >= arrLen: return 0
            if pos > steps: return 0
            if steps == pos: return 1
            return (dp(pos+1, steps-1) + dp(pos-1, steps-1) + dp(pos, steps-1)) % MOD
        
        return dp(0, steps)