math solution O(m+n) time with python code


  • 0
    P
    def uniquePaths(self, m, n):
        factorial = [1]
        for i in range(1, m+n):
            factorial.append(factorial[i-1]*i)
        return factorial[m+n-2]//factorial[n-1]//factorial[m-1]
    

    Compute $C_{m+n-2}^{m-1}$. Since we need to go right for n-1 times, go down for m-1 times, it will be the number of how many different ways we can combine the right and down.


Log in to reply
 

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