image.png

    状态定义：dp[i][j] 表示到达 （i，j）处的不同路径总数.

    问题目标：dp[n][m]

    状态转移：由于每次只能往右或往下移动，那么 dp[i][j] 必然与 dp[i-1][j] （注：（i-1，j）往下走一步到（i，j)) 和 dp[i][j - 1]有关，又由于题目对路径的格子加了约束（有些格子不能访问），那么有
    dp[i][j] = 当前格子是否有障碍物 ? dp[i-1][j] + dp[i][j-1] : 0

    状态初始化：dp[1][1] = 1，且 dp 中第一行、第一列在未遇到障碍物前均设置为1，障碍物及障碍物以后的位置均为0

    时间复杂度：O(m * n)

    空间复杂度：O(m * n) ——可优化

    1. class Solution {
    2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    3.         int m = obstacleGrid.length;
    4.         int n = obstacleGrid[0].length;
    6.         int[][] dp = new int[m + 1][n + 1];
    8.         //dp初始化
    9.         for(int i = 1; i <= n; i++){
    10.             if(obstacleGrid[0][i-1] == 1){ //如果遇到障碍物，说明后面的列过不去了
    11.                 break;
    12.             }
    13.             dp[1][i] = 1;
    14.         }
    15.         for(int i = 1; i <= m; i++){
    16.             if(obstacleGrid[i-1][0] == 1){ //如果遇到了障碍物，说明后面的行过不去了
    17.                 break;
    18.             }
    19.             dp[i][1] = 1;
    20.         }
    22.         for(int i = 2; i <= m; i++){
    23.             for(int j = 2; j <= n; j++){
    24.                 if(obstacleGrid[i-1][j-1] == 1){
    25.                     continue;
    26.                 }
    27.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
    28.             }
    29.         }
    30.         return dp[m][n];
    31.     }
    32. }