Use combination instead of DP


  • 0
    L
    class Solution:
        # @return an integer
        def uniquePaths(self, m, n):
            if m == 1:
                return 1
            if n == 1:
                return 1
            
            return self.combination(m+n-2, m-1)
        
        def combination(self, N, k):
            dt = {0:1}
            value = 1
            for i in xrange(1,N+1):
                value *= i
                dt[i] = value
            return dt[N]/(dt[k]*dt[N-k])

Log in to reply
 

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