AlgoPressAppearance
0931-下降路径最小和
https://leetcode.cn/problems/minimum-falling-path-sum
给你一个 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], 1 [[2,1,3], 1
[6,5,4], 5 [6,5,4], 4
[7,8,9]] 7 [7,8,9]] 8
示例 2：
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57], -19
[-40,-5]] -40
示例 3：
输入：matrix = [[-48]]
输出：-48
提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100
思路分析
如果从上往下，每选择1个数，它下面可以选择3个数，此时不一定是选择3个数中的最小数。 但是如果从下往上，当我们选定一个数之后，从上面能过来的数当中，我们一定是可以选择一个最小的数，累计了往上计算，取最小的值 从下往上方法也不成立，如下 会计算出 -18 实际是 -36
[100,-42, -46, -41]
[31 ,97, 10, -10]
[-58, -51, 82, 89]
[51, 81, 69, -51]
参考代码【有问题】
csharp
public class Solution{
public int MinFallingPathSum(int[][] matrix){
int totalMinSum = int.MaxValue;
int curMinSum = 0;
for(int col=0;col<matrix[0].Length;col++){
int row = matrix.Length - 1;
curMinSum = matrix[row][col]; //取最后一个值
int minCol = col;
row--;
while(row >= 0){
//取上面3个数的最小值
int left = minCol - 1 < 0 ? 0 : minCol-1;
int right = minCol + 1 >= matrix[0].Length ? matrix[0].Length - 1 : minCol+1;
int minValue = matrix[row][left];
minCol = left;
for(int i=left+1;left<=right;left++){
if(matrix[row][i] < minValue){
minValue = matrix[row][i];
minCol = i;
}
}
curMinSum += matrix[row][minCol];
row--;
}
if(totalMinSum > curMinSum){
totalMinSum = curMinSum;
}
}
return totalMinSum;
}
}
思路分析2：动态规划
- 如果只有1行, 我们取最小值 min(colums);
- 如果有第二行，我们取从上一行转移过来的最小值 min
dp表示选择了这个数的最小值
终于没有看答案做出了这道动态规划的题目，不容易啊。 dp的定义要包含这个上述每个数字选择之后的最小值
参考代码
csharp
public class Solution{
public int MinFallingPathSum(int[][] matrix){
int rows = matrix.Length;
int columns = matrix[0].Length;
int[,] dp = new int[rows,columns];
//dp表示选择了这一个单元格的最小值
for(int i=0; i<rows; i++){
for(int j=0; j<columns; j++){
if(i==0){
//第一行，原样复制
dp[i,j] = matrix[i][j];
}
else{
if(j==0){//左边界
dp[i,j] = Math.Min(dp[i-1,j],dp[i-1,j+1])+matrix[i][j];
}
else if(j==columns-1){ //右边界
dp[i,j] = Math.Min(dp[i-1,j],dp[i-1,j-1])+matrix[i][j];
}
else{//中间
dp[i,j] = Math.Min(Math.Min(dp[i-1,j-1],dp[i-1,j]),dp[i-1,j+1])+matrix[i][j];
}
}
}
}
//返回最后一个最小值
int minSum = dp[rows-1,0];
for(int i=1; i < columns; i++){
if(dp[rows-1,i] < minSum){
minSum = dp[rows-1,i];
}
}
return minSum;
}
}
参考答案2：处理边界
先取得中间的数，如果两边还有数字，则取最小的那个
csharp
public class Solution{
public int MinFallingPathSum(int[][] matrix){
int rows = matrix.Length;
int columns = matrix[0].Length;
int[,] dp = new int[rows,columns];
//dp表示选择了这一个单元格的最小值
for(int i=0; i<rows; i++){
for(int j=0; j<columns; j++){
if(i==0){
//第一行，原样复制
dp[i,j] = matrix[i][j];
}
else{
int best = dp[i-1,j];
if(j>0){
best = Math.Min(best,dp[i-1,j-1]);
}
if(j<columns-1){
best = Math.Min(best,dp[i-1,j+1]);
}
dp[i,j] = best + matrix[i][j];
}
}
}
//返回最后一个最小值
int minSum = dp[rows-1,0];
for(int i=1; i < columns; i++){
if(dp[rows-1,i] < minSum){
minSum = dp[rows-1,i];
}
}
return minSum;
}
}
复习：动态规划
dp[i,j] 表示 i,j 位置处的最小步数，为上面3个位置的最小值+当前值
csharp
public class Solution {
public int MinFallingPathSum(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
int[,] dp = new int[m,n];
//初始化第一行
for(int j=0; j<n; j++){
dp[0,j] = matrix[0][j];
}
for(int i=1; i<m; i++){
for(int j=0; j<n; j++){
//取上面三个数的最小值
dp[i,j] = dp[i-1,j];
if(j>0){
dp[i,j] = Math.Min(dp[i-1,j-1],dp[i,j]);
}
if(j<n-1){
dp[i,j] = Math.Min(dp[i-1,j+1],dp[i,j]);
}
dp[i,j]+=matrix[i][j];
}
}
//取最后一排的最小数
int sum = int.MaxValue;
for(int j=0; j<n; j++){
sum = Math.Min(dp[m-1,j],sum);
}
return sum;
}
}