Pythonで解く最小経路合計（Minimum Path Sum）―動的計画法による実装

問題の概要

m × n の行列に非負整数が格納されているとき、左上の角から右下の角へ至る経路のうち、経路上の数値の合計が最小になるものを見つけます。ただし、移動できる方向はどの時点でも「下」または「右」のいずれかに限定されます。

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

この場合の出力は 7 となり、最適な経路は 1 → 3 → 1 → 1 → 1 です。この経路を選ぶことで合計が最小になります。

アルゴリズムの手順

この問題は動的計画法（DP）を使うと効率的に解けます。ここでは、入力の行列自体を書き換えながら累積合計を記録していくインプレース方式を採用します。

1. 行数と列数を取得：row := 行数 − 1、column := 列数 − 1 とします。
2. 最終行を処理：j を column − 1 から 0 まで減らしながら、grid[row][j] += grid[row][j+1] を実行します。これで最終行の各セルには「そこから右端まで進んだ場合の合計」が格納されます。
3. 最終列を処理：i を row − 1 から 0 まで減らしながら、grid[i][column] += grid[i+1][column] を実行します。これで最終列の各セルには「そこから下端まで進んだ場合の合計」が格納されます。
4. 残りのセルを処理：i と j をそれぞれ右下から左上へ向かって減らしながら、grid[i][j] += min(grid[i][j+1], grid[i+1][j]) を実行します。「右に進む場合」と「下に進む場合」のうち、より小さい累積合計の方を選んで加算します。
5. 結果を返す：grid[0][0] には左上から右下までの最小経路合計が格納されているため、その値を返します。

Pythonでの実装例

class Solution(object):
    def minPathSum(self, grid):
        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]

ob1 = Solution()
print(ob1.minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))

入力

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

出力

7

計算量について

時間計算量は O(m × n) です。また、入力行列を直接書き換えるため、追加で必要な空間計算量は O(1) となります。元の行列を保持したい場合は、同じサイズのDPテーブルを別途用意して同様の計算を行えば対応できます。