LeetCode 筆記：跳躍遊戲 - 貪心與動態規劃雙解法

問題描述

給定一個非負整數陣列，初始位於第一個索引。陣列中每個元素代表在該位置可以跳躍的最大長度。判斷是否能到達最後一個索引。

範例：

• A = [2,3,1,1,4] → 返回 true
• A = [3,2,1,0,4] → 返回 false

解題分析

核心在於維護「目前能到達的最遠位置」。遍歷陣列時，若當前索引超過最遠可達位置，則無法繼續前進，返回 false；否則持續更新最遠可達位置。若最遠位置 ≥ 最後索引，即可到達終點。

貪心算法實現（推薦）

class Solution {
public:
    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;
    }
};

動態規劃實現

class Solution {
public:
    bool canJump(vector& nums) {
        int n = nums.size();
        vector dp(n, 0); // dp[i] 表示到達 i 後剩餘步數
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(dp[i-1], nums[i-1]) - 1;
            if (dp[i] < 0) return false;
        }
        return dp[n-1] >= 0;
    }
};

複雜度比較

核心總結

貪心策略的關鍵在於「始終保持 maxReach 為當前能到達的最遠位置」，這是一種典型的區間覆蓋思維。