C++で解く！行列の最終行の任意の要素で終わる最大重みパスの求め方

この問題では、整数 n と、各セルの重みが格納された n × n の行列が与えられます。目的は、行列の最終行の任意の要素で終わる最大重みパスを見つけるプログラムを作成することです。

経路の探索は左上のセル (0,0) から開始し、移動として許されるのは「下」と「右下（斜め）」のみです。左への移動は禁止されています。

問題例

具体例を使って問題を確認してみましょう。

入力：

n = 3
Mat[3][3] = {
    {4, 3, 1},
    {5, 8, 9},
    {6, 7, 2}}

出力：

19

説明：

取り得るすべての経路は以下の通りです。
Path1: 4+5+6 = 15
Path2: 4+8+7 = 19
Path3: 4+8+2 = 12
Path4: 4+5+7 = 16

これらの中で最も重みが大きいのは Path2 の 19 です。

解法のアプローチ

一つの解法として、すべての経路を列挙して比較する方法が考えられます。しかし、n が大きくなると組み合わせの数が爆発的に増えるため、この方法は非常に非効率です。

より効果的なのが動的計画法（Dynamic Programming）の活用です。この問題は、同じ部分問題が何度も現れる「重複する部分構造」を持つ典型的なケースだからです。起点となるセルからは最大 n 本の分岐が生じ、それぞれが答えの候補となります。

具体的には、次のような手順で解きます。

• DP用の行列 sumMat を作成し、そのセルへ到達するまでの最大重みを格納します。
• sumMat の最終行に含まれる値の中から最大値を求め、それを出力します。

サンプルプログラム

上記のアルゴリズムを実装したC++のプログラムがこちらです。

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int maxCost(int matrix[][MAX], int N) {
    int sumMat[N][N];
    memset(sumMat, 0, sizeof(sumMat));
    int maxSum = 0;
    sumMat[0][0] = matrix[0][0];
    for (int i=1; i<N; i++)
        sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
    for (int i=1; i<N; i++)
    for (int j=1; j<i+1&&j<N; j++)
        sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
    for (int i=0; i<N; i++)
        if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
    return maxSum;
}
int main(){
    int mat[MAX][MAX] ={
        {5 , 6 , 1 },
        {2 , 11 , 10 },
        {15, 3 , 2 }};
    int N = 3;
    cout<<"左上セルから最終行への最大パス合計 : "<<maxCost(mat, N)<<endl;
    return 0;
}

実行結果

左上セルから最終行への最大パス合計 : 22

このように動的計画法を使えば、全経路を列挙することなく O(n²) の計算量で最大重みパスを効率的に求めることができます。