leetcode63-不同路径II

原题

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

leetcode63-不同路径II

网格中的障碍物和空位置分别用 10 来表示。

说明: m 和 n 的值均不超过 100。

示例1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0] ] 输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解法

思想

leetcode62-不同路径类似,可以使用递归+记忆,每个位置的路径数为右边位置的路径数和下面位置的路径数之和,有障碍的点的路径数为0。

代码

class Solution {
    int[][] grid;
    Integer[][] paths;
    int length;
    int height;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        grid = obstacleGrid;
        if(grid.length==0||grid[0].length==0) return 0;
        height = grid.length;
        length = grid[0].length;
        paths = new Integer[height][length];
        return getPaths(0,0);
    }
    public int getPaths(int m,int n){
        if(m==height||n==length) return 0;
        if(grid[m][n]==1) return 0;
        if(m == height-1 && n==length-1) return 1; 
        if(paths[m][n] != null) return paths[m][n];
        int ans = getPaths(m+1,n)+getPaths(m,n+1);
        paths[m][n] = ans;
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode63-%e4%b8%8d%e5%90%8c%e8%b7%af%e5%be%84ii/

发表评论

电子邮件地址不会被公开。