931. Minimum Falling Path Sum
931. Minimum Falling Path Sum
题目
Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.
A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
Example 1:
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.
Example 2:
Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
题目大意
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的 下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
解题思路
这是一个典型的动态规划问题。可以采用自底向上的方法，从矩阵的倒数第二行开始，逐行更新，直到第一行。
定义状态 dp[i][j] 为从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp[i][j]。那么，dp[i][j] 的值可以通过考虑从 dp[i-1][j-1]，dp[i-1][j] 和 dp[i-1][j+1] 这三个路径和中，选择其中路径和最小的一个。
具体的状态转移方程为：
dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
最终，我们只需从 dp 数组的最后一行中找到最小的路径和，即为最终的答案：
return Math.min(...dp[m - 1]);
由于 dp[i][j] 只和 dp[i - 1][...] 有关，所以可以进一步优化空间复杂度，除了可以将 dp 数组降维以外，甚至可以不使用 dp 数组，直接原地修改 matrix 数组。
- 时间复杂度：
O(m * n)，其中m为矩阵行数，n为矩阵列数，需要遍历整个矩阵。 - 空间复杂度：
O(1)，原地修改矩阵。
代码
/**
* @param {number[][]} matrix
* @return {number}
*/
var minFallingPathSum = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
// 从倒数第二行开始逐行更新
for (let i = 1; i < m; i++) {
for (let j = 0; j < n; j++) {
// 考虑边界情况
if (j == 0) {
matrix[i][j] =
Math.min(matrix[i - 1][j], matrix[i - 1][j + 1]) + matrix[i][j];
} else if (j == n - 1) {
matrix[i][j] =
Math.min(matrix[i - 1][j - 1], matrix[i - 1][j]) + matrix[i][j];
} else {
matrix[i][j] =
Math.min(
matrix[i - 1][j - 1],
matrix[i - 1][j],
matrix[i - 1][j + 1]
) + matrix[i][j];
}
}
}
// 返回最后一行的最小路径和
return Math.min(...matrix[m - 1]);
};