C ++中的最小下降路径总和

假设我们有一个整数A的平方数组，我们希望通过A的下降路径的最小和。下降路径基本上是一条从第一行中的任何元素开始，并从每一行中选择一个元素的路径。并且下一行的元素必须位于与上一行的列最多相差一列的列中。所以如果矩阵像-

然后输出为12。几乎没有不同的下降路径。这些是[1,4,7]，[1,4,8]，[1,5,7]，[1,5,8]，[1,5,9]，[2,4,7]， [2,4,8]，[2,5,7]，[2,5,8]，[2,5,9]，[2,6,9]，[3,5,7]，[3 ，5,8]，[3,5,9]，[3,6,8]，[3,6,9]，最小和路径为[1,4,7]，和为12。

为了解决这个问题，我们将遵循以下步骤-

• n：=数组大小

• 当我在n – 2范围内下降到0

• 如果j – 1 <0，则x1：= inf，否则x1：= matrix [i + 1，j-1]

• x2：=矩阵[i + 1，j]

• 如果j + 1> = n，则x3：= inf，否则x3：= matrix [i +1，j + 1]

• 矩阵[i，j]：=矩阵[i，j] + x1，x2，x3的最小值

• 对于介于0到n之间的j

• ans：= inf

• 对于i，范围为0至n – 1

• ans：= ans和matrix [0，i]的最小值

• 返回ans

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minFallingPathSum(vector<vector<int>>& a) {
      int n = a.size();
      for(int i =n-2;i>=0;i--){
         for(int j =0;j<n;j++){
            int x1 = j-1<0?INT_MAX:a[i+1][j-1];
            int x2 = a[i+1][j];
            int x3 = j+1>=n?INT_MAX:a[i+1][j+1];
            a[i][j]+= min({x1,x2,x3});
         }
      }
      int ans = INT_MAX;
      for(int i =0;i<n;i++){
         ans = min(ans,a[0][i]);
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
   Solution ob;
   cout <<(ob.minFallingPathSum(v));
}

输入项

[[1,2,3],[4,5,6],[7,8,9]]

输出结果

12