C++でマトリックスの最大パス合計を求める方法|動的計画法(DP)による実装

問題の概要

この問題では、サイズ M×N の2次元行列が与えられ、その中から最大パス合計を見つけるプログラムを作成します。

ここでいう最大パス合計とは、最初の行の任意の要素を出発点とし、最後の行の任意の要素を終点として移動しながら通過する要素をすべて足し合わせた値のうち、最大になるものを指します。移動として許されているのは真下への移動と斜め下への移動の2種類のみです。

具体例で理解する

入力:

matrix [][] =
    3 5 9
    1 7 2
    4 8 6

出力: 24

説明: 最大パスは 9 → 7 → 8 となり、その合計は 9 + 7 + 8 = 24 です。

アプローチ:動的計画法(DP)

この問題は、動的計画法を用いることで効率的に解けます。基本的な考え方は次の通りです。

• 2行目以降の各セルについて、そのセルに到達できる直前の行のセル(左上・真上・右上)の中で最大の値を、現在のセルの値に加算していきます。
• こうすることで、処理後の各セルには「その位置へ到達するまでのパス合計の最大値」が格納されます。
• 最後に最終行の最大値を求めれば、それが行列全体の最大パス合計となります。

列の端では到達可能なセルが限られるため、条件分岐で場合分けを行います。

• 左端の列(j = 0): 真上と右上の2か所と比較
• 右端の列(j = M−1): 左上と真上の2か所と比較
• 中間の列: 左上・真上・右上の3か所と比較

計算量は時間・空間ともに O(M×N) です。入力行列自体を書き換えて利用するため、追加のメモリは不要という点もメリットです。

C++での実装例

マトリックスの最大パス合計を求めるプログラム:

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

// 行列の最大パス合計を求める関数
int maxPathSum(int mat[][M]){
    // 2行目以降を順に処理し、各セルに到達時点での最大合計を累積
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // 中間の列:左上・真上・右上の最大値を加算
            if (j > 0 && j < M - 1)
                mat[i][j] += max(mat[i - 1][j], max(mat[i - 1][j - 1], mat[i - 1][j + 1]));
            // 右端の列:左上・真上の最大値を加算
            else if (j > 0)
                mat[i][j] += max(mat[i - 1][j], mat[i - 1][j - 1]);
            // 左端の列:真上・右上の最大値を加算
            else if (j < M - 1)
                mat[i][j] += max(mat[i - 1][j], mat[i - 1][j + 1]);
        }
    }
    // 最終行の最大値が全体の最大パス合計
    int maxSum = mat[N-1][0];
    for (int j = 1; j < M; j++)
        maxSum = max(mat[N-1][j], maxSum);
    return maxSum;
}

int main(){
    int matrix[N][M] = {
        {3, 5, 9 },
        {1, 7, 2},
        {4, 8, 6}};
    cout<<"行列の最大パス合計 : "<<maxPathSum(matrix);
    return 0;
}

出力結果

行列の最大パス合計 : 24

まとめ

マトリックスの最大パス合計問題は、各セルに「そこへ到達するまでの最大合計」を累積していく動的計画法によって、O(M×N) の計算量で効率的に解くことができます。端の列の扱いに注意しながら実装すれば、どのような M×N の行列にも対応できる汎用的なアルゴリズムになります。