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 から始める場合、最適な経路のセル数は 5 です。
- 入力
- matrix = [[2, 2, 2], [2, 5, 2]]
- 出力
- 2
- 説明
- 等しい値は上への一歩ではないため、2の上を進む経路はありません。最善なのは、5の周囲にある3つの2のいずれかから5へ進むことです。2マスです。
- 入力
- matrix = [[4, 4], [4, 4], [4, 4]]
- 出力
- 1
- 説明
- すべての値が4なので、どこでも移動はできません。各セル単独で1セルの経路となるため、答えは1です。
発展問題
最長経路のセルと、その長さも返すことはできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
経路が、一度訪れたセルに再び戻ることはあるでしょうか？進むにつれて値がどう変化するかを見てみましょう。
値は増加する一方なので、経路上で同じセルを通ることはありません。また、あるセルから始まる最長経路は、そこに至るまでの経路には依存しません。それは、そのセルより大きい隣接セルのうち最適なものから始まる最長経路に1を加えたものです。
各セルについてその数を一度計算して保存します。自分で用意したスタックを使って、より大きな隣接セルをたどる深さ優先探索で求めるか、グリッドのピークから一層ずつ取り除いて層の数を数えます。
解説
各セルから、それぞれのより大きい隣接セルへ矢印を引きます。どの矢印をたどっても値は増加するため、矢印の連鎖がループすることはありません。したがって、グリッドは有向非巡回グラフであり、答えはその最長経路です。サイクルがないため、あるセルからの最長経路はそのセルだけで決まり、各セルにつき一度だけ計算すれば済みます：O(m × n)。
すべての増加する経路をたどる
正しいが、最大のテストでは終わらない
考え方
各マスから探索を始め、より大きな値を持つ隣接マスへのすべての分岐を、進めなくなるまでたどります。最も長い探索が答えです。進むたびに値が大きくなるため、探索が同じマスに戻ることはなく、訪問済み集合も必要ありません。
別の探索が通るたびに、そのマスからの探索をやり直します。各マスの値が行番号と列番号の和である 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について1 + max(best[nb])とし、そのようなセルがなければ1です。経路上でcellより前にあるセルはすべて小さく、cellより後に来ることはないため、これを保存しても安全です。最初の例では、9は1、8は2、7は3、6と2は4、5と1は5、4は6、3は7になります。
経路は10,000個すべてのセルを通ることもあり、再帰では深すぎるため、自分でスタックを用意します。スタック最上位のセルは次の方向を試し、まだ処理が終わっていない大きな隣接セルをプッシュします。4方向すべてを試し終えたら、そのセルをポップしてbestを設定します。各スタック上のセルはその下のセルより大きいため、「処理中」を示すマークは必要ありません。
アルゴリズム
- 各セルの
bestを0（まだ不明）にし、方向カウンターを0にします。 bestが0の各セルをスタックに積みます。- スタックの最上部にあるセルで、カウンターを進めます。その隣のセルがグリッド内にあり、値が大きく、処理が完了していなければ、そのセルをスタックに積みます。
- 4方向を調べたら、そのセルをスタックから取り出し、
bestを、そのセルより値が大きい隣接セルのbestの最大値に1を足した値、または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です。すべてのピークを取り除き、最後の大きい隣接セルを失ったセルが次のレイヤーになります。グリッドが空になるまで繰り返します。セルは最後の大きい隣接セルの1ラウンド後に取り除かれるため、そのレイヤーはbestと等しく、レイヤー数が答えです。最初の例のレイヤーは、9、8、7、2と6、1と5、4、3です。
各セルについて、残っている自分より大きい隣接セルの数を数えます。セルを取り除くと、自分より小さい各隣接セルの数が減り、数が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 つある場合、総当たりでは前後に永遠に行き来し、メモ化検索では計算中の長さを読み取ってしまいます。- Python で再帰する。100 × 100 のグリッドを蛇行する値は、10,000 個のセルからなる経路を作り、デフォルトの呼び出し上限 1,000 の 10 倍になります。
- 塗りつぶし処理のように、処理済みのセルを飛ばす。そのセルに保存された長さこそ、現在のセルが必要とする値です。
- 最小値からだけ開始する。最初の例では 1 から始めると 5 個のセルになりますが、答えの 7 は 3 から始まります。
- 長さを 0 から始める。同じ値だけのグリッドの答えは 1 です。
よくある質問3
行列内の最長増加パスの時間計算量は何ですか？
メモ化した深さ優先探索、または剥がし処理を使うと、時間計算量と空間計算量は O(m × n) です。各セルは一度だけ処理され、4つの隣接セルを調べます。すべてのセルからすべての経路を試すと、計算量は指数的になります。
行列内の最長増加パスは、動的計画法の問題ですか、それともグラフの問題ですか？
どちらも正しいです。これは有向非巡回グラフにおける最長経路であり、トポロジカル順序に沿った動的計画法です。セルを値の大きい順に並べ替える方法でも、有効な順序を得られますが、並べ替えに O(m × n × log(m × n)) のコストがかかります。
これは最長増加部分列とどう違いますか？
部分列は要素を飛ばしても構いませんが、順序は保ちます。ここでの経路は、上下左右いずれかの方向に隣接するセルへ進む必要があります。どちらの場合も、厳密に増加する連鎖が自分自身に戻ってループすることはありません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def longestIncreasingPath(matrix):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
期待される出力
7