【C++】動的計画法で行列の上から下への最大合計パスを求める方法

このチュートリアルでは、C++を使って、N×Nの行列（マトリックス）の最上行から最下行までの「最大合計パス」を求める方法を解説します。

問題の概要

N×Nサイズの整数行列が与えられます。最上行のいずれかのセルから出発し、1行ずつ下へ進みながら最下行に到達するまでの経路のうち、通過したセルの値の合計が最大になるものを見つけるのが目的です。移動先として選べるのは、次の行の斜め下（左下または右下）のセルのみです。

アプローチ：動的計画法（DP）

すべての経路を総当たりで調べると計算量が爆発的に増えてしまいますが、動的計画法を使えばO(N²)の計算量で効率的に解くことができます。手順は以下の通りです。

1. 初期化：最下行の各セルはそれ以上下に進めないため、そのセルの値がそのままDPテーブルの値になります。
2. 遷移：下から2番目の行から順に上へ向かって計算します。セル(i, j)のDP値は「自分の値 mat[i][j] ＋ 次の行にある左斜め下 (i+1, j-1) と右斜め下 (i+1, j+1) のDP値のうち大きい方」となります。
3. 答え：すべての行の計算が完了したら、最上行のDP値の中で最大のものが求める答えになります。

計算量は時間・空間ともにO(N²)です。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10

// 最大合計パスを求める関数
int maxSum(int mat[SIZE][SIZE], int n) {
    if (n == 1)
        return mat[0][0];
    int dp[n][n];
    int maxSum = INT_MIN, max;
    // 最下行の値をそのままDPテーブルに設定
    for (int j = 0; j < n; j++)
        dp[n - 1][j] = mat[n - 1][j];
    // 下の行から順にDPテーブルを更新
    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;
        }
    }
    // 最上行のDP値の最大値を返す
    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, 7 },
        { -2, 10, 8, -1 },
        { 3, -7, -9, 11 },
        { 12, -4, 2, 6 }
    };
    int n = 4;
    cout << "Maximum Sum = " << maxSum(mat, n);
    return 0;
}

実行結果

Maximum Sum = 28

結果の解説

この例の場合、右上端の「7」からスタートし、「8」「11」「2」とジグザグに斜め下へ進む経路（7 → 8 → 11 → 2）を選ぶと合計が28となり、これが最大値になります。負の値を含む行列でも、DPテーブルによって各セルからの最適な選択が保証されるため、正しく最大合計を求められる点がこの手法の強みです。