55. 跳跃游戏

image.png

/*
分析：动态规划法的重点在于 分解。 我们分成两部分，一部分是可以到达的，一部分是不可以到达的。初始化，最右边的那个是终点始终是在可以到达的那部分。其左边部分是 带解集 不确定的 依次和可到达的 部分 比较 距离是否可达，即 可到达部分的最靠近待解集的那个的下标-待解集的值，若可以便将放入可到达的一部分，并且重新调整，
可到达部分的最靠近待解集的那个的下标，反之。依次 之后，看第一个（起点）是否可达。
*/


class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length<2)
            return true;
        int temp[] = new int[nums.length];
        int jing = nums.length-1;
        for(int i = nums.length-1-1;i>=0;i--){
            if(nums[i]>=(jing-i)){
                temp[i] = 1;
                jing = i;
                
            }else{
                temp[i] = 0;
            }
                           
           // System.out.println(Arrays.toString(temp));
        }
        
        if(temp[0] == 1)
            return true;
        else
            return false;
    }
}

leetcode