dp第13天

931. 下降路径最小和

这题和之前的三角形下降最小和一样，边界判断更麻烦一点。用到的都是自底向上的方法

算法入门第12天 – zeroheart

/**
 931. 下降路径最小和
 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

 示例 1：

 输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
 输出：13
 解释：如图所示，为和最小的两条下降路径
 示例 2：

 输入：matrix = [[-19,57],[-40,-5]]
 输出：-59
 解释：如图所示，为和最小的下降路径

 * @author zeroheart
 *
 */
public class Question931 {
    public static int minFallingPathSum(int[][] matrix) {
        // 之前有个三角形最小路径，试下是不是一样的逻辑，实际看来是一样的，主要要处理边界问题
        int len = matrix.length;

        int[][] dp = new int[len+1][len+1];

        for(int i = len-1; i>=0; i--){
            for(int j = 0; j<len; j++){
                if(j==0) {
                    dp[i][j] = matrix[i][j] + Math.min(dp[i+1][j], dp[i+1][j+1]);
                } else if(j==len-1){
                    dp[i][j] = matrix[i][j] + Math.min(dp[i+1][j-1], dp[i+1][j]);
                }else {
                    dp[i][j] = matrix[i][j] + Math.min(dp[i+1][j-1], Math.min(dp[i+1][j], dp[i+1][j+1]));
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for(int i = 0; i<len; i++){
            res = Math.min(res, dp[0][i]);
        }

        return res;
    }

    public static void main(String[] args) {
//        minFallingPathSum(new int[][]{{2,1,3},{6,5,4},{7,8,9}});
        minFallingPathSum(new int[][]{{82,81},{69,33}});
    }
}