Jump Game

Q: 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.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

这道题有点像大富翁呀，题意也很简单明确，就不解释了。
我首先想到的就是用迭代遍历硬杠它。从最大值开始跳，每个位置都是从最小值开始跳，如果碰到了就返回，然后输出。
形象点地，可以用一个答案树进行解释

example: 
Input  [2, 3, 1, 1, 4]
stage 1                                                2                                   1                 
stage 2           index:(0+2)=2
                       value: 1                        1
stage 3           index:(2+1)=3     
                       value:1                         1
stage 4           index:(3+1)=4                      find!

于是开始进行愉快地代码。

/***
一个简单的迭代解法
***/
class Solution {
    void jump(int cur_index, int cur_step, bool& res, vector<int>& nums){
        int cur_num = nums[cur_index];
        if( cur_index == nums.size() - 1 ){
            res = true;
            return;
        }
        if (cur_num != 0) {
        for( int i=1; i<=cur_num; i++){
            if( cur_index + i < nums.size() ) {
                // 不能越界
                jump( cur_index + i , i, res, nums);
            }
        }
        }
    }
public:
    bool canJump(vector<int>& nums) {
        bool res = false;
        jump(0, nums[0],  res, nums);
        return res;
    }
};

解法是没错的，但是在提交的时候就华丽丽地超时了。想了一下，这个算法n^2的复杂度，超时了可能就是要我们求个O（nlgn）或者O（n）的算法，所以就需要tricky一下。

由于这个题目只是让我们返回true或者false，其实只要我们找到题目条件的必要条件就行了，把问题转化为判断必要条件是否成立。
其实这道题换种思路就非常容易理解。
从现在的位置 cur_index 到现在位置对应的可以跳跃位置的最大值 jump_max 之和所得到的 next_index 之间
的所有位置，从现在的位置都是 cur_index 都是跳到的。
所以我们可以记录一个最右端的值 right_max, 然后在数组循环过程当中进行 right_max 的更新，只要最后 right_max > nums.size() - 1
我们就可以返回 true。

AC代码如下:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int right_max = 0;
        for(int i=0; i< nums.size() - 1; i++){
            if( right_max < i ) break; //最右端的位置比现在遍历到的位置还要小，结束循环
            else{
                right_max = max( nums[i] + i , right_max);
            }
        }
        return right_max >= nums.size() - 1;
    }
};

只进行了一次循环，所有时间复杂度为O(n)，效率属于很高的了，就不再继续研究了。