C ++中的三角形

让我们看看步骤-

• 创建一个表以用于动态编程方法。

• n：=三角形的大小

• 对于i：= n – 2降至0

• dp [j]：=三角形[i，j] + dp [j]和dp [j +1]的最小值

• 对于j：= 0到i

• 返回dp [0]

例子（C ++）

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumTotal(vector<vector<int>>& triangle) {
      vector <int> dp(triangle.back());
      int n = triangle.size();
      for(int i = n - 2; i >= 0; i--){
         for(int j = 0; j <= i; j++){
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
         }
      }
      return dp[0];
   }
};
main(){
   Solution ob;
   vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
   cout << ob.minimumTotal(v);
}

输入值

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

输出结果

11