给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

解题思路：贪心

方式1. 状态转换

第一个下标是否能够跳到最后一个下标 等价于 最后一个下标是否能到达第一个下标。

我们将数组反向遍历，初始化时指针停留在倒数第二个下标，此时目标索引为最后一个下标。
如果倒数第二个下标能够跳到最后一个下标，那么也就意味着：如果到达第二个下标，就一定能够到达最后一个下标，因此可以将目标索引转换为倒数第二个下标。【状态转换】
● 那么如何判断某一索引能够跳到目标索引呢？→ nums[i] ≥ target_index - i
当我们遍历完数组，我们只需要判断第一个下标是否能够到达target_index（或者说第一个下标能否变成target_index）即可。

⭕ 把目标索引变得尽可能小，这就是贪心贪的地方！
因为如果某一个位置能够跳到最后一个下标位置，那么一定能够跳到比它跳数更小的位置（题目限定了最大跳数）！

class Solution {
    public boolean canJump(int[] nums) {
        int target_index = nums.length - 1;
        for(int i=target_index-1; i >= 0; i--){
            if(nums[i] >= target_index - i){
                target_index = i;
            }
        }
        return target_index == 0;
    }
}

方式2. 最大覆盖右界 ⭐

只关注当前可以被覆盖的区间。
我们设立一个覆盖区间的右界指针，右界往左（包括右界）的位置均可以到达！

我们顺序遍历这个区间的过程中，每遍历一个元素，都更新最大右界【贪心所贪，尽量覆盖更大的右界】，并判断它是否覆盖了最后一个位置。遍历指针i会一直往前移动，不会回头。（因为已经遍历过的位置，已经找过了最大右界）

● 成功条件：覆盖到了最后一个位置；
● 失败条件：已经到达最大右界，仍然没有覆盖到最后一个位置。

class Solution {
    public boolean canJump(int[] nums) {
        int max_index = 0;
        int i = 0;
        while(i < nums.length && i <= max_index){ // 只在覆盖范围内走
            int tmp = nums[i] + i; // 当前元素覆盖的范围
            if(tmp >= nums.length-1) return true; // 覆盖到最后一个元素
            if(tmp > max_index) max_index = tmp; // 每走一步都更新最大覆盖范围
            i++;
        }
        return false;
    }
}

方式3. 模拟（效率比较低）—— 倒过来思考，会有效率的提升，可参考方式1

class Solution {
    public boolean canJump(int[] nums) {
        boolean dp[] = new boolean[nums.length];
        dp[0] = true;
        for(int i=0; i<nums.length; i++){
            if(dp[i]){
                int tmp = i+nums[i];
                for(int j=i+1; j<nums.length&&j<=tmp; j++){
                    dp[j] = true;
                }
            }
        }
        return dp[nums.length-1];
    }
}