題目：

一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為 “Finish” ）。

問總共有多少條不同的路徑？

示例 1：

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

輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
   示例 3：

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

輸入：m = 3, n = 3
輸出：6

提示：

1 <= m, n <= 100
題目數(shù)據(jù)保證答案小于等于 2 * 109

思路：

剛看到這道題第一時間想不到這跟動態(tài)規(guī)劃有什么關系，這不是圖的深搜嗎？
但大家試過之后就會發(fā)圖的深搜會超時。

動態(tài)規(guī)劃：

機器人從(0 , 0) 位置出發(fā)，到(m - 1, n - 1)終點。

按照動規(guī)五部曲來分析：

1. 確定dp數(shù)組，以及下標的含義

這里要明確dp數(shù)組的含義，定義dp數(shù)組是為了找到不同路徑，
dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。

2. 確定遞推公式

這道題的遞歸公式不像之前的題一下就能看出來，
想要求dp[i][j]，只能有兩個方向來推導出來，即dp[i - 1][j] 和 dp[i][j - 1]。

此時在回顧一下 dp[i - 1][j] 表示啥，是從(0, 0)的位置到(i - 1, j)有幾條路徑，dp[i][j - 1]同理。

那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因為dp[i][j]只有這兩個方向過來。

可能有人會疑惑 dp[i - 1][j] 向下走一步就到dp[i][j]，dp[i][j - 1]向右走一步就到dp[i][j]，那為什么dp[i][j] 不等于 dp[i - 1][j] + dp[i][j - 1] + 1 + 1 呢？這里要明白dp數(shù)組的含義，這里dp數(shù)組求的是路徑而不是步數(shù)，你走一步路徑數(shù)并沒有發(fā)生變化。

3. dp數(shù)組的初始化

如何初始化呢，首先dp[i][0]一定都是1，因為從(0, 0)的位置到(i, 0)的路徑只有一條，那么dp[0][j]也同理。

4. 確定遍歷順序

這里要看一下遞推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是從其上方和左方推導而來，那么從左到右一層一層遍歷就可以了。

這樣就可以保證推導dp[i][j]的時候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值的。

5. 舉例推導dp數(shù)組

如圖所示：

這里要說明一下dp數(shù)組的日志打印，如果你提交不通過，你可以直接輸出dp數(shù)組，看看你是哪一步出現(xiàn)問題，然后對癥下藥。

定義二維數(shù)組

寫過很多要定義二維數(shù)組的題了，但依然是一寫就忘，這里稍微說一下python中二維數(shù)組的定義，

方法一：

dp = [[0] * n for _ in range(m)]

方法二（跟一其實是一個東西）：

dp = [[0 for i in range(n)] for j in range(m)]

方法三（NumPy庫）：

import numpy as np# 創(chuàng)建一個n×m的二維數(shù)組，初始值為0  np.ones((n, m)) 初始值為1
array = np.zeros((n, m))

完整代碼：

class Solution:def uniquePaths(self, m: int, n: int) -> int:# 創(chuàng)建一個二維列表用于存儲唯一路徑數(shù)dp = [[0] * n for _ in range(m)]# 設置第一行和第一列的基本情況for i in range(m):dp[i][0] = 1for j in range(n):dp[0][j] = 1# 計算每個單元格的唯一路徑數(shù)for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i - 1][j] + dp[i][j - 1]# 返回右下角單元格的唯一路徑數(shù)return dp[m - 1][n - 1]

復雜度分析：

• 時間復雜度：O(m × n)
• 空間復雜度：O(m × n)

PS：

做完本題可以接著做力扣：63. 不同路徑 II，完全一樣的思路。
詳細見：力扣：63. 不同路徑 II（動態(tài)規(guī)劃）