# 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个回复

1. 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());

2. 好吧..我看懂题意了…之前的理解是，到达数组的A[A.length-1]需要的最少步子，
正确的意思是到达数组最远的元素的最少步子..贪心就可以了…：）

1. 恩，我开始也想错了，就用了dp。后来仔细看题目才发现其实贪心就ok了。

3. 博主，我在做这道题的时候….用dp总是超时，看了这篇博文后，发现自己好像理解错了，你说的这句话,
“因为这道题是最远跳到那么远，而不是只能跳到那么远。如果是后者，引入dp值得。” 比如输入是A = [2,3,1,1,4]，题目的意思是让我求得到达最后一个元素的最少步子,对么？按照我的理解，那这里最后一个元素就是数组的A[A.length-1]，但是这样理解题意，就只能用dp，每次提交都是超时的…

4. zjsxzy说道：

动态规划优化一下跑的就很快了，一种优化44ms，另一种112ms

1. 恩，但是总体看来，贪心更适合解这道题，总的代价小些。

5. hujuyun说道：

一维动态规划那个好像还是超时了吧

1. 差点超时，1936ms，服务器抖一抖就超了。