# Jump Game II

## Question

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


## 题解(自顶向下-动态规划)

1. State: f[i] 从起点跳到这个位置最少需要多少步
2. Function: f[i] = MIN(f[j]+1, j < i && j + A[j] >= i) 取出所有能从j到i中的最小值
3. Initialization: f[0] = 0，即一个元素时不需移位即可到达

### C++ Dynamic Programming

class Solution {
public:
/**
* @param A: A list of lists of integers
* @return: An integer
*/
int jump(vector<int> A) {
if (A.empty()) {
return -1;
}

const int N = A.size() - 1;
vector<int> steps(N, INT_MAX);
steps[0] = 0;

for (int i = 1; i != N + 1; ++i) {
for (int j = 0; j != i; ++j) {
if ((steps[j] != INT_MAX) && (j + A[j] >= i)) {
steps[i] = steps[j] + 1;
break;
}
}
}

return steps[N];
}
};


### 源码分析

if ((steps[j] != INT_MAX) && (j + A[j] >= i)) {
steps[i] = steps[j] + 1;
break;
}


## 题解(贪心法-自底向上)

### C++ greedy from bottom to top, bug version

class Solution {
public:
/**
* @param A: A list of lists of integers
* @return: An integer
*/
int jump(vector<int> A) {
if (A.empty()) {
return -1;
}

const int N = A.size() - 1;
int jumps = 0;
int last_index = N;
int min_index = N;

for (int i = N - 1; i >= 0; --i) {
if (i + A[i] >= last_index) {
min_index = i;
}

if (0 == min_index) {
return ++jumps;
}

if ((0 == i) && (min_index < last_index)) {
++jumps;
last_index = min_index;
i = last_index - 1;
}
}

return jumps;
}
};


### C++ greedy, from bottom to top

class Solution {
public:
/**
* @param A: A list of lists of integers
* @return: An integer
*/
int jump(vector<int> A) {
if (A.empty()) {
return 0;
}

const int N = A.size() - 1;
int jumps = 0, end = N, min_index = N;

while (end > 0) {
for (int i = end - 1; i >= 0; --i) {
if (i + A[i] >= end) {
min_index = i;
}
}

if (min_index < end) {
++jumps;
end = min_index;
} else {
return -1;
}
}

return jumps;
}
};


### 源码分析

            for (int i = 0; i != end; ++i) {
if (i + A[i] >= end) {
min_index = i;
break;
}
}


## 题解(贪心法-自顶向下)

### C++

/**
* http://www.jiuzhang.com/solutions/jump-game-ii/
*/
class Solution {
public:
/**
* @param A: A list of lists of integers
* @return: An integer
*/
int jump(vector<int> A) {
if (A.empty()) {
return 0;
}

const int N = A.size() - 1;
int start = 0, end = 0, jumps = 0;

while (end < N) {
int farthest = end;
for (int i = start; i <= end; ++i) {
if (i + A[i] >= farthest) {
farthest = i + A[i];
}
}

if (end < farthest) {
++jumps;
start = end + 1;
end = farthest;
} else {
return -1;
}
}

return jumps;
}
};