Pythonで解くマトリックス内の最長増加パス ― DFSとメモ化による効率的な実装

問題概要

マトリックス（二次元配列）が与えられたとき、その中に存在する最長増加パスの長さを求めることを考えます。各セルからは上下左右の4方向へ移動できますが、斜め方向への移動やマトリックスの境界外への移動は禁止されています。

例として、次のようなマトリックスを見てみましょう。

この場合の出力は 4 となります。緑色で示したセルをたどる [1, 2, 6, 9] というパスが最長の増加パスだからです。

解法のアプローチ：DFS + メモ化再帰

この問題は、深さ優先探索（DFS）にメモ化を組み合わせることで効率的に解けます。ポイントは、「各セルから始まる最長増加パスの長さ」をdpテーブルにキャッシュしておき、同じセルを何度も再計算しないことです。

アルゴリズムの手順

• solve() 関数を定義します。引数は i, j, matrix の3つです。

• dp[i][j] が 0 以外（計算済み）であれば、その値をそのまま返します。

• dp[i][j] を 1 で初期化します（自分自身だけで構成されるパスの長さ）。

• 一時変数 temp を 0 で初期化します。

• r を i-1 から i+1 まで、c を j-1 から j+1 まで二重ループで回します。

  • 自分自身（r == i かつ c == j）、または斜め方向（|r-i| == 1 かつ |c-j| == 1）の場合はスキップします。

  • (r, c) がマトリックスの範囲内であり、かつ matrix[r][c] > matrix[i][j] を満たす場合、temp を max(temp, solve(r, c, matrix)) で更新します。

• dp[i][j] に temp を加算して返します。

メイン処理の手順

• マトリックスが空であれば 0 を返します。

• 元のマトリックスと同じサイズのdpテーブルを 0 で初期化します。

• すべてのセルに対して solve() を呼び出し、dpテーブルの最大値を答えとして返します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
    def solve(self, i, j, matrix):
        if self.dp[i][j]:
            return self.dp[i][j]
        self.dp[i][j] = 1
        temp = 0
        for r in range(i-1, i+2):
            for c in range(j-1, j+2):
                if r == i and c == j or (abs(r-i) == 1 and abs(c-j) == 1):
                    continue
                if c >= 0 and r >= 0 and r < len(matrix) and c < len(matrix[0]) and matrix[r][c] > matrix[i][j]:
                    temp = max(temp, self.solve(r, c, matrix))
        self.dp[i][j] += temp
        return self.dp[i][j]

    def longestIncreasingPath(self, matrix):
        if not matrix:
            return 0
        self.dp = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
        self.ans = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dp[i][j] == 0:
                    self.solve(i, j, matrix)
                self.ans = max(self.ans, self.dp[i][j])
        return self.ans

ob = Solution()
print(ob.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))

入力

[[9,9,4],[6,6,8],[2,1,1]]

出力

4

計算量について

メモ化により、各セルの結果は一度だけ計算されます。したがって、マトリックスの行数を m、列数を n とすると、時間計算量は O(m × n)、空間計算量もdpテーブルの分だけ O(m × n) となります。素朴な全探索では最悪 O(4^(m×n)) となるため、メモ化の効果は非常に大きいといえます。