055 - Jump Game

Jump Game

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.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Hide Tags
Array Greedy
 
贪心的逻辑还是比较清楚的，能跨多远跨多远，跨到/过了结尾就成功，
够不到结尾就在跨过的范围里找，谁能跨得更远，就从谁哪里递归调用继续跨。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int sz = nums.size();
        return sz ? trytry(nums, 0, sz) : true;
    }
   
    bool trytry(vector<int>& nums, int pos, int sz)
    {
        int range = nums[pos]+pos;
        if(range >= sz-1)
            return true;
   
        for(int ii=range; ii>pos; ii--)
            if((nums[ii]>=(nums[range]+(range-ii))) && (true == trytry(nums, ii, sz)))
                return true;
        return false;
    }
};
16 ms.

刚才做第二题，扑腾好久弄明白了，觉得思路可以借鉴回这一题，所以又回来重新写了一个DP的解法：
逐个循环，每一步先检查，是不是超过了可以到达的范围？如果是，就挂了。
如果不是，那么更新最大的可以到达范围，是已经知道的 reachable 更大，还是新的范围更大？
更新了之后检查是不是可以cover终点，是的话就直接返回true，不是则继续。
这么明显的DP居然没看出来，NND。

    bool canJump(vector<int>& nums) {
        int sz = nums.size();
        if(!sz)
            return false;
     
        int reachable=0;
        for(int ii=0; ii<sz; ++ii)
        {
            if(ii>reachable)
                return false;

            reachable = max(reachable, ii+nums[ii]);

            if(reachable >= sz-1)
                return true;
        }
        return false;
    }

也是16 ms.