lintcode-115-不同的路径 II
2024-08-28 17:13:17
115-不同的路径 II
"不同的路径" 的跟进问题：
现在考虑网格中有障碍物，那样将会有多少条不同的路径？
网格中的障碍和空位置分别用 1 和 0 来表示。注意事项
m 和 n 均不超过100
样例
如下所示在3x3的网格中有一个障碍物：
[
[0,0,0],
[0,1,0],
[0,0,0]
]
一共有2条不同的路径从左上角到右下角。标签
动态规划 数组
思路
延续lintcode-114-不同的路径的思路，在遇到障碍时，dp[i][j] = 0
code
class Solution {
public:
/**
* @param obstacleGrid: A list of lists of integers
* @return: An integer
*/
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
// write your code here
if(obstacleGrid.size() <= 0 || obstacleGrid[0].size() <= 0) {
return 0;
}
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int> > dp(m, vector<int>(n, INT_MAX));
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
continue;
}
if(i == 0 && j == 0) {
dp[i][j] = 1;
}
else if(i == 0 && j > 0) {
dp[i][j] = dp[i][j-1];
}
else if(i > 0 && j == 0) {
dp[i][j] = dp[i-1][j];
}
else if(i > 0 && j > 0) {
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
}
return dp[m-1][n-1];
}
};
最新文章
- Ruby 里的 %Q, %q, %W, %w, %x, %r, %s, %i (译)转
- yii2.0 Cache缓存
- phalcon: router规则与解析，已经生成router的链接地址
- MVC设计模式(持续更新中)
- Redis的Order Set操作
- Hat’s Words hdu-1247
- Eclipse无法打开“Failed to load the JNI shared library”
- MHA环境的搭建
- SqlConnection类
- c#将输入的人民币数字金额转换成小写
- UIPickView之自定义生日键盘和城市键盘
- iOS苹果官方Demo合集
- Ubuntu 16.04 安装和使用QQ最简洁的方式
- 初探奥尔良(Orleans)
- 《前端之路》之 初识 JavaScript
- Best Free Hacking E-Books 2017 In PDF Format
- NVMe协议1.3c（一） 概述
- Scrum Meeting NO.9
- Asp.net Daily Build by MsBuild
- 2019.01.10 bzoj1095: [ZJOI2007]Hide 捉迷藏（动态点分治）