576. Out of Boundary Paths

https://leetcode.com/problems/out-of-boundary-paths/

Python

Top Down DP

from functools import cache

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        @cache
        def dp(row: int, col: int, remains: int) -> int:
            if row >= m or row < 0 or col >= n or col < 0:
                return 1

            if remains == 0:
                return 0

            result = dp(row+1, col, remains-1) + \
                     dp(row-1, col, remains-1) + \
                     dp(row, col+1, remains-1) + \
                     dp(row, col-1, remains-1)

            return result % (10**9 + 7)

        return dp(startRow, startColumn, maxMove)