62. 不同路徑

一個(gè)機(jī)器人位于一個(gè) m x n網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。
問總共有多少條不同的路徑？

示例 1： 輸入：m = 3, n = 7 輸出：28

示例 2： 輸入：m = 3, n = 2 輸出：3
解釋：從左上角開始，總共有 3 條路徑可以到達(dá)右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 3： 輸入：m = 7, n = 3 輸出：28

示例 4： 輸入：m = 3, n = 3 輸出：6

提示：

• 1 <= m, n <= 100
• 題目數(shù)據(jù)保證答案小于等于 2 * 10<sup>9</sup>

解題思路：

1. 動(dòng)態(tài)規(guī)劃

   
   

2. 數(shù)學(xué)方式

   
   

兩種代碼，實(shí)際第一種比較快

代碼：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        x = [[1]*n]*m
        print (x)
        for i in range(1,m):
            for j in range(1,n):
                x[i][j] = x[i-1][j] + x[i][j-1]
        return x[m-1][n-1]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)

參考資料：

https://leetcode-cn.com/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/