Unique Paths IIMar 29 '124573 / 11497
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.
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { auto &a = obstacleGrid; int n = a.size(); if (n == 0) return 0; int m = a[0].size(); vector<int> res(m, 0); if (a[0][0] == 0) res[0] = 1; for (int i = 1; i < m; i++) { if (res[i-1] > 0 && a[0][i] == 0) res[i] = res[i-1]; } for (int i = 1; i < n; i++) { if (res[0] == 0 || a[i][0] == 1) res[0] = 0; for (int j = 1; j < m; j++) { if (a[i][j] == 1) res[j] = 0; else res[j] += res[j-1]; } } return res[m-1]; } };
相关推荐
javascript js_leetcode题解之63-unique-paths-ii.js
javascript js_leetcode题解之62-unique-paths.js
1、记忆化 2、二维dp 3、滚动优化
44. Unique Paths II:与 Unique Paths 类似,但是考虑网格中障碍物的处理。 45. Maximum Sum Subarray:找出一个数字序列中和最大的连续子序列。 46. Maximum Product Subarray:找出一个数字序列中乘积最大的连续...
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 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 ...
- Unique Paths / Unique Paths II: 前者计算从矩阵的左上角到右下角的路径数量;后者则考虑了障碍物。 - Minimum Path Sum: 在一个m×n的网格中,找到从左上角到右下角的路径,使得路径上的数字总和最小。 - Plus ...
- **Unique Paths**:计算机器人到达目标位置的唯一路径数。 - **Maximum Subarray**:寻找数组中的最大子数组和。 - **Climbing Stairs**:模拟爬楼梯,每次可以爬1阶或2阶。 5. **回溯(Backtracking)**: -...
- "不同路径"(Unique Paths)和"不同路径 II"(Unique Paths II)同样是关于路径计算的动态规划问题。 **二分搜索(Binary Search)** 二分搜索算法适用于有序数组或列表的快速查找问题。 - "搜索插入位置"...
* Unique Paths:给定一个矩形,返回从左上角到右下角的路径数量。这个题目需要使用动态规划的思想,将矩形分解成更小的子矩形,并统计路径数量。 * Maximum Subarray:给定一个数组,返回数组中的最大子数组和。这...
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"(不同路径)和"House Robber"(打家劫舍)都是经典的动态规划题目。 3. **回溯与深度优先搜索**:这类算法通常用于解决组合优化问题和图遍历问题。例如,"N-Queens"(八皇后问题)和"Word ...
63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的子串 49.组字谜...
def uniquePaths(m, n): dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m - 1][n - 1] ``...
扩展矩阵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...
【描述】"leetcode63" 提到的这个问题,全称为“Unique Paths II”,是LeetCode中的一个经典问题。在这个问题中,任务是计算一个机器人从左上角到达右下角有多少种不同的路径。与标准的“Unique Paths”问题相比,...
2. **不同路径(Unique Paths)**:给定一个机器人位于一个m x n网格的左上角,求出到达网格右下角的不同路径数量。 ### 二分查找 二分查找是解决有序数组或列表中特定问题的有效算法。 1. **搜索插入位置(Search...