Unique Paths

原題鏈接Unique Paths

計算從左上角有多少條不同的路徑可以到達右下角，移動方向只能是向右和向下。

對于每個位置，都有兩種移動的可能，即向右移動和向下移動。可以用深度優(yōu)先（dfs）解決，同時為了解決重復計算，可以用動態(tài)規(guī)劃的思想，記錄從dp[i][j]到達右下角有多少條不同的路徑。

除了深度優(yōu)先之外，可以用迭代法執(zhí)行動態(tài)規(guī)劃，這樣做可以減少dp的維度，只需要一維數(shù)組即可，不過要改變dp的含義，假設當前所在位置為(m, n)，那么dp[n]代表從左上角到達當前位置的不同路徑書，原因為

• 移動方向只能向右和向下，所以只要向下移動一行，就不能再返回上一行。這說明，對于行的記錄是可以忽略的。
• 只要遍歷每一行的每一列，不斷更新dp[n]直到到達右下角即可，假設當前在第m行的第n列，那么dp[n]表示從左上角開始移動可以有多少條不同的路徑達到第m行第n列
• 對于每個位置，它可以從上一行的當前列向下移動到達當前位置，也可以從當前行的上一列向右移動到達當前位置
• 所以dp[n] = dp[n] + dp[n - 1]，dp[n]代表從上一行的第n列到達右下角的不同路徑數(shù)，dp[n - 1]代表從當前行的第n-1列到達右下角的不同路徑數(shù)
• 直到遍歷到右下角，即遍歷了所有行所有列，那么dp[n]就代表從左上角到達右下角的不同路徑數(shù)

代碼如下

class Solution { public:int uniquePaths(int m, int n) {/* 到達第0行，第j列的路徑數(shù)只有1條 */vector<int> dp(n, 1);/* 這里直接忽略了第0行和第0列，原因是到達第0行和第0列的某個位置的路徑都只有1條 */for(int i = 1; i < m; ++i){for(int j = 1; j < n; ++j){/* dp[j]表示從左上角到達第i行第j列的不同路徑數(shù) *//* 當i為m-1，j為n-1時，就是從左上角到達右下角的不同路徑數(shù) */dp[j] = dp[j] + dp[j - 1];}}return dp[n - 1];} };

---

Unique Paths II

原題鏈接Unique Paths II

接著上面的問題，如果某些位置有障礙物，那么有多少條路徑可以到達右下角。
移動的過程中不能到達障礙物所在的位置。

方法和上面一樣，仍然有一維數(shù)組記錄到達某一列的不同路徑，不過需要判斷某個位置是否有障礙物，如果有，那么dp[n]為0，否則dp[n] = dp[n - 1] + dp[n]

另外，對于dp[0]要特殊處理，不能像上面一樣直接從第一行第一列開始，因為第0行第0列都可能存在障礙物導致dp[n[不是1而是0.

代碼如下

class Solution { public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid.empty())return 0;int m = obstacleGrid.size();int n = obstacleGrid[0].size();/* 如果起始位置和目標位置都有障礙物，那么就不可能到達 */if(n == 0 || obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)return 0;vector<int> dp(n);/* 到達開始位置的路徑為1 */dp[0] = 1;/* 到達第0行的某個位置的路徑，有障礙物的話后面就都是0，否則是1 */for(int i = 1; i < n; ++i)dp[i] = (obstacleGrid[0][i] == 1) ? 0 : dp[i - 1];for(int i = 1; i < m; ++i){/* 如果當前行的第0列是障礙物，那么到達當前行的第0列的路徑數(shù)為0 */if(obstacleGrid[i][0] == 1)dp[0] = 0;for(int j = 1; j < n; ++j){dp[j] = obstacleGrid[i][j] == 1 ? 0 : dp[j] + dp[j - 1];}}return dp[n - 1];} };

---

原題鏈接Minimum Path Sum

和上面的題一樣，只是這回要求是找到路徑長度最短的那一條，路徑長度是路徑上所有數(shù)字的和

仍然采用迭代法的動態(tài)規(guī)劃，不過要改變dp的含義，即dp[n]表示從左上角到達當前位置的最小路徑長，而不在是不同路徑數(shù)

另外，第一行和第一列不再單純的是1，而是數(shù)字累加，代表路徑長
代碼如下

class Solution { public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();if(m == 0) { return 0; }int n = grid[0].size();if(n == 0) { return 0; }vector<int> dp(n, 0);dp[0] = grid[0][0];/* 這里第一行的路徑長要累加 */for(int i = 1; i < n; ++i)dp[i] = dp[i - 1] + grid[0][i];for(int i = 1; i < m; ++i){/* 第一列也要累加 */dp[0] += grid[i][0];for(int j = 1; j < n; ++j){/* 不再是相加，而是找到較小的那個 */dp[j] = std::min(dp[j], dp[j - 1]) + grid[i][j];}}return dp[n - 1];} };

上面三道題主要利用動態(tài)規(guī)劃的思想，另外通過迭代法簡化動態(tài)規(guī)劃數(shù)組的維度。

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----计算从二维数组的左上角到达右下角的所有路径数及最短的那条，如果存在障碍物时又是多少的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。