Leetcode - 不同路径 II(DP)
发布日期:2021-07-01 00:15:03
浏览次数:2
分类:技术文章
本文共 833 字,大约阅读时间需要 2 分钟。
题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1
和 0
来表示。
说明:m 和 n 的值均不超过 100。
示例 1:
输入:[ [0,0,0], [0,1,0], [0,0,0]]输出: 2解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径:1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右
解题思路
这个和上次的不同路径()是差不多的,只要判断一下当前位置是否有障碍物,如果有那么就为0.
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) { int maxV[110] = {0}; maxV[0] = 1; for (int i = 0; i < obstacleGridRowSize; i++) { if (obstacleGrid[i][0]) maxV[0] = 0; for (int j = 1; j < obstacleGridColSize; j++) { if (obstacleGrid[i][j]) maxV[j] = 0; else maxV[j] = maxV[j - 1] + maxV[j]; } } return maxV[obstacleGridColSize - 1];}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84299224 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月22日 16时23分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
攻防世界web进阶区web2详解
2019-04-30
xss-labs详解(上)1-10
2019-04-30
xss-labs详解(下)11-20
2019-04-30
攻防世界web进阶区ics-04详解
2019-04-30
sql注入总结学习
2019-04-30
Python 之 histogram直方图
2019-04-30
Python实现决策树 Desision Tree & 可视化
2019-04-30
决策树 Decision tree
2019-04-30
MATLAB与CUDA
2019-04-30
Linux png转jpg (convert命令)
2019-04-30
Ubuntu更新后终端中字体的颜色全是白色
2019-04-30
vscode git
2019-04-30
基于MATLAB的二进制数字调制与解调信号的仿真——2PSK
2019-04-30
基于MATLAB的模拟调制信号与解调的仿真——DSB
2019-04-30
HDU - 1166 敌兵布阵 (树状数组模板题/线段树模板题)
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 675A Infinite Sequence(简单数论 细节)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30