题解 | 矩阵的最小路径和

import java.util.*;


public class Solution {

    private static int sum = Integer.MAX_VALUE;
    private static int r = 0;
    private static int l = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];

        // 初始化第一行和第一列
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < cols; j++) {
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }

        // 填充dp数组
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }
        // 右下角元素即为所求的最小路径和
        return dp[rows - 1][cols - 1];
    }

    private void back(int[][] matrix, int curl, int curr, int cursum) {

        if (r == curr || l == curl ) {
            return;
        }
        cursum += matrix[curl][curr];
        if (curr == r - 1 && curl == l - 1 ) {
            sum = Math.min(sum, cursum);
            return;
        }
        back(matrix, curl + 1,  curr, cursum);
        back(matrix, curl,  curr + 1, cursum);
        cursum -= matrix[curl][curr];
    }
}

每次只能向下和向右，提前获取构建最外层数据列和，头节点下对应向下和向右数据取最小值然后加上对应位置数据，通过这种方式计算完成，最后一个位置就是最小和