LeetCode刷题实战63：不同路径 II
共 1541字，需浏览 4分钟
·
2020-10-14 04:11
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 不同路径II，我们先来看题面：
https://leetcode-cn.com/problems/unique-paths-ii/
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
题意
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
解题
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m=obstacleGrid.length;
int n=obstacleGrid[0].length;
if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1){
return 0;
}
int dp[][] = new int[m + 1][n + 1];
dp[0][1]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if (obstacleGrid[i - 1][j - 1] == 0)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
}
上期推文：