DP and recursive solution that actually starts from the start point

  • 0
    class Solution(object):
        def uniquePaths(self, m, n):
            return self.uniquePathsDP(m,n)
        def uniquePathsDP(self, m,n):
            cache = [[0 for x in range(n+1)] for y in range(m+1)]
            cache[m-1][n-1] = 1
            print cache
            for col in range(n-1, -1, -1):
                for row in range(m-1,-1,-1):
                    cache[row][col] += cache[row+1][col]
                    cache[row][col] += cache[row][col+1]
            return cache[0][0]
        def uniquePathsRecurse(self, m, n, curr):
            if curr[0] == m-1 and curr[1]  == n-1:
                return 1
            moveDown = (curr[0]+1, curr[1])
            moveRight = (curr[0], curr[1]+1)
            possiblePaths = 0
            if self.isValid(m,n,moveDown):
                possiblePaths += self.uniquePathsRecurse(m,n,moveDown)
            if self.isValid(m,n,moveRight):
                possiblePaths += self.uniquePathsRecurse(m,n,moveRight)
            return possiblePaths
        def isValid(self, m,n,point):
            if 0<=point[0]<m:
                if 0<=point[1]<n:
                    return True
            return False

Log in to reply

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