Simple recursive DP Python


  • 0

    We can reduce repetitive work by memoizing each coordinate coupled with the moves left when that coordinate was reached.

        def findPaths(self, m, n, N, i, j):
     
            def try_path(r, c, m, n, mv, N, memo, directions):
                if r < 0 or r >= m or c < 0 or c >= n: return 1 # reached OB
                if mv == N: return 0 # ran out of moves
                pos = (r, c, mv) # memoize coord, moves left
                if pos not in memo:
                    cnt, mv = 0, mv + 1
                    for dr, dc in directions: # try each direction
                        cnt += try_path(r+dr, c+dc, m, n, mv, N, memo, directions)
                    memo[pos] = cnt
                return memo[pos]
            
            directions = {(0,1), (0,-1), (1,0), (-1,0)}
            return try_path(i, j, m, n, 0, N, {}, directions) % (10 ** 9 + 7)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.