Python submission through calculation the number of combination


  • 0
    L

    This problem is actually an combination problem in probability. A list of arrays with m-1 down move and n-1 right move. thus the answer is (m+n-2)!/(n-1)!/(m-1)!

    class Solution:
        # @return an integer
        def uniquePaths(self, m, n):
            # recurssive solution is very costy.
            (m,n)=(m,n) if m>n else (n,m)
            # make sure m is larger than n to save the computation
            res,jj=1,m
            while jj<=m+n-2:
                res,jj=res*jj,jj+1
            jj=2
            while jj<=n-1:
                res,jj=res/jj,jj+1
            return res

Log in to reply
 

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