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

用二维数组保存每次的结果，从左上角到右下角逐步计算。可以用一位数组来压缩空间，或者可以不开辟额外空间，直接将相应结果存到matrix的第一行，然后用变量存储被覆盖掉的值。

import java.util.*;


public class Solution {
    /**
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */

    public int minPathSum(int[][] matrix) {
        // right、down
        // 最小路径和
        int height = matrix.length, width = matrix[0].length;
        for (int i = 1; i < width; i++) {
            matrix[0][i] = matrix[0][i] + matrix[0][i - 1];
        }
        for (int i = 1; i < height; i++) {
            matrix[i][0] = matrix[i - 1][0] + matrix[i][0];
        }
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < width; j++) {
                matrix[i][j] = Math.min(matrix[i - 1][j], matrix[i][j - 1]) + matrix[i][j];
            }
        }
        return matrix[height - 1][width - 1];
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minPathSum(new int[][]{{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}}));
    }
}