Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space are marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
这是自己能独立做出来的DP类第二个题^^.
这题和上一题状体转移公式几乎一样．区别就是在 obstacles 的处理上．下面是方法：
核心思路：
- 先搞定第 0 行和第 0 列;
- 第 0 行和第 0 列若有障碍, 则该处及后面的都 = 0;
- 非０行、列，则按公式填写 bp matrix, 从 row=1, col=1开始. 若遇 obstacle, 该处设置为0.
注意处理 special case：if(A[0][0] = 1) return 0;
为了搞起来方便，申请了一个 m*n 的二维数组．但似乎只申请 n 维的一维数组就足够了．先不管啦．
自己思路，自个媳妇:
\(O(m*n)\) time, \(O(m*n)\) extra space.
// 思路：
// 1. 先搞定第 0 行和第 0 列;
// 2. 第 0 行和第 0 列若有障碍, 则该处及后面的都 = 0;
// 3. 非０行、列，则按公式填写 bp matrix, 从 row=1, col=1开始.
// 若遇 obstacle, 该处设置为0.
int uniquePathsWithObstacles(vector<vector<int>>& A) {
const int m = A.size(), n = A[0].size();
// special case
if (m == 0 || A[0][0] == 1)
return 0;
vector<vector<int>> dp(m);
// dp[m*n] initializaion
for (int i = 0; i < m; i++)
dp[i].resize(n);
// 初始化bp的行
for (int j = 0; j < n; j++) {
if (A[0][j] == 0)
dp[0][j] = 1;
else { // point A[0,j] is an obstacle
dp[0][j] = 0;
break; // 第0行若有障碍,则该处及后面的都 = 0
}
}
// 初始化bp的列
for (int i = 1; i < m; i++) {
if (A[i][0] == 0)
dp[i][0] = 1;
else { // point A[i,0] is an obstacle
dp[i][0] = 0;
break; // 第0列若有障碍,则该处及后面的都 = 0
}
}
// 按公式填写bp matrix, 从 row=1, col=1开始
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (A[i][j] == 1)
dp[i][j] == 0; //障碍处设置为0
// dp的状态转移公式
else if (A[i][j] == 0)
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
随机推荐
-
2018年Web前端自学路线
本文最初发表于博客园,并在GitHub上持续更新前端的系列文章.欢迎在GitHub上关注我,一起入门和进阶前端. 以下是正文. Web前端入门的自学路线 新手入门前端,需要学习的基础内容有很多,如下. ...
-
ssh整合之一spring的单独运行环境
这是本人第一次写博客,不足之处,还希望各位园友指出,在此先谢谢各位了! 先说我们的这三大框架,即struts,spring,hibernate,我们要进行整合的话,第一步是先单独搭建我们的Spring ...
-
JQuery Layer的应用实例
参考以上链接:https://blog.****.net/zlj_blog/article/details/24994799 sql面试题:https://www.cnblogs.com/qixuej ...
-
spark2.1：flatMap的用法
代码示例: val sample_data_combine_result=List( (0,(List(FitModel(4022,1447.92,-8.38983306721434,2.0)),1) ...
-
Spark：性能调优
来自:http://blog.****.net/u012102306/article/details/51637366 资源参数调优 了解完了Spark作业运行的基本原理之后,对资源相关的参数就容易理 ...
-
基于DFS的拓扑排序
传送门:Kahn算法拓扑排序 摘录一段*上的伪码: L ← Empty list that will contain the sorted nodes S ← Set of all nodes ...
-
Cassanfra、Hbase和MongoDB的选取
HBase比较中庸些,适合各种场景: Cassandra适合读写分离的场景,写入场景使用Cassandra,比如插入操作日志,或领域事件日志的写入: 而MongoDB适合做读写分离场景中的读取场景. ...
-
springboot测试、打包、部署
本文使用<springboot集成mybatis(一)>项目,依次介绍springboot测试.打包.部署. 大多数朋友是做后端的,也就是为其他系统或者前端UI提供Rest API服务. ...
-
SpringMVC 自定义类型转换器
先准备一个JavaBean(Employee) 一个Handler(SpringMVCTest) 一个converters(EmployeeConverter) 要实现的输入一个字符串转换成一个emp ...
-
python day two,while
一.运算符号 算数运算符:+ .-.*././/(取整除).%(去余).** 比较运算符:>.< .>=.<=.== 赋值运算符:=.+=.-=./=.%=.**= 逻辑预算符 ...