[[426767]]

本文轉載自微信公眾號「我好困啊」，作者我好困啊。轉載本文請聯系我好困啊公眾號。

題目說明

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

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

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

圖片來源leetcode

示例1:

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

示例2:

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

提示：

• 1 <= m, n <= 100
• 題目數據保證答案小于等于 2 * 109

解題思路

利用動態規劃算法

1.定義狀態f[i][j]為到達(i,j)位置的路徑條數

2.f[0][0] = 1,那么最終m*n的表格，到達右下角的路徑條數即為f[m-1][n-1]中的值

3.每次移動情況，如果當前位置：

向下：f[i][j] = f[i-1][j]

向右: f[i][j] = f[i][j-1]

向下，向右:f[i][j] = f[i-1][j]+f[i][j-1]

如果你還不理解的話，觀看一下流轉圖：

以2*2的網格為例

說明，從f[0][0]出發，那么開始時，節點f[0][0]=1，

節點f[0][1]只能由于f[0][0]向右移動得到,即 f[0][1]=f[0][0]

節點f[1][0]同理，只能f[0][0]下移得到。即 f[1][0]=f[0][0]

節點f[1][1]，可以由于f[0][1]向下移動，f[1][0]向右移動。兩種移動方式得到。即：f[1][1] = f[0][1] + f[1][0]

最后，f[m-1][n-1]，右下角的位置即為最終結果

如果你還不理解的話，建議你手動畫一下2*3的表格移動狀態的轉移過程。

代碼實現

 1func uniquePaths(m int, n int) int { 
 2    f := make([][]int,m) 
 3    for i:= range f{ 
 4        f[i] = make([]int,n) 
 5    } 
 6    f[0][0] = 1 
 7    for i:=0;i<m;i++ { 
 8        for j:=0;j<n;j++ { 
 9            if i>0 && j>0 { //可以向下，向右移動 
10                f[i][j] = f[i-1][j] + f[i][j-1] 
11            }else if i>0 { //可以向下移動 
12                f[i][j] = f[i-1][j] 
13            }else if j>0 { //可以向右移動 
14                f[i][j] = f[i][j-1] 
15            } 
16        } 
17    } 
18    //循環結束后，走到了終點 
19    return f[m-1][n-1] 
20} 

復雜度分析

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