C++で解く！行列の上から下への最大合計パスを求めるアルゴリズム

問題概要

n×n の行列を考えます。行列の各セル（マス）には何らかの値が割り当てられています。移動は、i 行目のセルから (i+1) 行目の斜め下のセルにのみ行うことができます。つまり、セル (i, j) から移動できるのは、セル (i+1, j-1) とセル (i+1, j+1) の2か所だけです。この条件に従って最上行から最下行まで移動する経路の中で、通過するセルの値の合計が最大となる経路を求めてください。

入力例

{
    {5, 6, 1, 17},
    {-2, 10, 8, -1},
    { 3, -7, -9, 4},
    {12, -4, 2, 2}
}

この場合、最大合計は (17 + 8 + 4 + 2) = 31 となります。

アルゴリズムの考え方

• 最上行の各セルを起点として、そこから最下行まで辿れるすべての経路の最大合計を求め、最終的にその中で最大の値を返します。
• 同じ部分問題の結果が何度も必要になるため、動的計画法（Dynamic Programming）を活用します。

具体的には、dp[i][j] を「セル (i, j) から最下行まで移動するときに得られる合計の最大値」と定義します。最下行では dp[n-1][j] = mat[n-1][j] であり、それより上の行では次の漸化式が成り立ちます。

dp[i][j] = mat[i][j] + max(dp[i+1][j-1], dp[i+1][j+1])

この計算を下の行から順番に行っていき、最後に最上行 dp[0][j] の最大値を答えとします。計算量は O(n²) であり、すべての経路を素朴に探索する指数時間のアプローチと比べてはるかに効率的です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int getMaxMatrixSum(int mat[SIZE][SIZE], int n){
    if (n == 1) {
       return mat[0][0];
    }
    int dp[n][n];
    int maxSum = INT_MIN, max;
    for (int j = 0; j < n; j++) {
       dp[n - 1][j] = mat[n - 1][j];
    }
    for (int i = n - 2; i >= 0; i--) {
       for (int j = 0; j < n; j++) {
          max = INT_MIN;
          if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) {
             max = dp[i + 1][j - 1];
          }
          if (((j + 1) < n) && (max < dp[i + 1][j + 1])) {
             max = dp[i + 1][j + 1];
          }
          dp[i][j] = mat[i][j] + max;
       }
    }
    for (int j = 0; j < n; j++) {
       if (maxSum < dp[0][j]) {
          maxSum = dp[0][j];
       }
    }
    return maxSum;
}
int main(){
    int mat[SIZE][SIZE] = {
        {5, 6, 1, 17},
        {-2, 10, 8, -1},
        {3, -7, -9, 4},
        {12, -4, 2, 2}
    };
    int n = 4;
    cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
    return 0;
}

実行結果

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

Maximum Sum = 31