题解 | #矩阵的最小路径和#

动态规划的经典问题，目的地的最优解，等于左边的最优解和上边的最优解的最小值。需要开辟一个二维数组，记录每个节点的最优解。

public int minPathSum(int[][] matrix) {
    int[][] arr = new int[matrix.length][matrix[0].length];
    arr[0][0] = matrix[0][0];
    // 初始化两边，避免在第三个循环中做过多的判断
    for (int i = 1; i < matrix.length; i++) {
        arr[i][0] = matrix[i][0] + arr[i - 1][0];
    }
    for (int i = 1; i < matrix[0].length; i++) {
        arr[0][i] = matrix[0][i] + arr[0][i - 1];
    }
    for (int i = 1; i < matrix.length; i++) {
        for (int j = 1; j < matrix[i].length; j++) {
            if (arr[i - 1][j] > arr[i][j - 1]) {
                arr[i][j] =  arr[i][j - 1] + matrix[i][j];
            }else{
                arr[i][j] =  arr[i-1][j ] + matrix[i][j];
            }
        }
    }

    return arr[matrix.length - 1][matrix[0].length - 1];
}