931.下降路径最小和

题目

给你一个 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]]

示例 2：

输入： matrix = [[-19,57],[-40,-5]]
输出： -59
解释： 下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57],
[-40,-5]]

示例 3：

输入： matrix = [[-48]]
输出： -48

提示：

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

  思路

1. DFS（超时）
   从上往下，遍历所有的情况。每次选择下面三支中路径和最小的加到上当前值作为从当前路径起始的路径长度。
2. 动态规划
   从下往上，依次遍历每一层每个节点作为起点到最下面的路径长度最小值。
   最后取第一行最小的即可。

   代码

3. DFS

   class Solution {
   public:
       int minFallingPathSum(vector<vector<int>>& matrix) {
           if(matrix.size()<1) return 0;
           int val = INT_MAX;
           for(int i=0;i<matrix[0].size();i++){
               val = min(val,minFallingPathSum(matrix,0,i));
           }
           return val;
       }
       int minFallingPathSum(vector<vector<int>>& m,int y,int x){
           if(y>=m.size()) return 0;
           if(x<0||x>=m[0].size()) return INT_MAX;
           int a = minFallingPathSum(m,y+1,x-1);
           int c = minFallingPathSum(m,y+1,x);
           int b = minFallingPathSum(m,y+1,x+1);
           int g = min(a,min(b,c));
           if(g==INT_MAX) return INT_MAX;
           return g+m[y][x];
           
       }
   };

4. 动态规划

   class Solution {
   public:
       int minFallingPathSum(vector<vector<int>>& matrix) {
           int m = matrix.size(),n=matrix[0].size();
           vector<vector<int>> dp(m,vector<int>(n,0));
           for(int x=0;x<n;++x) dp[m-1][x] = matrix[m-1][x];
           for(int y=m-2;y>=0;--y){
               for(int x=1;x<n-1;++x){
                   int val = dp[y+1][x];
                   if(x-1>=0) val = min(val,dp[y+1][x-1]);
                   if(x+1<n) val = min(val,dp[y+1][x+1]);
                   dp[y][x] = matrix[y][x]+val;
               }
           }
           int res = INT_MAX;
           for(int x=0;x<n;++x) res = min(res,dp[0][x]);
           return res;
       }
   };