Pythonで2D行列の最長増加パスの長さを求めるプログラム

2次元の行列が与えられたとき、その中に存在する「最も長い狭義単調増加パス」の長さを求める問題を考えます。パスをたどる際には、上下左右の4方向へ移動できますが、斜め方向への移動は許されません。

例として、次のような入力行列を見てみましょう。

この場合の出力は 6 になります。最長のパスは [1, 2, 4, 6, 7, 9] となるためです。

解法のアプローチ

この問題は、深さ優先探索(DFS)による再帰を使って解くことができます。各マスを起点とした場合の最長増加パスの長さを計算し、その最大値を答えとします。具体的な手順は以下の通りです。

• 行列の行数 n と列数 m を取得します。
• 上下左右への移動を表す方向リスト moves を定義します([[1, 0], [-1, 0], [0, 1], [0, -1]])。
• dp(y, x) 関数を定義します。これは座標 (y, x) を起点とする最長増加パスの長さを返します。
• 座標が行列の範囲外の場合は 0 を返します。
• 現在のマスの値 currVal を取得し、4方向それぞれについて、隣接マスが範囲内かつ現在の値より大きい場合は再帰的に dp を呼び出し、その結果の最大値を res に記録します。
• res + 1 を返します(自分自身のマス分を加算)。
• メイン処理では、すべてのマスを起点として dp を呼び出し、得られた結果の最大値を返します。

Pythonでの実装例

理解を深めるために、以下の実装例を確認してみましょう。

class Solution:
    def solve(self, matrix):
        n, m = len(matrix), len(matrix[0])
        moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        def dp(y, x):
            if y < 0 or y >= n or x < 0 or x >= m:
                return 0
            currVal = matrix[y][x]
            res = 0
            for d in moves:
                dy, dx = d
                newY, newX = y + dy, x + dx
                if (newY >= 0 and newY < n and newX >= 0 and newX < m and matrix[newY][newX] > currVal):
                    res = max(res, dp(newY, newX))
            return res + 1
        result = 0
        for i in range(n):
            for j in range(m):
                result = max(result, dp(i, j))
        return result
ob = Solution()
matrix = [
    [2, 4, 6],
    [1, 5, 7],
    [3, 3, 9]
]
print(ob.solve(matrix))

パフォーマンス改善のヒント

上記の実装では同じマスに対して何度も再帰計算が発生する可能性があります。functools.lru_cache を使ってメモ化を追加すると、各マスの計算が一度だけ行われるため、大規模な行列でも効率的に動作します。

入力

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

出力

6