`

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.

 

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];
    }
}

 

 

分享到:
评论

相关推荐

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

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

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

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

    leetcode分类-LeetCode:力码

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

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

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

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

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

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

    leetcode530-Leetcode:新的开始

    leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...

    leetcode叫数-Leetcode_JS:leetcode编程题,javascript版本

    Unique Paths 这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见...

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

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

    leetcode正方体堆叠-TakeUforward-SDE_180:TakeUforward-SDE_180

    leetcode正方体收藏TakeUforward-...Unique Paths Reverse Pairs (Leetcode) 从 GFG 中通过拼图(自行搜索) Day4: (Hashing) 2 Sum 问题 4 Sum 问题 Longest Consecutive Sequence Longest Subarray with 0 sum 给定

    leetcode算法题主函数如何写-visual-your-algo:网站暂停升级中

    uniquePaths = function(m, n) { let dp = new Array(m).fill(0).map(() =&gt; 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; ...

    cpp-算法精粹

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

Global site tag (gtag.js) - Google Analytics