注意，贪心法是错误的！贪心法在lintCode能够AC,leetCode不能AC。因为这道题是一道最优题，而贪心法不能保证最优
题意：
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
样例：
A = [2,3,1,1,4]，返回 true.
A = [3,2,1,0,4]，返回 false.
注意事项：
这个问题有两个方法，一个是贪心和 动态规划。
贪心方法时间复杂度为O（N）。
动态规划方法的时间复杂度为为O（n^2）。
我们手动设置小型数据集，使大家可以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次
1.贪心法
正如注意事项所说的，这道题有种解法。我们先来看看贪心法。
(1).解题思路
贪心法的思路非常的简单，那就是，当跳到一个位置上，我们在当前位置到当前位置能达到的最大位置范围找到最大值，如果最大值的index + 最大值大于当前位置能达到的最大位置的index，那么选择跳到最大值的index去，反之则跳到当前位置能达到的最大位置。
(2).代码
public boolean canJump(int[] A) {
//当前跳的位置
int index = 0;
while (index < A.length - 1) {
if (A[index] == 0) { // 如果当前的值为0，就跳不动了，那么肯定为false
return false;
}
//最大值
int max = Integer.MIN_VALUE;
//最大值的index
int maxIndex = 0;
for (int i = index + 1; i < A.length && i < index + A[index]; i++) {
if (max < A[i]) {
max = A[i];
maxIndex = i;
}
}
//如果最大值和最大值的index的和大于当前index + A[index]
//表示下次调到最大值的位置上去
if (maxIndex + max > index + A[index]) {
index = maxIndex;
} else {
//反之则跳到index + A[index]
index = index + A[index];
}
}
return true;
}
2.动态规划
(1).解题思路
说实话，自己的动态规划还是很弱，有待加强！
动态规划的思路相对来说要复杂一下，我们这里分两种情况来讨论
第一步,定义一个dp一维数组，用来记录每个位置是否能够达到终点。比如，dp[i],表示在i位置，是否能够跳到终点，如果能，为true；反之为false。
第二步，dp[i]是否能够跳到终点，这里主要分为两种情况：
1.如果当前位置可以直接跳到终点，也就是说i + A[i] >= A.length() - 1,那么直接让dp[i] 为true就行了。
2.如果当前位置不能直接跳到终点，但是可以借助其他位置跳到终点，那么dp[i]也为true。这里设置为true有两个条件，假设它借助j位置，首先dp[j]必须true，其次它必须能够跳到j位置，也就是说i + dp[i] >= j。
经过简单的分析，应该能够理解到这个解法的思路吧！！！
(2).代码
public boolean canJump(int[] A) {
//dp数组表示当前的位置是否能够跳到最后
boolean dp[] = new boolean[A.length];
//默认最后一个为true
dp[A.length - 1] = true;
for (int i = A.length - 2; i >= 0; i--) {
//如果当前位置能够直接跳到终点，直接设置为true
if (i + A[i] >= A.length - 1) {
dp[i] = true;
}
for (int j = i; j < A.length - 1; j++) {
//设置为true的条件是：
//1.借助的j点必须为true
//2.必须能够跳到j点来(i + A[i] >= j)
if (dp[j] && i + A[i] >= j) {
dp[i] = true;
}
}
}
return dp[0];
}
