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];
}
随机推荐
-
如何解决MSI类型的Sharepoint Server2016 安装即点即用的office 2016 plus问题
前提 在sharepoint server 2016安装office 2016 plus提示如下错误: 解决方法 Ø 概念 1. 即点和即用的概念:即点即用是一种通过 Internet 安装和更新 O ...
-
javascript语言理解
1.使用jquery remove,无法remove自身标签; 使用标签
-
html5用到的js
1.Zepto.js 是专门为现代智能手机浏览器退出的 Javascript 框架, 拥有和jQuery相似的语法, 但是和jQuery相比下来, 他有很多优点, 大小方面 , 压缩后的 zepto. ...
-
php中使用while遍历二维数组的方法
<?php $contact=array( 'gao'=>array('ID'=>1,'name'=>'高某','company'=>'A公司','addr'=>' ...
-
意外作出了一个javascript的服务器,可以通过js调用并执行任何java(包括 所有java 内核基本库)及C#类库,并最终由 C# 执行你提交的javascript代码! 不敢藏私,特与大家分
最近研发BDC 云开发部署平台的数据路由及服务管理器意外作出了一个javascript的服务器,可以通过js调用并执行任何java(包括 所有java 内核基本库)及C#类库,并最终由 C# 执行你提 ...
-
Eclipse系列： Eclipse设置Tomcat启动超时时间
在eclipse的workspace目录下,找到如下文件: .metadata\.plugins\org.eclipse.wst.server.core\servers.xml 如下图所示,然后将它修 ...
-
So easy Webservice 4.Java方式访问WebService（使用jdk1.6以上 wsimport命令）
1.选中要调用的服务单击”服务说明” 2.获取wsdl文件.使用JDK1.6以上的版本的wsimport命令 a) 例如选中:http://webservice.webxml.com.cn/WebSe ...
-
【Maven实战】依赖的聚合和版本管理
1.在之前的文章中,我们已经建立了四个Maven项目,但是此时如果我们要对这四个项目进行编译打包时,必须一个一个的进行执行命令,而聚合就是指只要我们在其中一个项目中编写一些代码,则在进行此项目的编译和 ...
-
在右键添加Cmder here选项，添加启动Cmder的快捷键
右键菜单添加“Cmder here” 打开cmder,在其中输入: cmder /register user 或 cmder /register all 即可 设置启动cmder的快捷键 右键 C ...
-
ueditor取消文本编辑器的自动拉伸高度、宽度。
1.首先引入富文本编辑器 <script type="text/javascript" src="<%=basePath%>js/ueditor/ued ...