leetcode63. 不同路徑 II
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/unique-paths-ii
題目描述
一個機(jī)器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。
示例1:
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網(wǎng)格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例2:
輸入：obstacleGrid = [[0,1],[0,0]]
輸出：1
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 為 0 或 1
暴力遞歸
這題是leetcode62. 不同路徑 的拓展版.加了障礙物,解題思路是一樣的,只是要加下障礙物的判斷.
還是向下和向右兩個方向的選擇,兩種情況的和就是所有的路線數(shù).
代碼演示
/**
* 主方法
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//如果右下角是障礙物,怎么都過不去,直接返回0
if(obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1){
return 0;
}
//開始遞歸
return process(obstacleGrid,0,0);
}
/**
* 暴力遞歸
* i 和 j 描述當(dāng)前在的位置
*/
public int process(int[][]obstacleGrid,int i,int j){
//base case 來到最后一個位置,前面路線有效,返回1
if(i == obstacleGrid.length - 1 && j == obstacleGrid[0].length - 1 ){
return 1;
}
//越界,路線無效 返回0
if(i >= obstacleGrid.length || j >= obstacleGrid[0].length){
return 0;
}
// 碰到障礙物,無效返回0
if(obstacleGrid[i][j] == 1){
return 0;
}
//x向下和向右兩種情況
int down = process(obstacleGrid,i + 1,j);
int right = process(obstacleGrid,i,j + 1);
//兩種情況累加就是所有的路線
return down + right;
}
動態(tài)規(guī)劃
從暴力遞歸中可以得知,(i,j) 位置依賴 (i+1,j)和(i,j+1)兩個位置,所以可以輕松得到狀態(tài)轉(zhuǎn)移方程是:
f(i,j) = f(i+1,j) + f(i,j+1;
但這里有一些需要注意的地方,就是障礙物的處理,和dp表的初始化,我們以圖為例:
上面圖代表要走的網(wǎng)格,我只填寫了最后一行和一列其他位置沒有標(biāo)注,因為現(xiàn)在只討論最后一行和一列的情況.
最后一行為例,三角符號標(biāo)注的位置是最后一次出現(xiàn)的障礙物,在這個障礙物之前的最后一行位置,都無法到最后位置了,所以之前的位置在dp 表中要初始化為0,之后的可以初始化為1,
最后一列也是同樣情況:
下面看下代碼中如何處理;
代碼演示
/**
* 動態(tài)規(guī)劃
* @param obstacleGrid
* @return
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
//最有下角如果是障礙物,就無法過去,返回 0
if (obstacleGrid[n - 1][m - 1] == 1) {
return 0;
}
//動態(tài)規(guī)劃表
int[][]dp = new int[n][m];
//來標(biāo)記最后一行最后一次出現(xiàn)障礙物的位置
int flagN = -1;
//來標(biāo)記最后一列最后一次出現(xiàn)障礙物的位置
int flagM = -1;
for (int i = m - 1; i >= 0;i--){
if(obstacleGrid[n - 1][i] == 1){
flagN = i;
break;
}
}
//最后一個障礙物之后的位置初始化為1
for (int i = flagN + 1; i < m;i++){
dp[n - 1][i] = 1;
}
//標(biāo)記最后一列最后一次出現(xiàn)障礙物的位置.
for (int j = n - 1; j >= 0;j--){
if(obstacleGrid[j][m - 1] == 1){
flagM = j;
break;
}
}
//最后一個障礙物之后的位置初始化為1
for (int j = flagM + 1; j < n;j++){
dp[j][m - 1] = 1;
}
for (int i = n - 2;i >= 0;i--){
for (int j = m - 2;j >= 0;j--){
//當(dāng)前位置本身是障礙物 即為0
if(obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}else{
//z狀態(tài)轉(zhuǎn)移方程
dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
}
}
}
return dp[0][0];
}
動態(tài)規(guī)劃空間壓縮
/**
* 動態(tài)規(guī)劃 + 空間壓縮
* @param obstacleGrid
* @return
*/
public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
if (obstacleGrid[n - 1][m - 1] == 1) {
return 0;
}
int[]dp = new int[m];
int flagN = -1;
for (int i = m - 1; i >= 0;i--){
if(obstacleGrid[n - 1][i] == 1){
flagN = i;
break;
}
}
for (int i = flagN + 1; i < m;i++){
dp[i] = 1;
}
int flagM = -1;
for (int j = n - 1; j >= 0;j--){
if(obstacleGrid[j][m - 1] == 1){
flagM = j;
break;
}
}
for (int i = n - 2;i >= 0;i--){
dp[m - 1] = i > flagM ? 1 : 0;
for (int j = m - 2;j >= 0;j--){
if(obstacleGrid[i][j] == 1){
dp[j] = 0;
}else{
dp[j] = dp[j] + dp[j + 1];
}
}
}
return dp[0];
}
動態(tài)規(guī)劃專題
leetcode62. 不同路徑
leetcode877. 石子游戲
leetcode64. 最小路徑和
leetcode416. 分割等和子集
leetcode354. 俄羅斯套娃信封問題
leetcode300. 最長遞增子序列文章來源：http://www.zghlxwxcb.cn/news/detail-503367.html
leetcode337. 打家劫舍 III文章來源地址http://www.zghlxwxcb.cn/news/detail-503367.html
到了這里，關(guān)于leetcode63. 不同路徑 II(動態(tài)規(guī)劃-java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
