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