C++で解く逆三角形の最大パス合計問題

問題概要

この問題では、逆三角形の形に並べられた数値が与えられます。各行から1つずつ要素を選んで加算したときに得られる最大の合計（最大パス合計）を求めるプログラムを作成するのが課題です。

逆三角形とは、1行目にn個の要素、2行目にn-1個の要素、というように下の行へ向かうにつれて要素数が1つずつ減っていく数値の配置のことです。

具体例で理解しよう

入力：

5 1 9
 3 6
  2

出力： 17

解説： 最下行から最上行へ向かって、パスに含まれる要素の合計が最大になるような経路を探索します。この例では「9 → 6 → 2」という経路を選ぶことで、合計17が得られます。

解き方：動的計画法（DP）

この問題は、最小コストパス問題などでも使われる動的計画法のアプローチで効率よく解くことができます。基本的な考え方は以下の通りです。

• まず、逆三角形の数値をすべて左詰めにシフトし、空いた部分を0で埋めることで、通常の行列として扱えるようにします。
• 最下行からスタートし、上の行へ向かって処理を進めます。
• 各要素に対して、真下および左下の位置にある要素のうち大きい方を現在の要素に加算します。
• これにより、各地点から下方向への最大合計が累積されていき、最終的な最大値が求まります。

C++による実装例

逆三角形の最大パス合計を求めるプログラムは以下の通りです。

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

int findMaxPathSumInvertedTriangle(int matrix[][N]){
    int maxSum = 0;
    for (int i = N - 2; i >= 0; i--) {
        for (int j = 0; j < N - i; j++) {
            if (j - 1 >= 0)
                matrix[i][j] += max(matrix[i + 1][j], matrix[i + 1][j - 1]);
            else
                matrix[i][j] += matrix[i + 1][j];
            maxSum = max(maxSum, matrix[i][j]);
        }
    }
    return maxSum;
}

int main(){
    int invertedTriangle[N][N] = {
        {5, 1, 9},
        {3, 6, 0},
        {2, 0, 0}};
    cout<<"The maximum path sum is "<<findMaxPathSumInvertedTriangle(invertedTriangle);
    return 0;
}

実行結果

The maximum path sum is 17

まとめ

逆三角形の最大パス合計問題は、三角形を左詰めの行列に変換し、下から上へ動的計画法で累積最大値を求めていくことで解くことができます。計算量はO(N²)であり、すべての経路を列挙する指数時間のアプローチよりもはるかに効率的です。同様の手法は、最小コストパス問題や他のグリッド系DP問題にも応用できるので、ぜひマスターしておきましょう。