64. Minimum Path Sum

二刷
DP
Time O(mn)
Space O(n)
91.54 %
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int width = grid[0].length;
        int[][] dp = new int[width][2];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < width; j++) {
                if (i == 0) {
                    if (j != 0) {
                        dp[j][0] = dp[j - 1][0] + grid[i][j];
                    }
                } else if (j == 0) {
                    dp[j][i % 2] = dp[j][(i - 1) % 2] + grid[i][j];
                } else {
                    dp[j][i % 2] = grid[i][j] + Math.min(dp[j][(i - 1) % 2], dp[j - 1][i % 2]);
                }
            }
        }
        return dp[width - 1][(grid.length - 1) % 2];
    }
}


一刷
Version #1 DP
Space O(mn)
Time O(mn)
可以不initialize dp数组
直接update grid
这样是no extra space
见version #2
44.00%
public class Solution {
    public int minPathSum(int[][] grid) {
         if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return -1;
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];
        int row, col;
        for (row = 1; row < rows; row++) {
            dp[row][0] = dp[row - 1][0] + grid[row][0];
        }
        for (col = 1; col < cols; col++) {
            dp[0][col] = dp[0][col - 1] + grid[0][col];
        }
        for (row = 1; row < rows; row++) {
            for (col = 1; col < cols; col++) {
                dp[row][col] = Math.min(dp[row - 1][col], dp[row][col - 1]) + grid[row][col];
            }
        }
        return dp[rows - 1][cols - 1];
     
    }
}

Version #2

DP
Space O(1)
需要注意当x == 0 || y == 0的时候初始化的问题
不是说不动就可以了
对于x==0, 它的值会变成+=sum[y - 1]
对于y==0,它的值会变成+=sum[x - 1]
 40.96 %
public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (x == 0 && y == 0) continue;
             
                if (x == 0) grid[x][y] += grid[x][y - 1];
                else if (y == 0) grid[x][y] += grid[x - 1][y];
                else grid[x][y] += Math.min(grid[x - 1][y], grid[x][y - 1]);
            }
        }
        return grid[rows - 1][cols - 1];
    }
}