LeetCode_动态规划_中等_63.不同路径 II

比眉伴天荒 2023-10-06 19:01 15阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。  
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。  
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

![在这里插入图片描述][c5d20ca031e845189a6706f20a0102c3.png]  
网格中的障碍物和空位置分别用 1 和 0 来表示。

**示例 1：**

![在这里插入图片描述][ce3cd5f927e44d2b8091b84d9e5664e5.png]  
输入：obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]  
输出：2  
解释：  
3x3 网格的正中间有一个障碍物。  
从左上角到右下角一共有 2 条不同的路径：  
1.向右 -> 向右 -> 向下 -> 向下  
2.向下 -> 向下 -> 向右 -> 向右

**示例 2：**

![在这里插入图片描述][1716377fd2574b6892ccd1cd7f075219.png]  
输入：obstacleGrid = \[\[0,1\],\[0,0\]\]  
输出：1

**提示：**  
m == obstacleGrid.length  
n == obstacleGrid\[i\].length  
1 <= m, n <= 100  
obstacleGrid\[i\]\[j\] 为 0 或 1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/unique-paths-ii

## 2.思路 ##

（1）动态规划  
该思路与[LeetCode62.不同路径][LeetCode62.]这题的思路 1 类似，只不过本题在那题的基础上，需要添加对位置 (i, j) 是否有障碍物的判断。**设 dp\[i\]\[j\] 表示从起点 (1, 1) 到终点 (i, j) 不同的路径总数，且需要躲避网格中的障碍物(1 ≤ i ≤ m, 1 ≤ j ≤ n)**，若 (i, j) 处有障碍物，则说明从起点不能到达该点，即设置 dp\[i\]\[j\] = 0；若 (i, j) 处没有障碍物，则像之前一样按照状态转移方程 dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\] 计算即可。

相关题目：  
[LeetCode\_动态规划\_中等\_62.不同路径][LeetCode62.]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
    	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
    	    int m = obstacleGrid.length;
    	    int n = obstacleGrid[0].length;
    	    //dp[i][j]: 表示从起点 (1, 1) 到终点 (i, j) 不同的路径总数，且若 (i,j) 处有障碍物，则设置 dp[i][j] = 0
    	    int[][] dp = new int[m + 1][n + 1];
    	    //设边界值 dp[0][1] = 1(或 dp[1][0] = 1)，这样便于得出 dp[1][1] = 1，然后以此为起点开始计算
    	    dp[0][1] = 1;
    	    for (int i = 1; i <= m; i++) {
        
    	        for (int j = 1; j <= n; j++) {
        
    	            //判断该位置是否有障碍物
    	            if (obstacleGrid[i - 1][j - 1] == 0) {
        
    	                //状态转移方程
    	                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    	            } else {
        
    	                //该位置有障碍物，则说明该位置不可达，即设置 dp[i][j] = 0
    	                dp[i][j] = 0;
    	            }        
    	        }
    	    }
    	    return dp[m][n];
    	}
    }

[c5d20ca031e845189a6706f20a0102c3.png]: https://img-blog.csdnimg.cn/c5d20ca031e845189a6706f20a0102c3.png
[ce3cd5f927e44d2b8091b84d9e5664e5.png]: https://img-blog.csdnimg.cn/ce3cd5f927e44d2b8091b84d9e5664e5.png
[1716377fd2574b6892ccd1cd7f075219.png]: https://img-blog.csdnimg.cn/1716377fd2574b6892ccd1cd7f075219.png
[LeetCode62.]: https://blog.csdn.net/weixin_43004044/article/details/119831861