Clean DP and Math solution in python


  • 0
    class Solution(object):
        '''
        combination problem:from m+n-2 elements choose m-1 elements
        '''
        def uniquePaths(self, m, n):
            return reduce(lambda x, y: x and x / y or y, map(math.factorial, (m + n - 2, m - 1, n - 1)))
    
    
    class Solution(object):
        '''
        dp[i][j]: the unique paths from (0, 0) to (i, j), then
    
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        '''
        def uniquePaths(self, m, n):
            dp = [[0] * n for _ in xrange(m)]
    
            for i in xrange(m):
                for j in xrange(n):
                    dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1], 1)
    
            return dp[m - 1][n - 1]

Log in to reply
 

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