動態規划算法求最小路徑（動態規劃求不同路徑）

2023-08-06 17:30:48

問題描述

一個機器人位於一個 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];//第一列都是1for(inti=0;i<m;i ){dp[i][0]=1;}//第一行都是1for(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;im||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,Mapmap){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;}
總結
這題使用動態規劃是最容易理解也是最容易解決的，當然後面的遞歸和公式計算也能解決。
如果喜歡這篇文章還可以關注微信公眾號「數據結構和算法」，查看更多的算法題
,