成长之路

title： 下降路径最小和931

date： 2024-05-20

tags：

- 数据结构

categories：

- 数据结构

下降路径最小和

状态转移方程定义 定义一个dp函数表示dp(matrix, i, j)表示从第0行任意一列移动到第i行第j列的最小路径和。

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int min = Integer.MAX_VALUE;
        // 可以从第一行的任意一列出发
        for (int i = 0; i < matrix[0].length; i++) {
            min = Math.min(min, dp(matrix, matrix.length - 1, i));
        }
        return min;
    }


    public int dp(int[][] matrix, int i, int j) {
        // 上一个节点的位置放置数组越界，给出一个大于可能值的值，让他在getMin的时候被过滤掉
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length ) {
            return 99999;
        }
        // base case
        if (i == 0) {
            return matrix[i][j];
        }

        // 灵魂所在，第0行任意一列移动到第i行第j列的最小路径和等于第i-1行中能到达第i行j列的最小值加上matrix[i][j]
        return getMin(dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1), dp(matrix, i - 1, j - 1)) + matrix[i][j];
    }

    public int getMin(int left, int down, int right) {
        int min = Math.min(left, down);
        return Math.min(min, right);
    }
}

上面的代码，因为存在过多的重复计算，可以使用备忘录来进行剪枝

class Solution {
    int memo[][];
    public int minFallingPathSum(int[][] matrix) {
        memo = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            Arrays.fill(memo[i], 666666);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < matrix[0].length; i++) {
            min = Math.min(min, dp(matrix, matrix.length - 1, i));
        }
        return min;
    }


    public int dp(int[][] matrix, int i, int j) {
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length ) {
            return 99999;
        }

         if (memo[i][j] != 666666) {
            return memo[i][j];
        }

        if (i == 0) {
            return matrix[i][j];
        }

        memo[i][j] = getMin(dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1), dp(matrix, i - 1, j - 1)) + matrix[i][j];
        return memo[i][j];
    }

    public int getMin(int left, int down, int right) {
        int min = Math.min(left, down);
        return Math.min(min, right);
    }
}