55.Jump Game

 这种动规的方法时间复杂度是0（n²）

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int length = nums.size();
        bool can[length];
        for(int i = 1;i < length;i++)
            can[i] = false;
        can[0] = true;
        for(int i = 1;i < length;i++){
            for(int j = i-1;j >= 0;j--){
                if(can[j] == true && nums[j] >= i-j){
                    can[i] = true;
                    break;
                }
            }
        }
        return can[length-1];
    }
};

 优化：记录能到达的最远距离，时间复杂度只有o（n）

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int length = nums.size();
        if(length < 0)
            return false;
        int canarrive = 0;
        for(int i = 0;i <= canarrive && canarrive < length-1;i++){
            if(i + nums[i] > canarrive)
                canarrive = i + nums[i];
        }
        return canarrive >= length-1;
    }
};