63. Unique Paths II

三刷 06/2022

Version #1 1D DP

由于每个DP的值只是向上看和向左看，we can read dp[x] value first then overwrite dp[x], so 1 dimension is enough

Time O(MN)

Space O(N)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.

Memory Usage: 40.2 MB, less than 96.76% of Java online submissions for Unique Paths II.

class Solution {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int rows = obstacleGrid.length;

        int cols = obstacleGrid[0].length;

        int[] dp = new int[cols];

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (obstacleGrid[y][x] == 1) {

                    dp[x] = 0;

                    continue;

                }

                if (y == 0 && x == 0) {

                    dp[x] = 1;

                } else if (y == 0) {

                    dp[x] = dp[x - 1];

                } else if (x == 0) {

                    continue;

                } else {

                    dp[x] += dp[x - 1];

                }

            }

        }

        return dp[cols - 1];

    }

}

二刷

98.52 %
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) return 0;
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        int[] prev = null;
        for (int y = 0; y < rows; y++) {
            int[] curr = new int[cols];
            for (int x = 0; x < cols; x++) {
                if (obstacleGrid[y][x] == 1) continue;
                if (y == 0 && x == 0) {
                    curr[0] = 1;
                } else if (y == 0) {
                    curr[x] = curr[x - 1];
                } else if (x == 0) {
                    curr[x] = prev[x];
                } else {
                    curr[x] = prev[x] + curr[x - 1];
                }
            }
            prev = curr;
        }
        return prev[cols - 1];
    }
}



一刷
直接写很难写对，先写二维的然后化简就很容易了
由于只用了一维dp
                 (y - 1, x)
                         |
(y, x - 1)  -  (y, x)
当扫到(y, x)的时候，(y, x - 1)已经被覆盖了，所以用prev保持(y, x - 1)的值
当x == 0 的时候，dp[x] = dp[x] 不需要更新

100.00 % 
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
            return 0;
        }
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        int[] ways = new int[cols];
        for (int y = 0; y < rows; y++) {
            int prev = 0;
            for (int x = 0; x < cols; x++) {
                if (obstacleGrid[y][x] == 1) {
                    ways[x] = 0;
                } else {
                    if (y == 0 && x == 0) {
                        ways[x] = 1;
                    } else if (y == 0) {
                        ways[x] = prev;
                    } else if (x != 0){
                        ways[x] = ways[x] + prev;
                    }
                }
                prev = ways[x];
            }
        }
        return ways[cols - 1];
    }
}