貪欲法
01 / 共通の仕組み
各ステップで局所最適を確定し、その確定が後で覆らないことを示す。 バックトラックも DP テーブルも要らない:交換論法でどの貪欲な選択を入れ替えても 改善できないと示すか、先行論法で貪欲がどの接頭辞でも遅れないと示す。 この発想を 3 つの古典的サブパターンに落とし込む: 区間でソートして取る、配列上で到達範囲を追う、累積量で「失敗したらリセット」。
01 / 一文での本質
左から右へ走査し、これまでに到達可能な最遠の添字だけを保持する。 ジャンプを列挙する必要はない — 走査位置がその境界を越えたら終点に到達できない、 境界が最後の添字に届いた瞬間に到達済み。
問題最後の添字に到達できるか?nums[2, 3, 1, 1, 4]
入力は 5 マス。左から右へ走査し、farthest = これまでに到達可能な最遠の添字 1 つだけを保持する。
ステップ
0 / 3
i
—
最遠
0
0 / 3
02 / パターンの骨格
# 一度走査して、走行中の最遠到達値だけ持つfarthest ← 0for i in 0..n−1:if i > farthest: return False # 走査が境界を追い越したfarthest ← max(farthest, i + nums[i])if farthest ≥ n − 1: return Truereturn True# 状態は整数 1 つ — DP も再帰もない
03 / このパターンを使うべき合図
「最後の添字に到達できるか」
教科書的なトリガー(LC 55)。値が表すのはジャンプの最大距離であって正確な歩幅ではない。 だから到達可能性は 1 パスで決まる — i に到達できるどの接頭辞も、i + nums[i] までのどこにでも到達できる。
「最少ジャンプ回数」
LC 45。同じ配列、問題が違う — 到達は与件で、回数を最小化する。 貪欲は同じだが管理が変わる:現在のフロンティアと次のフロンティアを保持し、
i が現在を超えたらジャンプを確定して次に入れ替える。同じ O(N) で不変条件が異なる。「ここから或る値に到達できるか」
LC 1306(Jump Game III)。グラフが単調でなくなる — 添字 i から
i + arr[i] または i − arr[i] へ進める。 最遠到達の手は通用しないので、visited を持った BFS / DFS に落とす。「最少蛇口 / 区間で [0,n] を覆う」
LC 1326。蛇口
i は [i − r, i + r] を覆う — 「添字 i が i + nums[i] まで届く」と同じ形。 各蛇口を対応する到達値に書き直せば、問題はそのまま LC 45 になる。04 / よくある落とし穴
i.
到達判定(LC 55)と最少ジャンプ(LC 45)を混同する。
どちらも「ジャンプゲーム」だが貪欲が違う。LC 55 は
farthest 1 つで、境界に追い越されたかを問う。LC 45 は2 つのフロンティア — 現在(確定)と次(現在の中から届く最遠)— を持ち、i が現在を越えた瞬間に ジャンプを確定して次へ繰り上げる。LC 55 のループで回数を数えようとしない。ii.
nums[i] を「正確なジャンプ」と読んでしまう。i の値は上限 —
[i+1, i+nums[i]] のどこにでも着地できる。 だからこそ貪欲が成立する:到達可能な任意の i から、すべてのより短いジャンプも ただで使えるので、走行中の最大値さえあれば足り、選択肢の木を展開する必要はない。iii.
反射的に DP を選んでしまう。
DP でも解ける(
can[i] = ∃ j<i, can[j] ∧ j+nums[j] ≥ i)。 だが時間 O(N²)・空間 O(N) で、貪欲は O(N)・O(1)。メモリに収まる入力では DP も同じことを遅く確かめているだけ。「各歩の上限がそこの値で決まる」を 見たら、まず走査を疑う。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
区間スケジューリング
入力が区間のリストで「最大いくつまで重ならないように選べるか」を問う時に使う。終点でソートし、直近に採用した終点を始点が超えている区間を順に取る。 交換論法が「最早終了」が常に安全だと保証する。
終点でソート · LC 435 · LC 452
ジャンプゲーム
各要素がそこから動ける距離を決めるときに使う。左から右へ走査し、今までに到達可能な最遠の添字を保持する。 走査位置がその境界を越えたら、終点に到達できない。
最遠を追う · LC 55 · LC 45
ガスステーション
(環状または線形の)経路で、ある累積量が常に非負でなければならないときに使う。 実行中の合計がゼロを下回った瞬間に開始位置を次へリセット — 失敗する区間は妥当な開始接頭辞にはなり得ない。
失敗で即リセット · LC 134 · LC 53