Jump Game II

解题思路：

最值问题，第一想到的就是动态规划。用d[i]记录从0到i最小的步数，则d[i]=min(d[k]+1)，当中k是全部可以到达i的下标。最開始，我用一个vector数组记录全部可以到达自身的下标，代码例如以下：

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        if(len<2){
            return 0;
        }
        int d[len];
        d[0] = 0;
        vector<int> pre[len];
        for(int i=1; i<=nums[0] && i<len; i++){
            pre[i].push_back(0);
        }
        for(int i=1; i<len; i++){
            d[i] = INT_MAX;
            for(int j=0; j<pre[i].size(); j++){
                d[i] = min(d[i], d[pre[i][j]] + 1);
            }
            for(int j=i+1; j<=(nums[i] + i) && j<len; j++){
                pre[j].push_back(i);
            }
        }
        return d[len-1];
    }
};

时间复杂度为O(n*n)，空间复杂度为O(n*n)。超时错误。

后经过改进。不须要记录前驱节点，代码例如以下，空间复杂度变为O(n)。但时间复杂度仍为O(n*n)，产生超时错误。

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        if(len<2){
            return 0;
        }
        int d[len];
        for(int i=1; i<len; i++){
            d[i] = INT_MAX;
        }
        d[0] = 0;
        for(int i=0; i<len; i++){
            for(int j=i+1; j<=(nums[i]+i) && j<len; j++){
                d[j]=min(d[j], d[i] + 1);
            }
        }
        return d[len-1];
    }
};

水中的<。)#)))≦给我们一个非常好的解法：http://fisherlei.blogspot.com/2012/12/leetcode-jump-ii.html，採用贪心算法，记录第k步最多可以走，且对第k+1步有影响的范围[Left, Right]，每走一步，left变成right+1。right变成[left, right]区间内走一步最远的下标。这里与上述方法的根本差别就是left=right+1，而非left=left+1，这样可以降低非常多计算。

由于[left+1, right]已经在[left, right]时已经计算过了。

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        int left = 0;
        int right = 0;
        int count = 0;
        while(right<len-1){
            count++;
            int mostRight = right;
            for(int i=left; i<=right; i++){
                mostRight = max(mostRight, i+nums[i]);
                if(mostRight>=len - 1){
                    break;
                }
            }
            left = right + 1;
            right=mostRight;
            if(right<left){
                return -1;
            }
        }
        
        return count;
    }
};