C++で解く直角三角形の数字パスにおける最大合計の求め方

問題文

数字が直角三角形の形に配置されたデータが与えられます。三角形の頂点から底辺へ向かう経路の中で、通過する数字の合計が最大になるものを見つけてください。ただし、各経路では次の数字として「真下」または「右斜め下」のいずれかのマスを選んで移動します。

例

入力:
3
4 5
1 10 7

このとき、最大合計は 18 となります（3 + 5 + 10 の経路が最適）。

アルゴリズム

基本的な考え方は、「最終行の各マスで終わる経路の最大合計」をすべて求め、その中から最大値を答えとして返すというものです。

これらの合計は、一つ上の行にある2つのマス（左上・右上）を順に参照していくことで再帰的に計算できます。

しかし、同じ部分問題が何度も重複して計算されるため、動的計画法（DP）を活用することで、最終行の各マスで終わる最大合計を効率よく求めることができます。

C++実装例

#include<bits/stdc++.h>
using namespace std;
int maxSum(int tringle[][3], int n){
    if (n > 1) {
        tringle[1][1] = tringle[1][1] + tringle[0][0];
        tringle[1][0] = tringle[1][0] + tringle[0][0];
    }
    for(int i = 2; i < n; i++) {
        tringle[i][0] = tringle[i][0] + tringle[i-1][0];
        tringle[i][i] = tringle[i][i] + tringle[i-1][i-1];
        for (int j = 1; j < i; j++){
            if (tringle[i][j] + tringle[i-1][j-1] >= tringle[i][j] + tringle[i-1][j]) {
                tringle[i][j] = tringle[i][j] + tringle[i-1][j-1];
            } else {
                tringle[i][j] = tringle[i][j] + tringle[i-1][j];
            }
        }
    }
    int max = tringle[n - 1][0];
    for(int i = 1; i < n; i++) {
        if(max < tringle[n-1][i]) {
            max = tringle[n-1][i];
        }
    }
    return max;
}
int main(){
    int tringle[3][3] = {
        {3},
        {4,5},
        {1,10,7}
    };
    cout << "Maximum sum = " << maxSum(tringle, 3) << endl;
    return 0;
}

出力

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

Maximum sum = 18