Use combination instead of DP

  • 0
    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.