跳跃游戏

import java.util.*;


public class Solution {
    /**
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean canJump (int[] nums) {
        // write code here
        // 当前可到达的最远位置
		int manLen = 0;
		for (int i = 0; i < nums.length; i++) {
			if (manLen >= i) {
				int tempLen = i + nums[i];
				manLen = Math.max(manLen, tempLen);
			}
			if (manLen >= nums.length - 1){
				return true;
			}
		}
		return false;
    }
}

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return false;
        }
        int k = 0;
        for (int i = 0; i < A.length; i++) {
            if (k < i) {
                return false;
            }
            k = Math.max(k, i + A[i]);
        }
        return true;
    }
}

public class Solution {
public static boolean canJump(int[] A) {
int n=A.length;
int i=0;
int step =A[0];
if(step==0&&n==1)
return true;
while(i0)
{
i=i+step;
if(i>=n-1)
return true;
else
step=A[i];
}
else
return false;
}
return true;
}
}

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

public class Solution {
    public boolean canJump(int[] A) {
		boolean[] flag = new boolean[A.length];
		flag[0] = true;
		for (int i = 0; i < A.length; i ++) {
			if(flag[i]) {
				int maxPosition = Math.min(i + A[i], A.length - 1);
				for (int j = i + 1; j <= maxPosition; j ++) {
					flag[j] = true;
				}
			}
			if(flag[A.length - 1]) return true;
		}
		return false;
	}
}

Idea is to work backwards from the last index. Keep track of the smallest index that can "jump" to the last index. Check whether the current index can jump to this smallest index.

bool canJump(int A[], int n) { int last=n-1,i,j; for(i=n-2;i>=0;i--){ if(i+A[i]>=last)last=i;
    } return last<=0;
}