新博文地址:[leetcode]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.
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几乎木有区别,遇到obstacleGrid[i][j] == 1的元素,即将path设为0即可。需要注意的是,在第一行和第一列,即obstacleGrid[i][0] == 1&& obstacleGrid[0][i] == 1后面的元素path全部置0
public int uniquePathsWithObstacles(int[][] obstacleGrid) { if(obstacleGrid == null || obstacleGrid.length == 0){ return 0; } int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] path = new int[m][n]; for(int i = 0; i < n; i++){ if(obstacleGrid[0][i] == 0){ path[0][i] = 1; }else{ path[0][i] = 0; break; } } for(int i = 0; i < m; i++){ if(obstacleGrid[i][0] == 0){ path[i][0] = 1; }else{ path[i][0] = 0; break; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if(obstacleGrid[i][j] == 0){ path[i][j] = path[i-1][j] + path[i][j-1]; } } } return path[m-1][n-1]; }
相关推荐
1、记忆化 2、二维dp 3、滚动优化
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
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。 ...
63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的子串 49.组字谜...
扩展矩阵leetcode ...uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...
Unique Paths 这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见...
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...
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; ...
leetcode正方体收藏TakeUforward-...Unique Paths Reverse Pairs (Leetcode) 从 GFG 中通过拼图(自行搜索) Day4: (Hashing) 2 Sum 问题 4 Sum 问题 Longest Consecutive Sequence Longest Subarray with 0 sum 给定
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...