# LeetCode题目：Jump Game II，一维动态规划，贪心

By | 2012 年 9 月 29 日

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];
}
};
```

## 9 thoughts on “LeetCode题目：Jump Game II，一维动态规划，贪心”

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

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

3. robin

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

4. zjsxzy

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