LeetCode(Dynamic Programming)Jump Game

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

思路：我们可以跟踪每一次跳跃时能够跳到的最远距离。这个问题的关键在于：（1）什么时候当前的位置不能跳到下一个位置；（2）什么时候最大的跳跃距离可以跳到最后一个点。

最远能到的距离可以这样来表示 : i + A[i].

Here is an example:

代码如下：

class Solution {
    public boolean canJump(int[] nums) {
        //如果只有1个或者0个数，则默认可以跳到最后的位置
    	if(nums.length<=1) {
    		return true;
    	}
    	int max=nums[0]; //max表示最远能到达的位置
        for(int i=0; i<nums.length-1; i++){
            //如果max<i 或者当max==i时num[i]==0肯定也不能跳到下一个点
            if(max<i || (max==i && nums[i]==0)) {
            	return false;
            }
            //如果可以跳过i，则更新能跳到的最远距离
            if(i+nums[i]>max) {
            	max=i+nums[i];
            }
            //如果最远距离大于等于最后一位的位置，则肯定可以跳到最后的位置
            if(max>=nums.length-1) {
            	return true;
            }
        }
        return false;
    }
}