leetcode63 不同路径二
题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
起点 | |||
障碍物 | |||
终点 |
如上图表格,需要找出从起点到终点的不同路径。
解题思路
利用动态规划的思路,对于终点来说,只能从上边和左边到达,可以得到状态转移公式
如果(i,j)位置上没有障碍物,则到达(i,j)位置的总路径就等于到达其左边(i,j-1)以及上方(i-1,j)的路径条数之和。
以4*4的格子说明,障碍物位置在(1,1)
1 | 1 | 1 | 1 |
1 | 炸弹0 | 1 | 2 |
1 | 1 | 2 | 4 |
1 | 2 | 4 | 8 |
需要注意的是,第一行和第一列的位置,如果没有障碍物存在的话,应该赋值为1,其他位置初始化0,状态转移过程如下
dp[i][j] = dp[i-1][j] dp[i][j-1];
i = 1-4
j =1:4
dp[1][1] = 0
dp[1][2] = 1 0 = 1
dp[1][3] = 1 1 = 2
dp[2][1] = 0 1 = 1
dp[2][2] = 1 1 = 2
dp[2][3] = 2 2 = 4
dp[3][1] = 1 1 = 2
dp[3][2] = 2 2 = 4
dp[3][3] = 4 4 = 8
最后输出到达最后一个位置的路径条数8
参考代码
-
class Solution {
-
public:
-
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
-
-
int n = obstacleGrid[0].size();
-
int m = obstacleGrid.size();
-
int dp[m][n];
-
for(int i=0;i<m;i )
-
for(int j=0;j<n;j )
-
dp[i][j]=0;
-
for (int i=0;i<m && obstacleGrid[i][0]==0;i ){
-
dp[i][0] = 1;
-
}
-
for (int i =0;i<n && obstacleGrid[0][i]==0;i ){
-
dp[0][i] = 1;
-
}
-
for (int i =1;i<m;i ){
-
for (int j=1;j<n;j ){
-
if (obstacleGrid[i][j]==0)
-
dp[i][j] = dp[i-1][j] dp[i][j-1];
-
}
-
}
-
return dp[m-1][n-1];
-
}
-
};
-
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfikjef
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01