LeetCode题目:Jump Game II,一维动态规划,贪心

By | 2012 年 9 月 29 日

这个简单,只需要在Jump Game的基础上用一个int来记录最小跳跃次数就行了。

不过,贪心法可以解,O(n)扫一次就可以了,比DP好得多。因为这道题是最远跳到那么远,而不是只能跳到那么远。如果是后者,引入dp值得。



题目描述: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.)



贪心法,48ms过大集合

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



一维动态规划,1936ms过大集合

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. Pingback: LeetCode Jump Game II | bitJoy > code

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

    Reply
  3. robin

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

    Reply
  4. robin

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

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注