C++での逆ポーランド記法の評価

三角形があるとします。上から下への最小経路合計を見つける必要があります。各ステップで、下の行の隣接する番号に移動できます。

たとえば、次の三角形が次のような場合

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

上から下への最小経路合計は11（2 + 3 + 5 + 1 =11）です。

手順を見てみましょう

• 動的計画法で使用するテーブルを1つ作成します。
• n：=三角形のサイズ
• for i：=n –2から0まで
  • for j：=0からi
    • dp [j]：=三角形[i、j]+最小のdp[j]およびdp[j + 1]
• return dp [0]

理解を深めるために、次の実装を見てみましょう

例

class Solution {
   public:
   void printVector(vector <int>& v){
   for(int i = 0; i < v.size(); i++)cout << v[i] << " ";
   cout << endl;
}
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]);
      }
      // printVector(dp);
   }
   return dp[0];
   }
};

入力

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

出力

11