题目

类型：动态规划

难度：中等

解题思路

贪心算法

依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 x，如果它在最远可以到达的位置的范围内，那么就可以从起点通过若干次跳跃到达该位置，因此可以用 x+nums[x] 更新 最远可以到达的位置。

在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，可以直接返回 True 作为答案。

反之，如果在遍历结束后，最后一个位置仍然不可达，就返回 False 作为答案。

代码

public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}