C++で解く三角形の最小パス和：動的計画法による効率的なアプローチ

問題概要

数値が三角形状に配置された構造が与えられます。頂点から最下段まで移動する際、各ステップで「下の行の隣接する数値」にのみ移動できるものとします。このとき、通過する数値の合計が最小となる経路の和を求めてください。

例

入力が以下の場合を考えます。

    5
  7 3
 8 1 2
9 6 4 5

このとき最小の合計は 13 となり、その経路は次のとおりです。

5 + 3 + 1 + 4

アルゴリズム

• 動的計画法（DP）のメモ化テクニックを利用します。
• メモ化用として、1次元配列 memorization を作成します。
• 各行 k に対して、以下の漸化式を適用します。

memorization[i] = min( memorization[i], memorization[i+1] )
+ A[k][i];

この方法のポイントは、最下段から順に上へ向かって計算を進めることです。まず最下段の値をそのまま配列にコピーし、その後は下の行の隣接する2つの要素のうち小さい方を選びながら上へ更新していきます。こうすることで、最終的に memorization[0] に最小パス和が格納されます。また、2次元のDPテーブルを使わず1次元配列だけで処理できるため、空間計算量を O(n) に抑えられるのも大きな利点です。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int>> &arr) {
    int memorization[arr.size()];
    int n = arr.size() - 1;
    for (int i = 0; i < arr[n].size(); ++i) {
        memorization[i] = arr[n][i];
    }
    for (int i = arr.size() - 2; i >= 0; --i) {
        for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
            memorization[j] = arr[i][j] +
            min(memorization[j],
            memorization[j + 1]);
        }
    }
    return memorization[0];
}
int main() {
    vector<vector<int>> arr = {
    {5},
    {7, 3},
    {8, 1, 2},
    {9, 6, 4, 5}};
    cout << "Minimum sum path = " << getMinSum(arr) << endl;
    return 0;
}

このプログラムをコンパイルして実行すると、以下の出力が得られます。

出力

Minimum sum path = 13