C++で解く「三角形」問題：動的計画法による最小パス和の求め方

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

問題の例

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

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

この場合、頂点から底辺への最小パス和は 11 になります（2 + 3 + 5 + 1 = 11）。上から順に、各行で隣接する小さい方の数字を選んで移動していくイメージです。

アルゴリズム（動的計画法）

この問題は動的計画法（DP）を使うことで効率的に解けます。ポイントは、下の行から順に計算を積み上げていくことです。手順は以下の通りです。

• 動的計画法用のテーブル dp を1つ作成します。初期値として、三角形の最下行をコピーします。

• n := 三角形の行数 とします。

• i := n − 2 から 0 まで（最後から2番目の行から頂点に向かって）繰り返します：

  • j := 0 から i まで繰り返します：

    • dp[j] := triangle[i][j] + min(dp[j], dp[j + 1]) を計算します。
      つまり、現在のマスの値と、直下・右下の2つの選択肢のうち小さい方を足し合わせます。

• 最終的に dp[0] を返します。これが頂点から底辺までの最小パス和となります。

この方法なら、時間計算量は O(n²)、空間計算量は O(n) と効率的です。dp配列を最下行で初期化し、上書きしながら更新していくため、追加のメモリをほとんど必要としません。

C++での実装例

理解を深めるために、実際の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);
}

コードの流れを簡単に整理すると、まず dp ベクトルを三角形の最下行 triangle.back() で初期化し、その後、下から2番目の行から順番に、各要素に対して「自分の値＋下の2つのうち小さい方」という更新を行っています。すべての行を処理し終えた時点で dp[0] に最小パス和が格納されています。

入力例

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

出力結果

11