Unique Paths II
来自 <https://leetcode.com/problems/unique-paths-ii/>
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 is 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.
题目解读:
上接题目“Unique Paths”
现在考虑如果某个方格内添加上障碍物,那一共有多少种唯一路径?在数组中的障碍物和空白分别用1和0表示。
例如:
在一个3*3的方格中,有一个障碍物,表示如下
[
[0,0,0],
[0,1,0],
[0,0,0]
]
总共的唯一路径数为2.
注:m 和n的最大值为100.
解析:
这个题和Unique Paths一样,都属于动态规划的问题,但此问题中添加了障碍物,到达障碍物下端down或右端right的路径数为down左端的路径数和right上端的路径数。如果把障碍物所在的数组元素值设为0,则就能变成河unique paths的问题相同。
Java代码:
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { //行数 int rows = obstacleGrid.length; //列数 int cols = obstacleGrid[0].length; //如果起始位置被堵死,则没有到达目的地的路径 if(obstacleGrid[0][0]==1) return 0; int value = 1; for(int i=0; i<cols; i++) { if(obstacleGrid[0][i] == 1) value = 0; obstacleGrid[0][i] = value; } //如果第一行或第一列的某个数组元素为1,则到达其后续的行和列中的路径为0种 value =1; for(int i=1; i<rows; i++) { if(obstacleGrid[i][0] == 1) value = 0; obstacleGrid[i][0] = value; } //到达空格i,j的路径等于到达其上方和其左方路径之和 for(int i=1; i<rows; i++) { for(int j=1; j<cols; j++) { if(obstacleGrid[i][j] != 1) obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]; else obstacleGrid[i][j]=0; } } return obstacleGrid[rows-1][cols-1]; } }
算法性能:
相关推荐
1、记忆化 2、二维dp 3、滚动优化
扩展矩阵leetcode ...uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...
II mod之后,可能数学公式就不能简单地给出答案了。但对我来说,其实和前一题没区别。动态规划处理这种问题,早就是牛刀杀鸡了。。 Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 ...
62.unique-paths.cpp [TODO] 5. 最长回文子串.cpp 第 3 天: [TODO] 96.unique-binary-search-trees.cpp [TODO] 70. 爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 ...
unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...
63.Unique Paths II, 64.Minimum Path Sum 2017/03/09 70.Climbing Stairs, 198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 (Lintcode)92....
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 ...47/46....54/59....63/62.Unique Paths 2 64.最小路径和
uniquePaths = function(m, n) { let dp = new Array(m).fill(0).map(() => new Array(n)); // dp[r][c] represents the number of possible paths from row = 0, col = 0 to row = r, col = c for (let row = 0; ...
Unique Paths 这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见...
63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的子串 49.组字谜...
leetcode正方体收藏TakeUforward-SDE_180 要了解整个列表和其他内容,如项目、简历、如何进行面试……观看整个视频: 在以下位置找到展示位置系列: 第一天:(数组) 在 N+1 整数数组中查找重复项。 (描述中的问题...
Unique Paths II N-Queens N-Queens II Restore IP Addresses Combination Sum Combination Sum II Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump...