LC931. 下降路径最小和

题目描述

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1： DldbbO2fyoGIp2xGy2Xc4yWgnuc.jpg

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

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

提示： n == matrix.length == matrix[i].length 1 <= n <= 100 -100 <= matrix[i][j] <= 100

题目解析

题目在说什么

简单来说，我们有一个正方形的数字矩阵（比如一个表格），要从第一行选一个格子出发，然后每次只能往下一行的正下方、左下方或右下方走一步，一直走到最后一行。这条路径上所有格子里的数字加起来，就是这条路径的“和”。我们要找到所有可能的路径里，和最小的那一条。

比如说，如果矩阵是：

2 1 3
6 5 4
7 8 9

从第一行选1，然后往下一行可以走到5（正下方）或4（右下方），再往下走……最后可能得到1+5+8=14，或者1+4+8=13，等等。我们要找出最小的那个和，这里就是13。

思路是怎么来的

想象一下，你站在一个山坡上，山坡分成很多层（行），每层有很多个位置（列）。你从最上面一层出发，每次只能往下走一层，而且只能走到正下方、左下方或右下方。你想找一条路，让经过的所有位置上的数字加起来最小。

这个问题有点像“走楼梯选最小数字”，但每一层你只能从上面层的三个位置（左、中、右）过来。如果我们从最上面开始想，会很复杂，因为要同时考虑很多条路。但如果我们反过来想：从最下面一层往上推，就简单多了。

假设我们已经知道走到第i行、第j列这个位置的最小和是多少，那么它一定是从上一行的三个位置（左上方、正上方、右上方）中，选一个最小的和，再加上当前位置的数字。这就是“动态规划”的思路：把大问题拆成小问题，先解决小问题，再一步步得到大问题的答案。

我们可以用一个表格（叫dp表）来记录走到每个位置的最小和。比如dp[i][j]就表示从第一行走到第i行第j列这个位置的最小和。那么dp[i][j] = matrix[i-1][j-1] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])。注意，这里的i和j是从1开始数的，方便处理边界。

代码逐步拆解

我们来看代码，一行一行解释。

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;

• 先得到矩阵的大小n，因为它是n x n的。

        int[][] dp = new int[n + 1][n + 2];

• 创建一个dp表格，比原矩阵多一行（用来处理第一行）和多两列（左右各多一列，用来处理边界情况，比如最左边和最右边没有格子时，我们给一个很大的数，这样就不会被选到）。

        // Base case
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }

• 把dp表格最左边一列（索引0）和最右边一列（索引n+1）都设为非常大的数。这样，当我们在计算dp[i][j]时，如果它要从上一行的左边或右边取，而那个位置是边界外，我们就不会选到它（因为很大）。

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = matrix[i - 1][j - 1] + Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1]));
            }
        }

• 这是核心部分。两层循环：i从1到n，j从1到n。
• dp[i][j] = 当前位置的数字（注意原矩阵索引是i-1, j-1） + 上一行三个位置的最小值。