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.
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
解题思路：本题给的提示是Greedy，但是Greedy很明显存在重复计算的问题啊？看了网上的一些解法，很明显没有考虑到重复计算的去除问题。
重复计算的产生：如下图，在位置A,B,C中都会发现D是可以选择的节点，所以会在D位计算3次。
根据动态规划中的技巧，巧妙的用一个数据来存储计算中的中间值，程序算法复杂度O(n)，个人感觉比贪心算法好多了。
public class Solution {
/**
* @param A: A list of integers
* @return: The boolean answer
*/
public boolean canJump(int[] A) {
if(A.length <= 1)
return true;
boolean[] step = new boolean[A.length];
step[0] = true;
for(int i=0;i<A.length;i++){
if(step[i] == true && A[i]>0){
for(int j=i+1;j<=i+A[i] && j < A.length;j++)
step[j] = true;
}
}
return step[step.length-1];
}
}
Jump Game II
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.
Your goal is to reach the last index in the minimum number of jumps.
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2.
(Jump 1 step from index 0 to 1, then 3 steps
to the last index.)
解题思路： 同样的，不使用贪心算法实现。
public class Solution {
/**
* @param A: A list of lists of integers
* @return: An integer
*/
public int jump(int[] A) {
if(A.length==1)
return 0;
boolean[] step = new boolean[A.length];
step[0] = true;
int n = 0;
while(true){
n++;
for(int i=A.length-1;i>=0;i--){
if(step[i]){
for(int j=i+A[i];j>i;j--){
if(j >= A.length-1)
return n;
step[j] = true;
}
}
}
}
}
}