LeetCode Jump Game：貪心判斷能否到達末尾

問題描述

數組 A 中每個元素代表在該位置最大跳躍長度。初始站在索引 0，判斷能否到達最後一個索引。

貪心策略一：正向掃描維護最遠可達位置

bool canJump(vector& nums) {
    int reach = 0, n = nums.size();
    for (int i = 0; i < n && i <= reach; ++i)
        reach = max(reach, i + nums[i]);
    return reach >= n-1;
}

貪心策略二：逆向掃描維護最左可達位置

bool canJump(vector& nums) {
    int last = nums.size() - 1;
    for (int i = last - 1; i >= 0; --i)
        if (i + nums[i] >= last) last = i;
    return last == 0;
}

複雜度與優勢

• 時間 O(n)，空間 O(1)。
• 比 DP O(n²) 或 BFS 高效得多。
• 正向版直觀易懂，逆向版代碼更短。

擴展：Jump Game II（最少跳躍次數）

同樣貪心：維護當前層最遠可達 curEnd 和下一層最遠可達 farthest，遍歷時更新，到達 curEnd 時步數+1並更新 curEnd=farthest。