08. 最小路径和

// 暴力递归方式：
public static int minPathSum(int[][] m) {
    if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        return 0;
    }
    return process(m, 0, 0);
}
public static int process(int[][] arr, int x, int y) {
    if (x == arr.length - 1 && y == arr[0].length - 1) {
        return arr[x][y];
    }
    //        if (x > arr.length - 1 ||  y > arr[0].length - 1){
    //            return 0;
    //        }
    int p1 = x + 1 < arr.length ? (arr[x][y] + process(arr, x + 1, y)) : Integer.MAX_VALUE;
    int p2 = y + 1 < arr[0].length ? (arr[x][y] + process(arr, x, y + 1)) : Integer.MAX_VALUE;
    return Math.min(p1, p2);
}
public static int minPathSum1(int[][] m) {
    if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        return 0;
    }
    int row = m.length;
    int col = m[0].length;
    int[][] dp = new int[row][col];
    dp[0][0] = m[0][0];
    for (int i = 1; i < row; i++) {
        dp[i][0] = dp[i - 1][0] + m[i][0];
    }
    for (int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j - 1] + m[0][j];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
        }
    }
    return dp[row - 1][col - 1];
}
// 空间压缩技巧,将dp[row][col] 压缩为 dp[col]
public static int minPathSum2(int[][] m) {
    if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        return 0;
    }
    int row = m.length;
    int col = m[0].length;
    int[] dp = new int[col];
    dp[0] = m[0][0];
    for (int j = 1; j < col; j++) {
        dp[j] = dp[j - 1] + m[0][j];
    }
    for (int i = 1; i < row; i++) {
        dp[0] += m[i][0];
        for (int j = 1; j < col; j++) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + m[i][j];
        }
    }
    return dp[col - 1];
}
// for test
public static int[][] generateRandomMatrix(int rowSize, int colSize) {
    if (rowSize < 0 || colSize < 0) {
        return null;
    }
    int[][] result = new int[rowSize][colSize];
    for (int i = 0; i != result.length; i++) {
        for (int j = 0; j != result[0].length; j++) {
            result[i][j] = (int) (Math.random() * 100);
        }
    }
    return result;
}
// for test
public static void printMatrix(int[][] matrix) {
    for (int i = 0; i != matrix.length; i++) {
        for (int j = 0; j != matrix[0].length; j++) {
            System.out.print(matrix[i][j] + " ");
        }
        System.out.println();
    }
}
public static void main(String[] args) {
    int rowSize = 10;
    int colSize = 10;
    int[][] m = generateRandomMatrix(rowSize, colSize);
    System.out.println(minPathSum(m));
    System.out.println(minPathSum1(m));
    System.out.println(minPathSum2(m));
}

// 动态规划 
public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }

    int M = grid.length;
    int N = grid[0].length;

    int[][] dp = new int[M][N];
    dp[M - 1][N - 1] = grid[M - 1][N - 1];
    // 最后一行
    for (int i = N - 2; i >= 0; i--) {
        dp[M - 1][i] = grid[M - 1][i] + dp[M - 1][i + 1];
    }
    // 最后一列
    for (int i = M - 2; i >= 0; i--) {
        dp[i][N - 1] = grid[i][N - 1] + dp[i + 1][N - 1];
    }
    //中间  从底向上 从右向左依次赋值
    for (int i = M - 2; i >= 0; i--) {
        for (int j = N - 2; j >= 0; j--) {
            dp[i][j] = grid[i][j]+Math.min(dp[i+1][j],dp[i][j+1]);
        }
    }
    return dp[0][0];
}