---

DP专题5 不同路径||

原创 于 2023-09-15 12:02:32 发布 · 粉丝可见 · 119 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132896323

题目：

思路：

这道题，思路跟 不同路径| 思路一样，只是不同的是，有障碍物这一块，我们的二维dp数组初始化的时候，要注意，机器人只能向右和向下，所以初始化第一行和第一列的时候，当遇到障碍块的时候，就后面初始化就是 0，障碍块前面是1。而当障碍块在二维地图内的时候，我们dp该位置应该跳过该障碍块的方法，即dp[][]障碍块中应该是 0。

代码详解如下：

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
	// 获取地图大小
	int n = obstacleGrid.size();
	int m = obstacleGrid[0].size();
	
	// 定义dp数组
	int dp[200][200];
	memset(dp,0,sizeof dp);
	
	// dp数组初始化
	for(int i = 0;i < m;++i)
	{
		if(!obstacleGrid[0][i])
		{
			dp[0][i] = 1;
		}else break;
	}
	for(int i = 0;i < n;++i)
	{
		if(!obstacleGrid[i][0])
		{
			dp[i][0] = 1;
		}else break;
	}
	
	// 开始dp寻值
	for(int i = 1;i < n;++i)
	{
		for(int j = 1;j < m;++j)
		{
			// 如果遇到障碍块，则跳过dp
			if(obstacleGrid[i][j]) continue;
			
			// dp 递推公式
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	// 返回结果
	return dp[n - 1][m - 1];
}

最后提交：