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

機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為“Finish”）。

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

例如，上圖是一個7 x 3 的網格。有多少可能的路徑？

示例 1:

輸入: m = 3, n = 2

輸出: 3

解釋:

從左上角開始，總共有 3 條路徑可以到達右下角。

1. 向右 -> 向右 -> 向下

2. 向右 -> 向下 -> 向右

3. 向下 -> 向右 -> 向右

示例 2:

輸入: m = 7, n = 3

輸出: 28

提示：

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

動态規劃解決

注意這裡機器人隻能向下和向右移動，不能往其他方向移動，我們用dp[i][j]表示到坐标(i，j)這個格内有多少條不同的路徑，所以最終的答案就是求dp[m-1][n-1]。

因為隻能從上面或左邊走過來，所以遞推公式是

dp[i][j]=dp[i-1][j] dp[i][j-1]。dp[i-1][j]表示的是從上面走過來的路徑條數。

dp[i][j-1]表示的是從左邊走過來的路徑條數。

那麼邊界條件是什麼呢，如果Finish在第一行的任何位置都隻有一條路徑，同理Finish在第一列的任何位置也都隻有一條路徑，所以邊界條件是第一行和第一列都是1。我們已經找到了遞推公式，又找到了邊界條件，所以動态規劃代碼很容易寫出來，我們來看下

publicintuniquePaths(intm,intn){ int[][]dp=newint[m][n]; //第一列都是1 for(inti=0;i<m;i ){ dp[i][0]=1; } //第一行都是1 for(inti=0;i<n;i ){ dp[0][i]=1; } //這裡是遞推公式 for(inti=1;i<m;i ) for(intj=1;j<n;j ) dp[i][j]=dp[i-1][j] dp[i][j-1]; returndp[m-1][n-1]; }

動态規劃優化

我們看上面二維數組的遞推公式，當前坐标的值隻和左邊與上面的值有關，和其他的無關，這樣二維數組造成大量的空間浪費，所以我們可以把它改為一維數組。

publicintuniquePaths(intm,intn){ int[]dp=newint[m]; Arrays.fill(dp,1); for(intj=1;j<n;j ) for(inti=1;i<m;i ) dp[i] =dp[i-1]; returndp[m-1];8}

這裡的dp[i] =dp[i-1]；實際上就是dp[i]=dp[i] dp[i-1]，我們可以這樣理解，上面的網格我們是一行一行計算的，dp[i]也就是上面紅色的表示的是當前位置上面的值，dp[i-1]表示的是當前位置左邊的值。

遞歸方式

這題除了動态規劃以外，還可以把上面的動态規劃改為遞歸的方式

publicintuniquePaths(intm,intn){ returnuniquePathsHelper(1,1,m,n); } //第i行第j列到第m行第n列共有多少種路徑 publicintuniquePathsHelper(inti,intj,intm,intn){ //邊界條件的判斷 if(i>m||j>n) return0; if((i==m&&j==n)) return1; //從右邊走有多少條路徑 intright=uniquePathsHelper(i 1,j,m,n); //從下邊走有多少條路徑 intdown=uniquePathsHelper(i,j 1,m,n); //返回總的路徑 returnright down; }

代碼中有注釋，很容易理解，但其實這種效率很差，因為他包含了大量的重複計算，我們畫個圖來看一下。

我們看到上面圖中紅色，黑色，還有那種什麼顔色的都表示重複的計算，所以有一種方式就是把計算過的值使用一個map存儲起來，用的時候先查看是否計算過，如果計算過就直接拿來用，看下代碼

publicintuniquePaths(intm,intn){ returnuniquePathsHelper(1,1,m,n,newHashMap<>()); } publicintuniquePathsHelper(inti,intj,intm,intn,Map<String,Integer>map){ if(i>m||j>n) return0; if((i==m&&j==n)) return1; Stringkey=i "*" j; if(map.containsKey(key)) returnmap.get(key); intright=uniquePathsHelper(i 1,j,m,n,map); intdown=uniquePathsHelper(i,j 1,m,n,map); inttotla=right down; map.put(key,totla); returntotla; }

使用公式計算

我們要想到達終點，需要往下走n-1步，往右走m-1步，總共需要走n m-2步。他無論往右走還是往下走他的總的步數是不會變的。也就相當于總共要走n m-2步，往右走m-1步總共有多少種走法，很明顯這就是一個排列組合問題，公式如下

排列組合的計算公式如下

公式為(m n-2)! / [(m-1)! * (n-1)!]

代碼如下

publicintuniquePaths(intm,intn){ intN=n m-2; doubleres=1; for(inti=1;i<m;i ) res=res*(N-(m-1) i)/i; return(int)res; }

總結

這題使用動态規劃是最容易理解也是最容易解決的，當然後面的遞歸和公式計算也能解決。

如果喜歡這篇文章還可以關注微信公衆号“數據結構和算法”，查看更多的算法題

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部