C++で解く「最小落下パスの合計」問題 ― 動的計画法による効率的なアプローチ

整数の正方配列 A が与えられたとき、A を通る「落下パス（Falling Path）」の合計の最小値を求めることを考えます。落下パスとは、最初の行の任意の要素からスタートし、それ以降は各行から1つずつ要素を選んで進む経路のことです。ただし重要な制約として、次の行で選べる要素は、直前の行で選んだ列から最大でも1列しかずれていない場所（同じ列・左隣・右隣）に限定されます。

例えば、次のような行列が与えられたとしましょう。

この場合の出力は 12 になります。条件を満たす落下パスは複数存在し、[1,4,7]、[1,4,8]、[1,5,7]、[1,5,8]、[1,5,9]、[2,4,7]、[2,4,8]、[2,5,7]、[2,5,8]、[2,5,9]、[2,6,9]、[3,5,7]、[3,5,8]、[3,5,9]、[3,6,8]、[3,6,9] などが挙げられます。これらの中で合計が最小となるのは [1,4,7] のパスで、その合計は 12 です。

アプローチ：ボトムアップ型の動的計画法

この問題は動的計画法（DP）を使うことで効率的に解けます。ポイントは、行列の下の行から順に処理を進めていくことです。各セルに対して「そのセルを出発点として最下部まで到達したときの最小合計」を計算し、元の行列に書き込んでいきます。

具体的な手順は以下の通りです。

• n := 配列のサイズとする
• i を n − 2 から 0 まで減らしながら繰り返す
  • j を 0 から n − 1 まで繰り返す
    • j − 1 < 0 の場合は x1 := 無限大、それ以外は x1 := matrix[i + 1][j − 1]（左下のセル）
    • x2 := matrix[i + 1][j]（真下のセル）
    • j + 1 >= n の場合は x3 := 無限大、それ以外は x3 := matrix[i + 1][j + 1]（右下のセル）
    • matrix[i][j] := matrix[i][j] + min(x1, x2, x3)
• ans := 無限大とする
• i を 0 から n − 1 まで繰り返す
  • ans := min(ans, matrix[0][i])
• ans を返す

端の列では斜め方向のセルが存在しないため、無限大（INT_MAX）を代入することで、min の計算時に自動的に除外されるようにしています。すべての行を処理し終えると、最初の行には「そこから始まる落下パスの最小合計」が格納されているので、その行の最小値が答えになります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minFallingPathSum(vector<vector<int>>& a) {
        int n = a.size();
        // 下の行から順に処理する（ボトムアップ）
        for(int i = n - 2; i >= 0; i--){
            for(int j = 0; j < n; j++){
                int x1 = j - 1 < 0 ? INT_MAX : a[i+1][j-1]; // 左下
                int x2 = a[i+1][j];                         // 真下
                int x3 = j + 1 >= n ? INT_MAX : a[i+1][j+1]; // 右下
                a[i][j] += min({x1, x2, x3});
            }
        }
        int ans = INT_MAX;
        for(int i = 0; i < n; i++){
            ans = min(ans, a[0][i]);
        }
        return ans;
    }
};
main(){
    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
    Solution ob;
    cout << (ob.minFallingPathSum(v));
}

入力

[[1,2,3],[4,5,6],[7,8,9]]

出力

12

計算量について

このアルゴリズムは、行列内の全セルを一度ずつ処理するため、時間計算量は O(n²) です。また、入力の行列自体を結果の保存先として再利用しているため、追加のメモリはほぼ不要で、空間計算量は O(1) に抑えられます。全経路を素朴に列挙する方法では指数関数的に計算量が増大しますが、動的計画法を用いることで大規模な行列でも高速に解けるのが大きな利点です。