62. Unique Paths LeetCode

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

avatar

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Fisrt

跟台阶问题有些类似，这里走到终点时，我们可以判断。
走到终点的所有可能走法等于走到终点左边和上面的所有可能走法的总和
即 Sum(i,j) = Sum(i, j-1) + Sum(i-1, j)
这就可以将问题简化，先求出子问题的解，再通过子问题的解得出问题的解。

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [1 for i in range(m)]
        for i in range(1, n):
            for j in range(1, m):
                dp[j] = dp[j-1] + dp[j]
        return dp[-1]

代码思想通过自底向上的解法，不断得出子问题的解，再通过子问题得到整个问题的解。
由于每个子问题只会用到一次， 因此可以使用一个一维数组来缓存中间值，将数组复用。

Fastest

大佬代码思想没有看懂，留给有缘人看吧

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        r = m-1
        d = n-1
        t = m+n-2
        x = min(r,d)
        res1 = 1.0
        res2 = 1.0
        while x!=0:
            res1 = res1*t
            res2 = res2*x
            x-=1
            t-=1
       
        return int(res1/res2)