C++でNxNグリッドの最小下降パスの合計を求める方法

問題文

N×Nのサイズを持つ整数行列 A が与えられます。この課題では、A を通る「下降パス（Falling Path）」の最小合計を求めることが目標です。

• 下降パスは、最初の行の任意の要素から開始し、最後の行で終了します。
• パスは次の行ごとに1つの要素を選択していきます。ただし、次の行で選ぶ要素の列は、前の行で選んだ列と同じ列、または左右に1つだけ隣接する列でなければなりません。

例

N = 2、行列が以下の場合：
{
    {5, 10},
    {25, 15}
}
出力は 20 となります（要素 5 と 15 が選択されるため）

解法の考え方（動的計画法）

この問題は動的計画法（DP）を用いることで効率的に解けます。下から2番目の行から順に上へ向かって処理し、各セルに対して「そのセルから最下段まで到達する場合の最小合計」を計算していきます。具体的には、各セルの値に、真下・左下・右下の3つのセルのうち最小の値を加算します。すべての行を処理し終えた後、最初の行の中で最小の値が答えとなります。

C++実装例

#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
    for (int row = MAX - 2; row >= 0; --row) {
        for (int col = 0; col < MAX; ++col) {
            int val = matrix[row + 1][col];
            if (col > 0) {
                val = min(val, matrix[row + 1][col - 1]);
            }
            if (col + 1 < MAX) {
                val = min(val, matrix[row + 1][col + 1]);
            }
            matrix[row][col] = matrix[row][col] + val;
        }
    }
    int result = INT_MAX;
    for (int i = 0; i < MAX; ++i)
        result = min(result, matrix[0][i]);
    return result;
}
int main() {
    int matrix[MAX][MAX] = {
        {5, 10},
        {25, 15},
    };
    cout << "Minimum sum path = " << getMinSumPath(matrix)
        << endl;
    return 0;
}

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

出力

Minimum sum path = 20

計算量

• 時間計算量：O(N²) — 行列のすべてのセルを一度ずつ処理するためです。
• 空間計算量：O(1) — 入力の行列をそのまま更新して結果を保持するため、追加のメモリは不要です。