BinarySearch 0122 A Maniacal Walk

Problem statement

https://binarysearch.com/problems/A-Maniacal-Walk/

Solution

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

Complexity

It is O(n * m) here for time and space.

Code

class Solution:
    def solve(self, length, n):
        @lru_cache(None)
        def dp(ind, s):
            if not 0 <= ind < length: 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 int(dp(0, n))