[[426767]]

本文轉(zhuǎn)載自微信公眾號(hào)「我好困啊」，作者我好困啊。轉(zhuǎn)載本文請(qǐng)聯(lián)系我好困啊公眾號(hào)。

題目說明

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 (起始點(diǎn)在下圖中標(biāo)記為 “Start” )。

機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角(在下圖中標(biāo)記為 “Finish” )。

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

圖片來源leetcode

示例1:

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

示例2:

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

提示：

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

解題思路

利用動(dòng)態(tài)規(guī)劃算法

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

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

3.每次移動(dòng)情況，如果當(dāng)前位置：

向下：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]

如果你還不理解的話，觀看一下流轉(zhuǎn)圖：

以2*2的網(wǎng)格為例

說明，從f[0][0]出發(fā)，那么開始時(shí)，節(jié)點(diǎn)f[0][0]=1，

節(jié)點(diǎn)f[0][1]只能由于f[0][0]向右移動(dòng)得到,即 f[0][1]=f[0][0]

節(jié)點(diǎn)f[1][0]同理，只能f[0][0]下移得到。即 f[1][0]=f[0][0]

節(jié)點(diǎn)f[1][1]，可以由于f[0][1]向下移動(dòng)，f[1][0]向右移動(dòng)。兩種移動(dòng)方式得到。即：f[1][1] = f[0][1] + f[1][0]

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

如果你還不理解的話，建議你手動(dòng)畫一下2*3的表格移動(dòng)狀態(tài)的轉(zhuǎn)移過程。

代碼實(shí)現(xiàn)

 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 { //可以向下，向右移動(dòng) 
10                f[i][j] = f[i-1][j] + f[i][j-1] 
11            }else if i>0 { //可以向下移動(dòng) 
12                f[i][j] = f[i-1][j] 
13            }else if j>0 { //可以向右移動(dòng) 
14                f[i][j] = f[i][j-1] 
15            } 
16        } 
17    } 
18    //循環(huán)結(jié)束后，走到了終點(diǎn) 
19    return f[m-1][n-1] 
20} 

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(m*n)
• 空間復(fù)雜度: O(m*n)