DP Python (easy to understand)


  • 0
    A
    class Solution(object):
        def findPaths(self, m, n, N, i, j):
            # m x n board, can move max N times, start pos i, j
            numWays = 0
         
            # next state just keeps track of what possible coordinates we can go from a given coordinate
            nextStateDict = self.createNextStateDict(m, n)
            
            # keeps track of how many times we see a coordinate
            # at start, we only see one coordinate, which are the start coordinates
            posCount = {(i,j):1}    
            
            for _ in xrange(N):
                new_pos_count = dict()
                # iterate through all the positions
                for pos in posCount:
                    # get all valid new positions from pos
                    validMoves = nextStateDict[pos]
                    numWays += (4 - len(validMoves)) * posCount[pos]    
                    
                    for newPos in validMoves:
                        if newPos not in new_pos_count:
                            new_pos_count[newPos] = 0
                        new_pos_count[newPos] += posCount[pos]
                posCount = new_pos_count
            return numWays % (10**9 + 7)
            
        def getValidMoves(self, m, n, i, j):
            # given pos (i,j), what next states can i be in?
            posAfterOneMove = [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
            return [(a,b) for a,b in posAfterOneMove if (0 <= a < m) and (0 <= b < n)]
        
        def createNextStateDict(self, m, n):
            # for each pos in board, get a dict of next possible states
            d = dict()
            for row in range(0, m):
                for col in range(0, n):
                    d[(row,col)] = self.getValidMoves(m, n, row, col)
            return d
    

Log in to reply
 

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