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.
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { if (obstacleGrid == null) return 0; int m = obstacleGrid.length; int n = obstacleGrid[0].length; if (m == 0 || n == 0 || obstacleGrid[0][0] == 1) return 0; int[][] dp = new int[m][n]; dp[0][0] = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (obstacleGrid[i][j] == 1) dp[i][j] = 0; else if (i > 0 && j > 0) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } else if (i > 0) { dp[i][j] = dp[i - 1][j]; } else if (j > 0) { dp[i][j] = dp[i][j - 1]; } } } return dp[m - 1][n - 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...
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。 ...
II mod之后,可能数学公式就不能简单地给出答案了。但对我来说,其实和前一题没区别。动态规划处理这种问题,早就是牛刀杀鸡了。。 Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 ...
unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...
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/...
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...
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-...Unique Paths Reverse Pairs (Leetcode) 从 GFG 中通过拼图(自行搜索) Day4: (Hashing) 2 Sum 问题 4 Sum 问题 Longest Consecutive Sequence Longest Subarray with 0 sum 给定
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 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...