Longest Increasing Path in a Matrix
m 行 n 列の整数のグリッドである matrix が、行のリストとして与えられます。パスは、上下左右のいずれかに一歩ずつ移動してセルからセルへ進みます（斜めへの移動や、端を越えて反対側に回り込む移動はできません）。また、各移動先の値は、移動元の値より厳密に大きくなければなりません。このようなパスのうち、最長のものに含まれるセルの数を返してください。セル1つだけでも、長さ1のパスです。
関数
- matrixinteger-2d-array
- 同じ長さの行のリストとしての値のグリッド
- 戻り値integer
- 最長の狭義単調増加経路上のセル数
制約
1 ≤ m, n ≤ 100。ここで、m = matrix.length、n = matrix[i].length- すべての行の長さは同じ
nです。 0 ≤ matrix[i][j] ≤ 231-1
例
- 入力
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- 出力
- 7
- 説明
- 経路 3, 4, 5, 6, 7, 8, 9 は右端の列を下り、最下段を左に進み、中央の列を上り、角の 9 まで左に進みます。7 マスです。最小値はこれより悪くなります。1 からの最良の経路は 1, 2, 7, 8, 9 と 1, 6, 7, 8, 9 で、それぞれ 5 マスです。
- 入力
- matrix = [[2, 2, 2], [2, 5, 2]]
- 出力
- 2
- 説明
- 等しい値が 2 つあっても増加する段階にはならないため、どの経路も 2 のマスをたどることはできません。できるのは、5 の周りにある 3 つの 2 のいずれかから 5 へ進むことです。2 マスです。
- 入力
- matrix = [[4, 4], [4, 4], [4, 4]]
- 出力
- 1
- 説明
- すべての値は4なので、どこにも進めるマスはありません。各セルはそれだけで1マスの経路となり、答えは1です。
提出時に隠しテスト+18件
発展問題
最長経路の長さだけでなく、最長経路のうち1つを構成するセルも返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
経路が、すでに通ったセルに戻ってくることはあるでしょうか？進むにつれて値がどう変化するかを見てみましょう。
値は増加する一方なので、経路上で同じセルを通ることはありません。また、あるセルから始まる最長経路は、そこに至るまでの経路には依存しません。それは、そのセルより大きい隣接セルのうち最適なものから始まる最長経路に 1 を加えたものです。
各セルについてその数を一度計算して保存します。自分で用意したスタックを使って、より大きい近傍セルをたどる深さ優先探索で値を埋めるか、グリッドの頂点から層ごとに一度ずつ取り除いて、層の数を数えます。
解説
各セルから、より大きな値を持つ各隣接セルへ矢印を引きます。矢印をたどるたびに値が大きくなるため、矢印をたどる連鎖が出発点に戻ることはありません。つまり、このグリッドは有向非巡回グラフであり、求めるのはその最長経路です。一般のグラフでは、入力が大きい場合、この問題を解くのは非常に困難です。しかし、サイクルがなければ、あるセルからの最長経路はそのセルだけで決まるため、各セルにつき一度計算すればよく、問題全体の計算量は O(m × n) になります。メモ化した深さ優先探索では上から下へ計算し、山頂からグリッドを剥がしていく逆向きの Kahn のアルゴリズムでは下から上へ計算します。
すべての増加するパスをたどる
正しいが、最大のテストでは終わらない
考え方
すべてのセルから探索を始めます。現在いるセルから、値が大きい隣接セルを4方向それぞれ試し、そこから同じように、値の大きい隣接セルがなくなるまで進み続けます。それぞれの探索で通ったセルの数を数え、その最大値を保持します。
この探索に訪問済み集合は必要ありません。各ステップで値が大きくなるため、探索が同じセルに戻ることはありません。再びそのセルに立つには、そのセルの値まで下がらなければならないからです。探索は（セル、長さ）の組をスタックに積んで行います。組を取り出すと、そのセルで探索が1つ終了し、値の大きい隣接セルを積むと探索が延長されます。
この方法は正しいものの、探索が分岐するため、どうしようもなく遅くなります。各値が行番号と列番号の和である100 × 100のグリッドでは、右または下への移動はどちらも値が増える一歩となり、左上のセルから始まる探索だけでも、その数は10^58を超えます。さらに悪いことに、あるセルからの探索は、別の探索がそのセルを通るたびにやり直されます。次の方法では、この無駄をなくします。
アルゴリズム
- 各セルについて、(そのセル, 1) をスタックにプッシュします。
- エントリ (セル, 長さ) をポップし、長さで答えを更新します。
- グリッド内にあり、値が厳密に大きい各隣接セルについて、(隣接セル, 長さ + 1) をプッシュします。
- スタックが空になるまで繰り返し、その後、次の開始セルに移動します。
- 確認した中で最大の長さを返します。
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
answer = 0
for sr in range(rows):
for sc in range(cols):
# Each entry is one path in progress: the cell it ends on and
# how many cells it has.
stack = [(sr, sc, 1)]
while stack:
r, c, length = stack.pop()
answer = max(answer, length)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
stack.append((nr, nc, length + 1))
return answer独自のスタックを使ったメモ化深さ優先探索
考え方
best[cell]を、そのセルから始まる最長増加経路に含まれるセルの数とします。経路はそのセルで終わるか、次のステップでより大きい隣接セルへ進み、その隣接セルからの最長経路をたどります。したがって、より大きい隣接セルnbについてbest[cell] = 1 + max(best[nb])となり、隣接セルがなければ1です。この値を再利用しても安全です。グラフは非巡回の形をしているため、どの経路でもcellより前にあるセルはすべて小さく、cellより後に現れることはありません。また、cellからの最適な続きは、そこにどう到達したかに関係なく同じです。各bestを一度だけ計算して保存すれば、指数的に増える歩行の木を、セルごとに一度訪問するだけにできます。
最初の例では、9にはより大きい隣接セルがないため、そこでのbestは1です。次に8は2、7は3、6と2は4、5と1は5、4は6、そして3は7となり、これが答えです。各セルは4つの隣接セルを確認するので、計算量はO(m × n)です。
自然なコードは再帰的です。あるセルのbestを返す関数が、より大きい隣接セルそれぞれに対して自分自身を呼び出します。呼び出しの深さはたどる経路の長さと等しく、制約上、すべてのセルを通る経路がありえます。100 × 100のグリッドを行きつ戻りつ蛇行する値を配置すると、10,000セルからなる1本の経路ができます。一方、Pythonはデフォルトではネストした呼び出しが1,000回に達すると停止します。以下のコードは再帰処理そのものを実行するため、どんなに長い経路でも処理できます。セルのスタックと、各セルについて4方向のうちいくつ試したかを保持します。スタックの一番上のセルを確認し、まだ試していない方向があればそれを試します。そこにある隣接セルがより大きく、まだ処理済みでなければ、スタックに追加します。4方向すべてを試し終えたとき、より大きい隣接セルはすべて処理済みです。そこでセルを取り出し、そのbestを設定します。これは、再帰呼び出しがたどる順序とまったく同じです。
この探索では、サイクル検出とは異なり、「処理中」の印は必要ありません。スタック上の各セルは、その直下にあるセルより大きいため、スタックの一番上のセルに隣接するより大きいセルが、スタックのより下に存在することはありません。
アルゴリズム
bestを0（まだ不明）で初期化し、すべてのセルの方向カウンターを0にします。bestが0のセルをそれぞれスタックに積みます。- スタックの一番上のセルを確認します。まだ試していない方向があれば、カウンターを進め、その方向の隣接セルがグリッド内にあり、値が大きく、処理が完了していなければスタックに積みます。
- 4方向すべてを試したら、セルをスタックから取り出し、そのセルより値が大きい隣接セルの
bestの最大値に1を加えた値をbestに設定します。該当する隣接セルがなければ、1を設定します。 - 最大の
bestを返します。
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# best[r][c]: cells on the longest increasing path that starts at (r, c).
# 0 means not known yet.
best = [[0] * cols for _ in range(rows)]
# step[r][c]: how many of the 4 directions the search has tried from (r, c).
step = [[0] * cols for _ in range(rows)]
answer = 0
for sr in range(rows):
for sc in range(cols):
if best[sr][sc]:
continue
# Our own stack instead of recursion: a path can be thousands of
# cells long, past Python's limit of 1,000 nested calls.
stack = [(sr, sc)]
while stack:
r, c = stack[-1]
d = step[r][c]
if d < 4:
step[r][c] = d + 1
nr, nc = r + dirs[d][0], c + dirs[d][1]
# The stack only climbs, so a larger neighbour is never on it.
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
stack.append((nr, nc))
continue
# Every larger neighbour is finished: build on the best of them.
stack.pop()
length = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
length = max(length, best[nr][nc] + 1)
best[r][c] = length
answer = max(answer, length)
return answerグリッドを頂点から剥がす
考え方
動的計画法を逆向きにして、Kahnのアルゴリズムがトポロジカル順序を構築するように、値の大きいセルから下へ進めます。どの隣接セルよりも大きいセルをピークと呼びます。ピークから始まる経路は動けないため、セルは1つです。すべてのピークを一度に取り除きます。これがレイヤー1です。すると、最後の大きい隣接セルを失ったセルがいくつか現れ、残ったセルの中でピークになります。それらをレイヤー2として取り除き、グリッドが空になるまで続けます。レイヤー数が答えです。
理由：セルがレイヤーkに属するのは、そのセルから始まる最長経路のセル数がちょうどkの場合です。セルは、最後の大きい隣接セルが取り除かれた次のラウンドで取り除かれるため、そのレイヤーは大きい隣接セルのレイヤーの最大値に1を足した値になります。これは、前の方法の式 best[cell] = 1 + max(best[nb]) と同じです。最も深いレイヤーは、最長経路の始点に属します。
最初の例では、唯一のピークは9です（隣接セルは8と2）。これを取り除くと8が解放され、8を取り除くと7が解放され、7を取り除くと2と6が解放されます。この2つを取り除くと1と5が解放され、5を取り除くと4が解放され、4を取り除くと3が解放されます。レイヤーは7つで、経路3、4、5、6、7、8、9はそれぞれのレイヤーのセルを1つずつ通ります。
次のレイヤーを素早く見つけるには、各セルについて、まだ残っている大きい隣接セルの数を数えます。セルを取り除くと、それより小さい各隣接セルの数が減り、その数が0になった隣接セルは次のレイヤーに入ります。各セルは一度だけ取り除かれ、隣接するセルの各組は定数回調べられるため、処理量は O(m × n) で、スタックも再帰も必要ありません。
アルゴリズム
- すべてのセルについて、値が大きい隣接セルの数を数えます。
- 数が 0 のすべてのセルを現在のレイヤーに入れます。
- レイヤーが空でない間、レイヤー数に 1 を加えます。レイヤー内の各セルについて、値が厳密に小さい各隣接セルの数を減らし、数が 0 になった隣接セルを次のレイヤーに入れます。
- 次のレイヤーを現在のレイヤーにして、繰り返します。
- レイヤー数を返します。
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
higher = [[0] * cols for _ in range(rows)]
layer = []
for r in range(rows):
for c in range(cols):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
higher[r][c] += 1
# A peak: no neighbour is larger, so a path from it has one cell.
if higher[r][c] == 0:
layer.append((r, c))
layers = 0
while layer:
layers += 1
next_layer = []
for r, c in layer:
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
higher[nr][nc] -= 1
# Its last larger neighbour is peeled: it is a peak now.
if higher[nr][nc] == 0:
next_layer.append((nr, nc))
layer = next_layer
# Each layer is one step further from a peak; the count is the longest path.
return layers
落とし穴と境界ケース
ここでのバグは、「厳密に」という条件、深い再帰、そして他のグリッド問題で身についた習慣に起因します。
>=ではなく>と比較すること。隣り合う 4 が 2 つあると、それぞれがもう一方より大きいものとして数えられ、矢印がループを作ります。総当たりでは行ったり来たりを永遠に繰り返し、メモ化した探索では、まだ計算中の長さを読み取ってしまいます。- 非常に長い経路での再帰。再帰探索は、経路の長さと同じ深さまで呼び出しが続きます。また、制約上、すべてのセルを通る経路があり得ます。100 × 100 のグリッドを蛇行する値によって、セル数 10,000 の経路ができます。これは Python のデフォルト上限である 1,000 回のネストした呼び出しの 10 倍です。このような長い経路には、自前のスタックを使った反復的な探索、または再帰上限の引き上げ（Python では
sys.setrecursionlimit）が必要です。ただし、上限を非常に高くしても、インタープリター自体のスタックがオーバーフローすることがあります。 - 塗りつぶしのように、訪問済みのセルを飛ばすこと。計算済みのセルに到達しても行き止まりではありません。そのセルに保存された長さこそが、現在のセルに必要な値です。飛ばさずに読み取りましょう。
- 最小値からだけ開始すること。最初の例では、1 から始めるとセル数は 5 ですが、答えの 7 は 3 から始まります。最長経路は、より小さい隣接セルのない任意のセルから開始でき、そのようなセルは複数ある場合もあります。
- 0 を返すこと。すべてのセルはセル数 1 の経路なので、値がすべて等しいグリッドでも、1 × 1 のグリッドでも、答えは 1 です。各セルの長さは 0 ではなく 1 で初期化しましょう。
- 剥離方式で、値が等しい隣接セルのカウントを減らすこと。より大きい隣接セルを失ったのは、厳密に小さい隣接セルだけです。
よくある質問4
行列内の最長増加パスの時間計算量は何ですか？
メモ化した深さ優先探索またはトポロジカルな剥離を使うと、時間計算量は O(m × n)、空間計算量は O(m × n) です。m × n 個のセルはそれぞれ一度処理され、4 つの隣接セルを定数回確認します。また、どちらの方法でも各セルにつき1つの数値を保持します。すべてのセルから可能な経路を試すと、代わりに計算量は指数関数的になります。各値が行番号と列番号の和である 100 × 100 のグリッドでは、左上のセルから 10^58 を超える経路が出ていきます。
この問題では、なぜ訪問済み集合が不要なのでしょうか？
上るだけの経路では、セルに戻ることはできません。そのセルの値まで下りて戻る必要があるからです。したがって、厳密に増加するというルールによって、すでに再訪は禁止されています。よって、ステップのグラフに循環はありません。メモ化が安全なのもそのためです。あるセルに至るまでのセルが、そのセル以降の経路に影響することはありません。
行列内の最長増加パスは、動的計画法の問題ですか、それともグラフの問題ですか？
両方です。これは有向非巡回グラフにおける最長経路であり、トポロジカル順序に沿った動的計画法です。各セルの答えは、そのセルより値の大きい隣接セルの答えのうち最大のものに1を加えた値です。メモ化した深さ優先探索では、探索が各セルを終了する順に表を埋めていきます。一方、トポロジカルな剥離では、ピークから始めて層ごとに表を埋めます。セルを値の大きい順に並べる方法も有効な3つ目の順序ですが、その場合、ソートに O(m × n × log(m × n)) のコストがかかります。
これは最長増加部分列とどう違うのですか？
部分列は要素を飛ばすことができ、順序を保つ必要があります。一方、ここでの経路は、上下左右いずれかの方向で隣接するマスへ進まなければなりません。部分列の問題は直線上の動的計画法ですが、こちらはグラフに変換した格子上の動的計画法です。どちらも、厳密に増加する列は決して自分自身に戻ってループすることがない、という同じ事実に基づいています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def longestIncreasingPath(matrix):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
期待値
7