C++で三角形の最小パス合計を求める方法（動的計画法）

三角形が与えられたとき、頂点から底辺までの最小パス合計を求める問題を考えてみましょう。各ステップでは、下の行にある隣接する数字のいずれかに移動することができます。

例えば、次のような三角形があるとします。

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

この場合、上から下への最小パス合計は 11 となります（2 + 3 + 5 + 1 = 11）。

アルゴリズムの手順

この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解くことができます。手順は以下の通りです。

• 動的計画法で使用するためのテーブル（配列 dp）を1つ作成します。初期値として三角形の最下行をコピーします。
• n := 三角形のサイズとします。
• i を n − 2 から 0 まで減らしながら繰り返します。
  • j を 0 から i まで繰り返します。
    • dp[j] := triangle[i][j] + min(dp[j], dp[j + 1])
• 最後に dp[0] を返します。

ポイントは、下の行から順に処理していくことです。各位置について、「真下の要素」と「右下の要素」のうち小さい方を選んで現在の値に加算することで、その時点での最適な経路の累積和が求まります。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

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];
   }
};

このコードでは、まず三角形の最下行をコピーして dp 配列を初期化しています。その後、下から上へ向かって各行を更新していき、すべての行を処理し終えた時点で dp[0] に頂点から底辺までの最小パス合計が格納されます。

なお、この手法の計算量は時間・空間ともに O(n²) の三角形に対して、時間計算量は O(n²)、追加の空間計算量は O(n) に抑えられるため、非常に効率的です。

入力

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

出力

11