Jump Game（LeetCode #55）

nums[i] は添字 i から前へ跳べる最大距離です。最後の添字へ到達できるかを調べます。貪欲法は最遠到達境界 reach 一つで左から走査し、時間 O(n)、空間 O(1)。跳躍長は非負です。

到達済み i からは 1 から nums[i] の任意距離を選べ、最大を必ず跳ぶわけではありません。到達可能な添字は 0 からの連続区間なので、右端だけで表せます。落下位置ごとの DP や明示的な辺の探索は最悪 O(n²)、記憶なしの試行は多数の経路を繰り返し得ます。

Jump Game の仕組み

各添字で二つをこの順に実行します。

最初に i > reach なら False。走査が到達前線を越えています。この時、起点にできる前の位置はすべて処理済みで、合わせても最遠は reach です。穴の先に大きい値があっても、そこへ立てないので使えません。

次に reach = max(reach, i + nums[i])。i が到達可能と確認済みなので、そこから i + nums[i] までの連続した着地点を加えられます。

具体的な道筋や実際の一跳躍は保存しません。到達可否には連続区間の右端で足ります。距離を必ずぴったり跳ぶ規則や着地禁止位置を加えると集合に穴ができ、この圧縮をそのまま使えません。実際の到達状態を表せる方法が必要です。

更新を先にすると、到達していない位置も貢献します。非負の nums[i] では更新後に必ず reach ≥ i となり、検査が失敗せず全入力を誤って受け入れます。

最後まで通れば末尾を含む全添字が検査を通り、True です。

判定をステップで追う

既定は nums = [2, 3, 1, 0, 4]。零が必ずしも障害ではないと示します。

1. i = 0：0 ≤ 0。1 と 2 へ跳べ、reach = max(0, 0 + 2) = 2。
2. i = 1：1 ≤ 2。reach = max(2, 1 + 3) = 4 で末尾を含む。ここでは後の状態を見るため続ける。
3. i = 2：通過。2 + 1 = 3 は 4 を超えず、前線不変。
4. i = 3：零なので max(4, 3 + 0) = 4。拡張しなくても 3 は範囲内で失敗しない。
5. i = 4：4 ≤ 4 で末尾に到達。更新は reach を 8 へ進めるが、能力の上界は配列外でもよい。終了して True。

Every path funnels の [3, 2, 1, 0, 4] では、0 が 3、1 の 1 + 2 = 3、2 の 2 + 1 = 3 も同じ場所までです。添字 3 の零は広げられず、i = 4 で 4 > 3、False。最後の 4 は届かないので自分を救えません。

緑のレールが reach、橙の弧が各セルの最遠提供位置です。弧が前線を越える時だけレールを伸ばします。初拡張では全許可着地点を開いて示し、新区間を旧レールと合わせ、連続性を証明します。失敗例は三本の最遠弧が同じ位置に集まり、赤破線が穴を示します。

時間・空間計算量

各添字を一回検査・更新します。reach ≥ n − 1 で早期 True にしても最悪界は同じです。アニメーションは、既定の零も到達範囲内なら通れると示すため最後まで進みます。

境界ケース

• 一要素、[0] も含む：すでに末尾で、跳ばず True。
• 先頭零で後続あり：[0, 3] は reach が 0 のまま、i = 1 で失敗。
• 末尾越え：既定は n = 5、reach = 8。切り詰め不要で、走査添字は範囲内。
• 穴の位置：最初の失敗は reach + 1。それ以前は前線内で通る。

よくある間違い

• 零を見ただけで失敗にする。 前線がそこで止まり、まだ目的地が先なら問題です。既定は零があっても成功します。
• 検査前に更新する。 未到達セルで境界を広げ、検査が常に通ります。
• 毎回最大距離を跳ぶ。 [2, 3, 0, 1, 4] は 0 から二つ跳ぶと零ですが、一つで値 3 へ行けば末尾へ届き、正解は True。
• 可否のために全着地関係を保存する。 一般 BFS は正しくても、明示的な辺展開は最悪 O(n²)。この「最大まで」の規則なら前線一つで十分です。
• 最後の値に依存する。 そこから跳ぶ必要はなく、そこへ着くのが目標です。大きくても手前の穴を埋められません。