# LeetCode题目：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.
For 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.)

```class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int minstep = 0;
int ldist = 0;
int hdist = 0;
if (n == 1) return 0;
while(ldist <= hdist) {
++minstep;
int lasthdist = hdist;
for(int i = ldist; i <= lasthdist; ++i) {
int possibledist = i + A[i];
if (possibledist >= n-1)
return minstep;
if (possibledist > hdist) {
hdist = possibledist;
}
}
ldist = lasthdist + 1;
}
return 0;
}
};
```

```class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 1)
return 0;
const int noWay = n + 1;
int *jumps = new int[n];
jumps[n-1] = 0;
for(int i = n - 2; i >= 0; -- i) {
int lenJump = A[i];
int minJumps = noWay;
for(int j = i + 1; j <= i + lenJump && j < n; ++ j) {
if(jumps[j] + 1 < minJumps)
minJumps = jumps[j] + 1;
}
jumps[i] = minJumps;
}
return jumps[0];
}
};
```

## “LeetCode题目：Jump Game II，一维动态规划，贪心”上的9条回复

Hong Jiang说：

function minJump(Q, len) {

if (len==0)
return;

var index = 0;
var i = len-1;
while (i>= 0) {
if (Q[i] >= (len-i)) {
index = i;
}
i–;
}
M.push(index);
minJump(Q, index);
}

var Q = [2,3,1,1,4];
var M = [];
var len2 = Q.length -1;
minJump(Q, len2);

console.log(“The minimum number of jumps to reach the last index is ” + M.length);
console.log(M.reverse());

“因为这道题是最远跳到那么远，而不是只能跳到那么远。如果是后者，引入dp值得。” 比如输入是A = [2,3,1,1,4]，题目的意思是让我求得到达最后一个元素的最少步子,对么？按照我的理解，那这里最后一个元素就是数组的A[A.length-1]，但是这样理解题意，就只能用dp，每次提交都是超时的…

zjsxzy说：

hujuyun说：