给你一个 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,*1*,3], [[2,*1*,3],
[6,*5*,4], [6,5,*4*],
[*7*,8,9]] [7,*8*,9]]
思路
定义如下dp函数，表示从matrix[0,...]出发到matrix[i][j]的下降路径最小和。
int dp(int matrix[][], int i, int j)
分析状态转移过程，我们可以推出，matrix[i][j]处的下降路径只能来自于matrix[i-1][j]、matrix[i-1][j-1] 、matrix[i-1][j+1]三个位置，所以dp(matrix,i,j)即为dp(matrix,i-1,j-1)、dp(matrix,i-1,j)、dp(matrix,i-1,j+1)再加上matrix[i][j]这三个值中的最小值。所以状态转移方程即为：
\[dp(matrix,i,j)=matrix[i][j] + min[dp(matrix,i-1,j-1),dp(matrix,i-1,j),dp(matrix,i-1,j+1)]
\]
base case：从matrix[0][j]开始下落。那如果我们想落到的目的地就是 i == 0，所需的路径和即为 matrix[0][j]
算法1（暴力递归）
时间复杂度：\(O(3^N)\)，指数级，运行超时！
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int res = 1e5;
for (int j = 0; j < matrix.size(); j ++ ) {
res = min(res, dp(matrix, matrix.size() - 1, j));
}
return res;
}
int min_3(int a, int b, int c) {
return min(a, min(b, c));
}
int dp(vector<vector<int>>& matrix, int i, int j) {
//非法索引检查
if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix.size()) return 99999;
//base case
if (i == 0) return matrix[i][j];
return matrix[i][j] +
min_3( dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1)
);
}
};
算法2（带备忘录的递归）
时间复杂度：\(O(N^2)\)
利用备忘录消除重叠子问题，避免重复计算。
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int res = 1e5;
vector<vector<int>> memo(matrix.size(), vector<int>(matrix.size(), 66666));
for (int j = 0; j < matrix.size(); j ++ ) {
res = min(res, dp(matrix, matrix.size() - 1, j, memo));
}
return res;
}
int min_3(int a, int b, int c) {
return min(a, min(b, c));
}
int dp(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& memo) {
//非法索引检查，因为dp函数会导致越界问题
if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix.size()) return 99999;
//base case
if (i == 0) return matrix[i][j];
if (memo[i][j] != 66666) return memo[i][j];
memo[i][j] = matrix[i][j] +
min_3( dp(matrix, i - 1, j - 1, memo),
dp(matrix, i - 1, j, memo),
dp(matrix, i - 1, j + 1, memo));
return memo[i][j];
}
};
注：
之所以将memo的元素初始化为66666，是因为题目的数据范围能取到的合法答案区间为[-10000,10000]，所以可以设置一个超出这个范围的初始值用于判断此处的下降路径最小和是否已经被计算过。
数组越界访问时返回99999同理。