45. Jump Game II ～～～～～～～～仔细体会方法2

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.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

Note:

You can assume that you can always reach the last index.

A:

First, try the one-by-one step to move further.

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> DP(n,INT_MAX); //DP to find each minimum jump
        DP[0] =0;
        for(int i = 0;i<n;i++){
            for(int j = i+1;j <= min(n-1, i+nums[i]); j++){
                DP[j] = min(DP[j], DP[i] + 1 );
            }
        }
        return DP[n-1];
    }
};

***************Exceed the time limit **************

Each round, we found the right most reachable position, and update all positions before it.

这个应该算是DP问题吧.
思路 来自 问题1：  i_th position 用k步的时候，之前的节点，都可以在不超过k步内达到。
因此，先建立minJump的一些节点，如果然后，没有按照 A[i] 跳到的地方，就直接copy 后面的节点的step 值。   这样，一个while loop就完了。

这样之后， 再update后面的minJump。 哎呀，比较乱，还是看代码吧。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> DP(n, INT_MAX);
        DP[0] = 0;
        int start = 0,end = 0;
        while(start < n-1){
            int rightMost = -1;
            for(int i = start; i<= end; i++){                
                rightMost = min(n-1,  max(rightMost, i + nums[i]  )  );
            }
            // assign the minStep for next few available position
            for(int i = end+1; i<= rightMost; i++){
                DP[i] = DP[start]+1;
            }
            start = end+1;
            end = rightMost;
        }
        return DP[n-1];
    }
};

---------------------------------3 rd pass-------------------------same idea, but instead of allocating an Array, we use constant space.----------------------------------------

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int curStart = 0, curEnd = 0; // current level of start and end
        int res = 0;
        while(curEnd < n-1){ // use curEnd NOT curStart
            int mostRight = -1;
            res++;
            // from curStart till most recent,
            for(int i =curStart;i<= curEnd;i++){
                mostRight = max(mostRight, i + nums[i]);
            }
            mostRight = min(mostRight, n-1);
            curStart = curEnd +1;
            curEnd = mostRight;
        }
        return res;
    }
};

Mistakes:
1: 刚开始的思路错误。 而没有借助problem 1的思路。 搞得晚上1点多到2点多。也没弄完这道题。哎， 早点儿睡觉啊，Tiger

Learned: