Python easy to understand solutions (math, dp O(m*n) and O(n) space).


  • 10
    C
    # math C(m+n-2,n-1)
    def uniquePaths1(self, m, n):
        if not m or not n:
            return 0
        return math.factorial(m+n-2)/(math.factorial(n-1) * math.factorial(m-1))
     
    # O(m*n) space   
    def uniquePaths2(self, m, n):
        if not m or not n:
            return 0
        dp = [[1 for _ in xrange(n)] for _ in xrange(m)]
        for i in xrange(1, m):
            for j in xrange(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]
    
    # O(n) space 
    def uniquePaths(self, m, n):
        if not m or not n:
            return 0
        cur = [1] * n
        for i in xrange(1, m):
            for j in xrange(1, n):
                cur[j] += cur[j-1]
        return cur[-1]

  • 0
    L

    Very nice solution! I am a beginner in python. For the dp method, can you explain more about why do we use " dp = [[1 for _ in xrange(n)] for _ in xrange(m)] " Why do you use value 1? and why is xrange(n) first not xrange[m]? Thanks a lot.


Log in to reply
 

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