class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> f(n);
        f[0] = 1;
        for (int i = 0, end = nums[0]; i <= end; i ++) {
            if (i == n - 1) return true;
            end = max(end, i + nums[i]);
        }
        return false;
    }
};

class Solution {
public:
    // DP
    /*
    bool canJump(vector<int>& nums) {
        int pos = 0;
        int n = nums.size();
        for (int i = 0; i <= pos; i ++) {
            if (i + nums[i] >= n - 1) {
                return 1;   
            }
            else {
                pos = max(pos, i + nums[i]);
            }
        }
        return false;
    }
    */

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

// 2024-03-11 贪心做法