C++で三角形の最大パス合計を求める方法

この問題では、三角形の形に配置された数値が与えられます。私たちのタスクは、三角形の中で最大のパス合計を見つけるプログラムを作成することです。

要素は、1行目に1つの要素から始まり、行が進むごとに要素数が1つずつ増えていき、n行目まで配置されます。

つまり、プログラムは三角形内の要素の合計が最大となるパスを見つける必要があります。頂点から下へ進む際に、隣接する行の要素を選びながら、合計が最大になる経路を求めるのが目標です。

具体例を使って問題を理解しましょう。

入力例と出力例

入力 −

   1
  5 6
 8 2 9

出力 − 16

説明 −

頂点から下へ進むパスのうち、最大の合計を返すのは 9 + 6 + 1 = 16 となるパスです。

解き方のアプローチ

この問題を解くには、ボトムアップ（下から上へ）方式の動的計画法（DP）を使用します。

まず、三角形のすべての数値を左詰めにし、各行の末尾に0を埋めて整形します。これにより、三角形は「最小コストパス問題」で扱うような行列の形になります。

次に、最下段から処理を開始し、各要素について取り得るすべてのパスを確認します。その要素に到達するまでの合計が最大になるパスを選択し、値を累積していきます。この処理を頂点まで繰り返すことで、三角形のパスにおける最大合計を効率的に求めることができます。

アルゴリズムのポイント

• 下の行から順に処理することで、各要素は「真下の要素」と「右下の要素」のうち大きい方を選んで加算します。
• 計算結果は行列自体に上書き保存されるため、追加のメモリをほとんど必要としません。
• 最終的に頂点の要素 mat[0][0] に最大合計が格納されます。

実装例

三角形の最大パス合計を求めるC++プログラム −

#include<iostream>
using namespace std;
#define N 3

int findMaxPathSumTriangle(int mat[][N], int m, int n){
    for (int i=m-1; i>=0; i--){
        for (int j=0; j<=i; j++){
            if (mat[i+1][j] > mat[i+1][j+1])
                mat[i][j] += mat[i+1][j];
            else
                mat[i][j] += mat[i+1][j+1];
        }
    }
    return mat[0][0];
}

int main() {
    int triangle[N][N] = {
        {1, 0, 0},
        {5, 6, 0},
        {8, 2, 9} };
    cout<<"三角形の最大パス合計は "<<findMaxPathSumTriangle(triangle, 2, 2);
    return 0;
}

出力

三角形の最大パス合計は 16

このように、ボトムアップの動的計画法を用いることで、全経路を個別に探索する必要がなくなり、時間計算量 O(n²) で効率的に最大パス合計を求めることができます。