leetcode刷题（125）——931. 下降路径最小和

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

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

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

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

提示：

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

动态规划

分析

我们用 dp(r, c) 表示从位置为 (r, c) 的元素开始的下降路径最小和。根据题目的要求，位置 (r, c) 可以下降到 (r + 1, c - 1)，(r + 1, c) 和 (r + 1, c + 1) 三个位置（先不考虑超出数组边界的情况），因此状态转移方程为：

dp(r, c) = A[r][c] + min{dp(r + 1, c - 1), dp(r + 1, c), dp(r + 1, c + 1)}

由于下降路径可以从第一行中的任何元素开始，因此最终的答案为min dp(0, c)

算法

我们可以直接在原数组 A 上计算 dp(r, c)，因为最后一行 A 的值就是 dp 的值 。因此我们从倒数第二行开始，从下往上进行动态规划，状态转移方程为：

A[r][c] = A[r][c] + min{A[r + 1][c - 1], A[r + 1][c], A[r + 1][c + 1]}

注意需要处理超出边界的情况，即在第一列和最后一列只能下降到两个位置。

我们用一个例子来解释动态规划的正确性。假设数组 A 为 [[1,1,1],[5,3,1],[2,3,4]]，我们现在在位置 (1, 0) 有 A[1][0] = 5，可以选择下降到位置 (2, 0) 选择元素 2，或者下降到位置 (2, 1) 选择元素 3。由于 2 比 3 小，因此我们选择下降到位置 (2, 0)，有dp(1, 0) = 5 + 2 = 7。

在依次处理完位置 (1, 0)，(1, 1) 和 (1, 2) 后，数组 A 变成了 [[1,1,1],[7,5,4],[2,3,4]]。我们继续向上处理位置 (0, 0)，(0, 1) 和 (0, 2)，最终数组 A 为 [[6,5,5],[7,5,4],[2,3,4]]，因此最终的答案为 min(A[0]) = 5。

class Solution {
    public int minFallingPathSum(int[][] A) {
        int N = A.length;
        for (int r = N-2; r >= 0; --r) {
            for (int c = 0; c < N; ++c) {
                // best = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1])
                int best = A[r+1][c];
                if (c > 0)
                    best = Math.min(best, A[r+1][c-1]);
                if (c+1 < N)
                    best = Math.min(best, A[r+1][c+1]);
                A[r][c] += best;
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int x: A[0])
            ans = Math.min(ans, x);
        return ans;
    }
}

复杂度分析

时间复杂度：O(N^2)，其中 N 是数组 A 的边长。

空间复杂度：O(N^2)。如果考虑的是额外空间复杂度，那么在使用数组 A 直接计算 dp 值时，额外空间复杂度为 O(1)。