Python DP memorization with good performance


  • 0
    C

    DP with memorization and good performance.

        def uniquePaths(self, m, n):
            def calPaths(i, j):
                if i <= 0 or j <= 0:
                    return 0
                if i == 1 or j == 1:
                    return 1
                if memo[i][j] == -1:
                    memo[i][j] = calPaths(i-1, j) + calPaths(i, j-1)
                return memo[i][j]
            
            memo = [[-1 for _ in xrange(n+1)] for _ in xrange(m+1)]
            return calPaths(m, n)
    

Log in to reply
 

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