LeetCode 55 Jump Game：動態規劃與貪心兩種 O(N) 解法

問題描述

非負整數數組 `nums`，初始位於索引 0。每個元素代表該位置**最大**跳躍長度。判斷能否到達最後一個下標。

方法一：動態規劃（維護最遠可達）

遍歷數組，維護 `maxReach` = 當前能到達的最遠下標。
若 `i > maxReach` → 無法到達位置 i → 返回 false。
否則 `maxReach = max(maxReach, i + nums[i])`。
若 `maxReach >= n-1` → 提前返回 true。
時間 O(N)，空間 O(1)。

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

方法二：貪心（反向檢查「吸收態」）

從右向左，維護 `leftmostGood` = 最左邊能到達終點的位置。
初始 `leftmostGood = n-1`。
對 i 從 n-2 遞減至 0：若 `i + nums[i] >= leftmostGood`，則 i 也能到達終點，更新 `leftmostGood = i`。
最後檢查 `leftmostGood == 0`。
同樣 O(N) O(1)。

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

對比

兩種方法本質相同，均為線性掃描，面試推薦反向貪心代碼更優雅。