63. 不同路径 II

难度中等389收藏分享切换为英文关注反馈
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
算法练习第三十题 - 图1
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         // 动态规划思路
  4.         // 1.首先每一个格子的可到达的方式累加，即动态规划方程为：dp[i][j] = dp[i-1][j]+dp[i][j-1]
  5.         // 2.当某一个位置为障碍物的时候，其可达路径为记为0，因为没有可以到达它的位置。
  6.         // 3.第一行和第一列因为只有一个方式可达，因此均记为1，遇到障碍物记为0
  7.         // 4.循环遍历二维数组，从第一个位置开始记录可达路径数量
  9.           if (obstacleGrid == null || obstacleGrid.length == 0) {
  10.             return 0;
  11.         }
  13.         // 定义 dp 数组并初始化第 1 行和第 1 列。
  14.         int len1 = obstacleGrid.length, len2 = obstacleGrid[0].length;
  15.         int[][] dp = new int[len1][len2];
  16.         for (int i = 0; i < len1 && obstacleGrid[i][0] == 0; i++) {
  17.             dp[i][0] = 1;
  18.         }
  19.         for (int j = 0; j < len2 && obstacleGrid[0][j] == 0; j++) {
  20.             dp[0][j] = 1;
  21.         }
  22.         for(int i=1;i<len1;i++){
  23.             for(int j=1;j<len2;j++){
  24.                 if(obstacleGrid[i][j]==0){
  25.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
  26.                 }
  27.             }
  28.         }
  29.         return dp[len1-1][len2-1];
  30.     }
  31. }