LeetCode 55. 跳跃游戏

55. 跳跃游戏

解题思路

“从后往前”思考

• 最后一个位置就是终点，问题转换为 倒数第二个位置能否到达终点?
• 从倒数第二个位置开始检查，逐步向前递推
• 如果最后目标位置变为0，那么从位置0到最后一个位置是可达的

参考代码

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