63. 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?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Example 1:

Input: obstacleGrid = [0,0,0],[0,1,0],[0,0,0](/kumaeki/LeetCode/wiki/0,0,0],[0,1,0],[0,0,0)
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [0,1],[0,0](/kumaeki/LeetCode/wiki/0,1],[0,0)
Output: 1

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

---

解法1

每次只能往下或者往右移动, 也就是说对于每个位置 grid[i][j] 来说,只需要考虑 grid[i-1][j] 和 grid[i][j-1] 两个位置就可以了.

定义一个 m * n 的二位数组, 每个位置到达当前位置的可能路径数.

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1 - obstacleGrid[0][0];
        // 第一列单独计算
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = dp[i - 1][0];
        }
        // 第一行单独计算
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 1)
                break;
            dp[0][j] = dp[0][j - 1];
        }

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];

        return dp[m - 1][n - 1];
    }
}

---

解法2

dynamic programming, 动态规划.

其实不用把所有结果都保存下来,可以观察到其实每次只需要保存相邻2层的数据就可以.

定义两个长度为n的数组(更优雅的方式是定义n+1长度, 但是我很容易把自己绕进去,所以这里用n), 一个保存上一层的数据,一个保持当前层的数据.

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        // 上一层到每一个点可能的路径数
        int[] pre = new int[n];
        // 当前层到每一个点可能的路径数
        int[] cur = new int[n];
        
        // 第一层单独计算
        int[] arr = obstacleGrid[0];
        for(int j = 0; j < n; j++){
            // 如果当前位置是障碍物,那么后面的位置都是不可到达的,退出循环
            if(arr[j] == 1)
                break;
            // 否则计为1
            pre[j] = 1;
        }
        
        // 从第二层开始,每次的计算都基于上一层的计算结果
        for(int i = 1; i < m; i++){
            arr = obstacleGrid[i];
            for(int j = 0; j < n; j++){
                // 如果当前位置是障碍物,那么跳过当前位置,计算下一位置
                if(arr[j] == 1)
                    continue;
                
                cur[j] = pre[j] + (j > 0 ? cur[j-1] : 0);
            }
            pre = cur;
            cur = new int[n];
        }
        
        return pre[n - 1];
    }
}