63. 不同路径 II java解决

63. 不同路径 II

 题目描述：

难度：中等
相关标签：数组、动态规划、矩阵

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。


示例 1：
    输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    输出：2
    解释：
        3x3 网格的正中间有一个障碍物。
        从左上角到右下角一共有 2 条不同的路径：
        1. 向右 -> 向右 -> 向下 -> 向下
        2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
    输入：obstacleGrid = [[0,1],[0,0]]
    输出：1
提示：
    m ==obstacleGrid.length
    n ==obstacleGrid[i].length
    1 <= m, n <= 100
    obstacleGrid[i][j] 为 0 或 1

核心的思路和算法依旧是动态规划：

        dp[ i ][ j ] = dp[ i - 1 ] + dp[ j -1 ]

        只不过相比 (75条消息) 62. 不同路径 java解决_其然乐衣的博客-CSDN博客 ，本题需要先前加上判断，判断前一格是否是障碍，非障碍则可以加上

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 
        //情况：如果开头（左上角）== 1，也就是开始第一步都走不，这是可以直返回0
        if ( obstacleGrid[ 0 ][ 0 ] == 1 )
            return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[ 0 ].length;
        int[][] dp = new int[ m ][ n ];
        for ( int i = 0; i < m; i ++ ) {
            for( int j = 0; j < n ; j ++ ) {
 
                //1. 如果i == 0 || j == 0 的情况
                if ( i == 0 && obstacleGrid[ i ][ j ] == 0 ) {
                    if ( j == 0 ) {   //如果是起点，赋值1即可
                        dp[i][j] = 1;
                        continue;
                    } 
                    //如果上方一个不是障碍1，则等于上方一格值即可，如果是上方一格是障碍的话，那么该列的下边剩下的值都将会是0
                    else if( obstacleGrid[ i ][ j - 1 ] != 1 ) 
                        dp[ i ][ j ] = dp[ i ][ j - 1 ];
                } else if ( j == 0 && obstacleGrid[ i ][ j ] == 0 ) {
                    if ( i == 0 ) {  //如果是起点，赋值1即可
                        dp[i][j] = 1;
                        continue;
                    } 
                    //如果左方一个不是障碍1，则等于左方一格值即可，如果是左方一格是障碍的话，那么该行的右边剩下的值都将会是0
                    else if( obstacleGrid[ i - 1 ][ j ] != 1 ) 
                        dp[ i ][ j ] = dp[ i - 1 ][ j ];
                }
 
                //2. i != 0 && j != 0 的情况
                else if ( obstacleGrid[ i ][ j ] != 1 ) {
                    //左边一格不是障碍，方可加上
                    if ( obstacleGrid[ i - 1 ][ j ] != 1  ) 
                        dp[ i ][ j ] += dp[ i - 1 ][ j ];
                    //上边一格不是障碍，方可加上
                    if( obstacleGrid[ i ][ j - 1 ] != 1 )
                        dp[ i ][ j ] += dp[ i ][ j - 1 ];
                }
            }
        }
 
        return dp[ m - 1 ][ n - 1 ];
 
    }
}