045 - Jump Game II

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.)
Hide Tags
Array Greedy

沿着第一题的思路，不难得到 greedy 的解法：
加入一个计数，像回溯一样，进去之前 + 1， 进去之后 -1；
到达终点就更新最小步骤即可。
性能上并不是很理想，一开始是 76 ms，后来过滤了 count 大于已知的最小次数的情况，降到了 36 ms，
但还是不太好，又加上了提前返回的条件（如果最小次数已经是当前位置的最优解就没必要再看其他的了），
但是降到了 28 ms 就再也提高不了了。

跑去看别人的帖子，果然有线性的解法（话说这位同学的图文解释真的很不错啊）：
基本思想是，记住两个位置，
一个是在当前点上可以到达的最远距离，一个是当前已经在到达范围内的最远位置，我分别用 reachable 和 reached 来表示。
首先，对于每个点，都检查已知的 reachable 跟自己的 reachable’ （也就是 ii + nums[ii]）哪个更大， 保存大的；
然后就是看 ii 是否已经超过了 reached 的范围，如果是，说明又多了一跳，就要对 count 加一，
        同时还要更新 reached 的范围为前一跳范围内的最大reachable值（类似 DP，动态保存这个最大的 reachable 值），
最后如果更新后的 reached 覆盖到了终点，那么此时的 count 次数就是所求的最小次数了。

举个例子：2，5，12，3，2，3，2，3，4，8 的话，
当位于 2 的时候，reachable 是 2， reached 是 0，因为只到达了第 0 个位置；
当进入 5 的时候，reachable 是 5+1=6， reached 则是因为 ii 的值 1 大于 reached 的值 0，
                 所以，count++，且 reached 的范围变成 2， 因为跳了这一步，0，1 和 2 都在已到达的范围内了；
当进入 12 的时候，自己可以达到的是 12+2=14，大于已知的6，那么reachable 用14，而 reached 还是 2；
再进入 3 的时候，自己可以到达的是 3+3=6，还是保持 14，
                 但此时因为 ii 大于已经 reached 的范围了，所以需要再跳一次，这一跳完成之后， reached 的范围就是 14 以内了。
                 此时 reached = 14， 也就包含了终点，因此可以直接返回当前的 count 值（2）作为最小次数了。

class Solution {
public:
    //---------------------------------- Greedy ----------------------------------
    int jump28ms(vector<int>& nums) {
        int rst = INT_MAX, count=0;
        int sz = nums.size();
        if(sz)
            trytry(nums, 0, sz, count, rst);
        return rst;
    }
    bool trytry(vector<int>& nums, int pos, int sz, int& count, int& rst)
    {
        int range = nums[pos]+pos;
        if(range >= sz-1)
        {
            count += (pos<sz-1);
            if(count<rst)
                rst = count;
            count -= (pos<sz-1);
            return true;
        }
        for(int ii=range; ii>pos; ii--)
            if((count<rst) && (nums[ii]>=(nums[range]+(range-ii))))
            {
                count++;
                trytry(nums, ii, sz, count, rst);
                count--;
               
                if(rst==count+2)
                    return true;
            }
        return false;
    }   
    //---------------------------------- DP ----------------------------------
    int jump(vector<int>& nums) {
        int sz = nums.size();
        if(!sz)
            return 0;         int reachable=0, reached=0, count=0;
        for(int ii=0; ii<sz; ++ii)
        {
            if(ii>reached)
            {
                reached = reachable;
                count++;
            }
            reachable = max(reachable, nums[ii]+ii);
           
            if(reached >= sz-1)                return count;
        }
        return count;
    }
};
28 ms, 16 ms.