Today's Challenge

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

Out of Boundary Paths - LeetCode

단순 재귀로 풀 수도 있는데, lru_cache라는 옵션을 추가하면 속도가 엄청나게 향상되는 듯

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        mod = (10**9)+7
        @lru_cache(None)
        def moves(move, r, c):
            if r == m or r < 0 or c < 0 or c == n:
                return 1
            if move == 0:
                return 0
            move -= 1
            
            return (moves(move, r+1, c) + moves(move, r, c+1) + moves(move, r-1, c) +  moves(move, r, c-1)) % mod
        
        return moves(maxMove, startRow, startColumn)