C++の三角形

• 動的計画法で使用するテーブルを1つ作成します。

• n：=三角形のサイズ

• for i：=n –2から0まで

  • for j：=0からi

    • dp [j]：=三角形[i、j]+最小のdp[j]とdp[j + 1]

• 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