[LeetCode]--63. Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

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

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

寻求最短路径，从左上走到右下，保证每次只能往左走或往下走（不可以斜着走）。其中数字1是障碍，表示“此路不通”，求总共的路线数。

第一种二维数组

用一个二维数组来表示前者的路径
核心就是这个，如果不等于1，我们就找到前者的路径相加。

if (obstacleGrid[i][j] == 1) {
                    continue;
                } else {
                    int tmp = obstacleGrid[i - 1][j] == 1 ? 0 : val[i - 1][j];
                    tmp = obstacleGrid[i][j - 1] == 1 ? tmp : tmp
                            + val[i][j - 1];
                    val[i][j] = tmp;
                }

public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1)
            return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] val = new int[m][n];
        val[0][0] = 1;

        for (int i = 1; i < m; i++)
            if (obstacleGrid[i][0] != 1 && val[i - 1][0] != 0)
                val[i][0] = 1;

        for (int i = 1; i < n; i++)
            if (obstacleGrid[0][i] != 1 && val[0][i - 1] != 0)
                val[0][i] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    continue;
                } else {
                    int tmp = obstacleGrid[i - 1][j] == 1 ? 0 : val[i - 1][j];
                    tmp = obstacleGrid[i][j - 1] == 1 ? tmp : tmp
                            + val[i][j - 1];
                    val[i][j] = tmp;
                }
            }
        }
        return val[m - 1][n - 1];
    }

第二种一维数组

其实一维数组足以表示前者的路径，因为一维数组左边是你更新过的，右边是没更新，没更新的相当于上一排，也就是上一排的来路加上左边的来路之和就是现在的来路。（解释好混乱，但我是这样想就理解了）

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1)
            return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] step = new int[n];
        step[0] = 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                    step[j] = 0;
                else if (j > 0)
                    step[j] += step[j - 1];
            }
        return step[n - 1];
    }