C++で解く最小経路和（Minimum Path Sum）：動的計画法による効率的な解法

最小経路和（Minimum Path Sum）とは？

非負整数が格納された m × n の行列 が与えられたとき、左上の角から右下の角へ移動する経路の中で、通過する数値の合計が最小となるもの を求めるのが「最小経路和」問題です。

ただし、移動できる方向は任意の時点で下または右のみに制限されています。

たとえば、次のような行列が与えられた場合を考えてみましょう。

この場合の出力は 7 となります。最適な経路は 1 → 3 → 1 → 1 → 1 であり、これが通過する数値の合計を最小化します。

アルゴリズムの考え方（動的計画法）

この問題は、動的計画法（DP）を使って効率的に解けます。ポイントは、行列を右下から左上に向かって逆順に走査し、各セルに対して「そのマスからゴールまで到達できる最小合計」を累積していくことです。

処理の手順

• a := 行数、b := 列数 とします。

• i := a − 1、j := b − 1 として初期化します。

• j ≥ 0 の間、次を繰り返します。

  • 最終行のセルに対して、右隣のセルの値を加算します：matrix[a, j] := matrix[a, j] + matrix[a, j + 1]

  • j を 1 減らします。

• i ≥ 0 の間、次を繰り返します。

  • 最終列のセルに対して、下のセルの値を加算します：matrix[i, b] := matrix[i, b] + matrix[i + 1, b]

  • i を 1 減らします。

• j := b − 1、i := row − 1 と再設定します。

• i ≥ 0 の間、次を繰り返します。

  • j ≥ 0 の間、次を繰り返します。

    • 現在のセルに、右隣と下のセルのうち小さい方を加算します：matrix[i, j] := matrix[i, j] + min(matrix[i, j + 1], matrix[i + 1, j])

    • j を 1 減らします。

  • j := b − 1 に戻し、i を 1 減らします。

• matrix[0, 0] を返します。これが左上から右下までの最小合計です。

この方法では元の行列をそのまま DP テーブルとして利用するため、追加のメモリはほぼ不要です。

Pythonでの実装例

まずは、上記の手順を実装したサンプルコードを見てみましょう。

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row = len(grid) - 1
        column = len(grid[0]) - 1
        i = row - 1
        j = column - 1
        # 最終行の処理：右隣の値を加算
        while j >= 0:
            grid[row][j] += grid[row][j + 1]
            j -= 1
        # 最終列の処理：下の値を加算
        while i >= 0:
            grid[i][column] += grid[i + 1][column]
            i -= 1
        # 残りのセルを右下から順に処理
        j = column - 1
        i = row - 1
        while i >= 0:
            while j >= 0:
                grid[i][j] += min(grid[i][j + 1], grid[i + 1][j])
                j -= 1
            j = column - 1
            i -= 1
        return grid[0][0]

C++での実装例

同じロジックをC++で書くと、以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size() - 1;
        int column = grid[0].size() - 1;

        // 最終行の処理：右隣の値を加算
        for (int j = column - 1; j >= 0; j--)
            grid[row][j] += grid[row][j + 1];

        // 最終列の処理：下の値を加算
        for (int i = row - 1; i >= 0; i--)
            grid[i][column] += grid[i + 1][column];

        // 残りのセルを右下から順に処理
        for (int i = row - 1; i >= 0; i--) {
            for (int j = column - 1; j >= 0; j--) {
                grid[i][j] += min(grid[i][j + 1], grid[i + 1][j]);
            }
        }
        return grid[0][0];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    cout << sol.minPathSum(grid) << endl;  // 出力: 7
    return 0;
}

計算量について

• 時間計算量：O(m × n) ― 行列の全セルを一度ずつ処理します。

• 空間計算量：O(1) ― 入力の行列をそのままDPテーブルとして書き換えるため、追加メモリは不要です。

入力例

[[1,3,1],[1,5,1],[4,2,1]]

出力例

7