public class JumpGame {

	public static boolean canJump(int[] a)

	{

		int reach = 0;//代表最多能到达的位置

		int i = 0; //代表每次走一步能到达的位置

		for(; i < a.length && i <= reach; i ++)

		{

			reach = Math.max(reach, i + a[i]);

		}

		return i == a.length;

	}

	public static void main(String[] args) {

		int[] a = {2,3,1,1,4};

		System.out.println(canJump(a));

	}

}

public static int canJump2(int[] a)

	{

		int pre[] = new int[a.length];//记录到达i的前一位置

		int reach = 0;

		for(int i = 0; i < a.length; i ++)

		{

			if(i+a[i] > reach)

			{

				//reach+1 - i+a[i]的前一位置是i

				for(int j = reach + 1; j <= i + a[i] && j < a.length; j ++)

				{

					pre[j] = i;

				}

				reach = i + a[i];

			}

		}

		int count = 0;

		int k = a.length -1;

		while(k > 0)

		{

			k = pre[k];

			count ++;

		}

		return count;

	}