---
title: "55. Jump Game"
url: "https://laigary.com/interview/coding/55-jump-game"
type: "note"
section: "coding"
date: "2023-01-28"
updated: "2026-07-27"
tags: ["Greedy", "Dynamic Programming", "Array"]
---

# 55. Jump Game

[55\. Jump Game](https://leetcode.com/problems/jump-game/)

從起點開始，看有哪些座標可以去，選定一個座標後繼續走下去，看看能不能到達終點（超時）

```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        @cache
        def dp(i):
            if i == len(nums) - 1:
                return True
            for j in range(i + 1, min(i + nums[i] + 1, len(nums))):
                if dp(j):
                    return True
            return False
        
        return dp(0)
```

上面這個方法存在著一個小地方可以優化，那就是每一次我們要走的時候，都應該要先朝能走得最遠的方向去探索，但是理論的時間複雜度還沒有被優化。

```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:    
        def traverse(i):
            if i == len(nums) - 1:
                return True
            farestPosition = min(i + nums[i] + 1, len(nums))
            for j in reversed(range(i+1, farestPosition)):
                if traverse(j):
                    return True
            return False
        return traverse(0)
```

上面的解法存在這一個問題，那就是在探索的路程中，有些節點可能會一直不斷的重複探索，像是題目中的第二個範例，第一開始的起點探索完之後，我們其實早就知道座標 1, 2 怎麼走都會走到零，當我們再一次走到 2 的時候，應該就要直接知道不要再去走了。

```text
[3,2,1,0,4]
```

## 動態規劃

所以我們需要記錄座標是不是走過了，但是如果說我們只記錄座標是不是走過了，是不是還少了點什麼？因為一個走過的座標，還要去考量他是不是有用的座標能夠幫我們繼續往下走。

這樣看起來好像有四個狀態：走過 vs 沒有走過和有用 vs 沒有用。不過事實上只有三種，因為沒有走過的座標，我們一定不知道有沒有用，只有走過的座標才會知道有用或是沒有用，所以如果知道一個座標是有用或是沒有用的話，我們就知道這個座標一定是走過的。

這個觀念有了後，就可以建立一個表幫助我們記錄走過的路徑，這個表需要的記憶體看陣列的大小，一開始都是沒有造訪過的，用 None 來表示。那最後一個點一定是有用的，因為那是我們的終點，所以先將其記錄成有用的。

```python
memo = [None] * len(nums)
memo[-1] = True
```

至此，我們就完成了時間複雜度在 $O(n^2)$ 的解法。

```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        memo = [None] * len(nums)
        memo[-1] = True
        def traverse(i):
            # 如果我們已經知道此點是造訪過的，那我們就直接回傳結果
            # 不用再判斷 i 是否等於 len(nums) - 1 是因為初始化
            # 時，已經將結果存入了。
            if memo[i] is not None:
                return memo[i]
            farestPosition = min(i + nums[i] + 1, len(nums))
            for j in reversed(range(i+1, farestPosition)):
                if traverse(j):
                    # 更新這個點有助於往前
                    memo[i] = True
                    return memo[i]
            # 如果上面的路都沒有幫助，那這個點就是沒有意義的點。
            memo[i] = False
            return memo[i]
        return traverse(0)
```

## 貪心：只記「能到的最遠處」

上面的 DP 問的是「**從 i 出發**能不能到終點」，所以每個座標都得往後把能跳的範圍試一遍，$O(n^2)$ 跑不掉。

換個方向問：「**從起點出發**目前最遠能碰到哪裡？」這個問題只需要一個變數。

一路從左掃到右，維護 `farthest`：

- 如果 `i > farthest`，代表這一格根本走不到，前面已經斷掉了，直接 False
- 否則更新 `farthest = max(farthest, i + nums[i])`

走完整個陣列都沒斷掉，就代表終點碰得到。

```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        for i, num in enumerate(nums):
            if i > farthest:
                return False
            farthest = max(farthest, i + num)
        return True
```

拿 `[3,2,1,0,4]` 走一次：

| i | nums[i] | i + nums[i] | farthest |
|---|---|---|---|
| 0 | 3 | 3 | 3 |
| 1 | 2 | 3 | 3 |
| 2 | 1 | 3 | 3 |
| 3 | 0 | 3 | 3 |
| 4 | 4 | — | `4 > 3` → False |

走到 `i = 4` 的時候 `4 > 3`，前面四格誰都跳不過那個 0，直接結束。

### 貪在哪裡

貪心的動作是：**把「怎麼走到 i」的所有路徑全部丟掉，只留一個 `farthest`。**

敢這樣丟，是因為這題的可達集合有一個很強的性質：

**可以到達的座標永遠是一段連續的前綴區間 `[0, farthest]`，中間不會有洞。**

用歸納法看：一開始只有座標 0 可達。當我們走到某個可達的 `i`，它一步可以跳到 `i + 1` 到 `i + nums[i]` 的**每一格**（題目說的是「最多」跳 `nums[i]` 步，不是剛好跳那麼多），所以新增的也是一段連續區間，接在舊區間後面，不可能產生洞。

既然沒有洞，「可不可達」就只剩一個數字要記 —— 區間的右端點。這也是為什麼 `i > farthest` 可以直接回 False：`i` 已經掉出區間，而區間右邊不可能再有孤島等著我們。

DP 版本記的是「從每個點出發能不能到終點」（$n$ 個布林值），貪心版本記的是「從起點出發能到多遠」（1 個整數）。**同一件事換個方向問，狀態就從 $O(n)$ 塌成 $O(1)$，DP 也就退化成一次掃描。**

## 補充

**同樣是「維護一個最遠可達」的題**：[1306. Jump Game III](/interview/coding/1306-jump-game-iii)（只能跳固定的 `±arr[i]`，區間性質沒了，只能乖乖 BFS/DFS）。這個對照很值得看 —— 它說明 55 能貪心不是因為它叫 Jump Game，而是因為「最多跳 k 步」這個規則造出了連續區間。

更多貪心的判斷方式見 [Greedy 模板](/interview/coding/greedy-template)。

## 複雜度

- 時間 $O(n)$ — 掃過陣列一次，每格 $O(1)$
- 空間 $O(1)$ — 只有一個 `farthest`

其中 $n$ 是陣列長度。作為對照，上面的 DP 版本是 $O(n^2)$ 時間、$O(n)$ 空間 —— 每個座標都要往後掃一遍它能跳到的範圍。