`
cozilla
  • 浏览: 91909 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Unique Paths II

 
阅读更多
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];
    }
};

 

分享到:
评论

相关推荐

    js-leetcode题解之63-unique-paths-ii.js

    javascript js_leetcode题解之63-unique-paths-ii.js

    js-leetcode题解之62-unique-paths.js

    javascript js_leetcode题解之62-unique-paths.js

    pcw0118#ZXBlog#LeetCode-62.Unique Paths(不同的路径数量)(简单dp)1

    1、记忆化 2、二维dp 3、滚动优化

    Leetcode book刷题必备

    44. Unique Paths II:与 Unique Paths 类似,但是考虑网格中障碍物的处理。 45. Maximum Sum Subarray:找出一个数字序列中和最大的连续子序列。 46. Maximum Product Subarray:找出一个数字序列中乘积最大的连续...

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    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答案-leetcode:leetcode

    II mod之后,可能数学公式就不能简单地给出答案了。但对我来说,其实和前一题没区别。动态规划处理这种问题,早就是牛刀杀鸡了。。 Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 ...

    _leetcode-python.pdf

    - Unique Paths / Unique Paths II: 前者计算从矩阵的左上角到右下角的路径数量;后者则考虑了障碍物。 - Minimum Path Sum: 在一个m×n的网格中,找到从左上角到右下角的路径,使得路径上的数字总和最小。 - Plus ...

    Leetcode题目+解析+思路+答案.pdf

    - **Unique Paths**:计算机器人到达目标位置的唯一路径数。 - **Maximum Subarray**:寻找数组中的最大子数组和。 - **Climbing Stairs**:模拟爬楼梯,每次可以爬1阶或2阶。 5. **回溯(Backtracking)**: -...

    leetcode java

    - "不同路径"(Unique Paths)和"不同路径 II"(Unique Paths II)同样是关于路径计算的动态规划问题。 **二分搜索(Binary Search)** 二分搜索算法适用于有序数组或列表的快速查找问题。 - "搜索插入位置"...

    LeetCode leetcode部分题解答代码实现

    * Unique Paths:给定一个矩形,返回从左上角到右下角的路径数量。这个题目需要使用动态规划的思想,将矩形分解成更小的子矩形,并统计路径数量。 * Maximum Subarray:给定一个数组,返回数组中的最大子数组和。这...

    leetcode1477-coding-for-fun:编码乐趣

    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。 ...

    leetcode常见的100热点算法题

    例如,"Unique Paths"(不同路径)和"House Robber"(打家劫舍)都是经典的动态规划题目。 3. **回溯与深度优先搜索**:这类算法通常用于解决组合优化问题和图遍历问题。例如,"N-Queens"(八皇后问题)和"Word ...

    lrucacheleetcode-LeetcodeSolution:Leetcode刷题的分类和答案记录

    63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的子串 49.组字谜...

    python-leetcode面试题解之第62题不同路径-题解.zip

    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-Leetcode:LeetcodeAnswer-Java

    扩展矩阵leetcode ...uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆

    leetcode棋盘-Algorithms:通用算法实现

    unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...

    leetcode63-leetcode:我在2015年的leetcode解决方案

    【描述】"leetcode63" 提到的这个问题,全称为“Unique Paths II”,是LeetCode中的一个经典问题。在这个问题中,任务是计算一个机器人从左上角到达右下角有多少种不同的路径。与标准的“Unique Paths”问题相比,...

    leetcode官方50题算法详解

    2. **不同路径(Unique Paths)**:给定一个机器人位于一个m x n网格的左上角,求出到达网格右下角的不同路径数量。 ### 二分查找 二分查找是解决有序数组或列表中特定问题的有效算法。 1. **搜索插入位置(Search...

Global site tag (gtag.js) - Google Analytics