解題說明
Jump Game II（跳躍遊戲 II）
題目描述：給定一個非負整數陣列 nums，初始位置在索引 0，nums[i] 表示在第 i 格最多能往前跳幾步。保證一定能到達最後一格，求到達最後一格的最少跳躍次數。
解題思路：
採用貪心 BFS 分層的思路，類似 BFS 的「層」概念：每一跳代表一層，每一層包含用相同跳躍次數能到達的所有位置。
關鍵觀察：
- 維護當前跳可到達的視窗
[l, r]（代表「本層」的範圍） - 遍歷視窗內所有位置，計算從這些位置出發能到達的最遠位置
farthest - 當我們走到視窗右端 r，代表本層所有可能都已考慮，必須再跳一次
- 新視窗變為
[r+1, farthest]，跳躍次數加 1
關鍵細節：
- 若
r >= n-1（最後一格已在視窗內），直接返回當前跳躍次數，無需再跳 - 遍歷時只需到
n-2（不需要從最後一格再跳出去）
為何貪心正確？每次我們選擇最遠可達位置，等同於 BFS 中一次性展開整層節點，確保在最少跳躍次數下抵達終點。
C++ 解法
複雜度分析
時間複雜度：O(n) — 雖然寫作雙層迴圈形式，但內層迴圈的指標 l 只會單調遞增，每個索引只會被遍歷一次，整體為 O(n)。
空間複雜度：O(1) — 只使用常數個輔助變數（jumps、l、r、farthest），無需額外資料結構。
虛擬碼
1. If n == 1, return 0 (already at destination)
2. Initialize jumps=0, l=0, r=0, farthest=0
3. While r < n-1 (haven't reached last index yet):
a. For each position i in [l, r]:
farthest = max(farthest, i + nums[i])
b. l = r + 1 (advance window start)
c. r = farthest (advance window end to farthest reachable)
d. jumps += 1
4. Return jumps其他解法
動態規劃 O(n²)：定義 dp[i] 為到達第 i 格的最少跳躍次數。對每個 i，枚舉所有能跳到 i 的位置 j（即 j + nums[j] >= i），dp[i] = min(dp[j] + 1)。正確但時間複雜度為 O(n²)，不如貪心高效。
貪心精簡版（單指標）O(n)：不維護視窗 [l, r]，僅用 curEnd（當前跳躍層的右端）和 farthest（可達最遠），當 i == curEnd 時跳躍次數加一並更新 curEnd = farthest。與視窗版本等價，但程式碼更簡潔，只需一層迴圈。
延伸思考
- 若
nums[i]可以是負數（即某些格子強制向後退），問題是否仍有貪心解，還是必須改用 DP？ - Jump Game I（LeetCode 55）只問能否到達終點，Jump Game II 問最少步數——兩題的貪心策略有何本質區別？
- 若每次跳躍的代價不是固定 1，而是
cost[i]，如何求到達終點的最小總代價？