Simple Python DP Memoization O( m * n * N)


  • 0

    We can save duplicate work by memoizing computed combinations at each grid point. Key is to record moves left when memoizing as the combination count will be different for different remaining move counts.

        def findPaths(self, m, n, N, i, j):
    
            def traverse(r, c, moves, l, h, cache, directions):
                if r < 0 or r >= h or c < 0 or c >= l: # out of bounds
                    return 1
                if not moves: # not out of bound and ran out of moves
                    return 0
                key = (r, c, moves)
                if key not in cache:
                    moves -= 1
                    cache[key] = sum(traverse(r + dr, c + dc, moves, l, h, cache, directions) for dr, dc in directions)
                return cache[key]
            
            directions = [(0,1),(0,-1),(1,0),(-1,0)] # list of possible 4 directions
            return traverse(i, j, N, n, m, {}, directions) % (10 ** 9 + 7)
    

Log in to reply
 

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