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

假设我们有一个整数的方形数组 A，我们想要找到通过 A 的最小下降路径和。下降路径基本上是从第一行中的任何元素开始的路径，并从每一行中选择一个元素。并且下一行的元素必须位于与前一行的列最多相差一的列中。所以如果矩阵是这样的：

123
456
789

那么输出是 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 := 数组的大小
  • for i in range n – 2 down to 0
    • for j in range 0 to n
      • 如果 j – 1 < 0，则 x1 := inf，否则 x1 := matrix[i + 1, j - 1]
      • x2 := matrix[i + 1, j]
      • 如果 j + 1 >= n，则 x3 := inf，否则 x3 := matrix[i + 1, j + 1]
      • matrix[i, j] := matrix[i, j] + min of x1, x2, x3
  • ans := inf
  • for i in range 0 to n – 1
    • ans := min of ans and matrix[0, i]
  • return 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

更新于: 2020年4月30日

203 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告