# Jump Game

## 1. 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

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution: Dynamic Programming.

f[i] = if it is possible to jump to i from the beginning.

f[i] = OR(f[j], j < i && j能够跳到i)

public boolean canJump(int[] A) {
if(A==null|| A.length==0){
return false;
}
boolean[] resultMap = new boolean[A.length];
resultMap[0] = true;
for(int i=1;i<A.length;i++){
for(int j=0;j<i;j++){
if(resultMap[j] && (i-j)<=A[j]){
resultMap[i] = true;
break;
}
}
}
return resultMap[A.length-1];
}

## 2. Jump Game II（问最小step数）

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.

Example
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.)

### Version 1. DP做法 不是最优 这道题可以用greedy

public int jump(int[] A) {
if(A==null||A.length==0){
return 0;
}
//minimum number of jumps from start to i
int[] resultMap = new int[A.length];
resultMap[0] = 0;
for(int i=1;i<A.length;i++){
resultMap[i] = -1;
for(int j=0;j<i;j++){
if(resultMap[j]>=0 && (i-j)<=A[j]){
resultMap[i] = resultMap[j]+1;
break; //这里包含Greedy思想，最先出现的一定是最优的
}
}
}
return resultMap[A.length-1];
}

### Version 2. Greedy (O(n) One pass)

public int jump(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int start = 0, end = 0, jump = 0;
while (end < A.length) {
jump++;
int furthest = end;
for (int i = start; i <= end; i++) {
if (A[i] + i > furthest) {
furthest = A[i] + i;
}
}
start = end + 1;
end = furthest;
if (start > end) {