55. Jump Game

──────────────────────────────────────────────────────────────────────

55. Jump Game

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

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)

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

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 的時候，應該就要直接知道不要再去走了。

[3,2,1,0,4]

動態規劃

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

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

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

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

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

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])

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

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（只能跳固定的 ±arr[i]，區間性質沒了，只能乖乖 BFS/DFS）。這個對照很值得看 —— 它說明 55 能貪心不是因為它叫 Jump Game，而是因為「最多跳 k 步」這個規則造出了連續區間。

更多貪心的判斷方式見 Greedy 模板。

複雜度

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

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