Leetcode: jump game I & jump gameII

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.

M1: linear 往回看dp, 经典DP， 时间复杂度： O（n^2）,空间复杂度： O（n）
但是大集合超时！DP:M[i]: 能否从i 跳到最后
class Solution {
public:
    bool canJump(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return true;
        //use dp to solve this problem
        bool M[nums.size()];
        //base case
        M[nums.size()-1] = true;
        //fill the array
        for (int i = nums.size()-2; i >= 0; i--) {
            //case 1: can jump out at one step
            if (nums[i] + i >= nums.size()) M[i] = true;
            else {//case 2: jump to one true then jump to the end
                int j = 0;
                for (j = i+1; j <= nums[i]+i; j++) {
                    if (M[j] == true) {
                        M[i] = true;
                        break;
                    }
                }
                if (j > nums[i] + i) M[i] = false;
            }
        }
        return M[0];
    }
};

M2：
reach : 从当前一步出发能到达的最远距离。下一步i跳也只能跳到reach的地方，看在reach范围内i能不能跳到更远， 即更新reach的值
time complexity： O（n）space complexity: O(1)
class Solution {
public:
    bool canJump(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return true;
        int local = nums[0];
        int global_max = nums[0];
        for (int i = 1; i <= global_max && i < nums.size();i++) {
            local = nums[i] + i;
            global_max = max(global_max, local);
        }
        if (global_max >= nums.size()-1) return true;
        return false;
    }
};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.)

M1: 基础DP： time complexity: O(n^2), space complexity: O(n)
M[i]: 在index 为i的地方到达终点的 最小步数
class Solution {
public:
    int jump(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return -1;
        //use dp
        int M[nums.size()];
        //base case
        M[nums.size()-1] = 0;
        for (int i = nums.size()-2; i >= 0; i--) {
            //case 1: jump out
            if ( nums[i] + i >= nums.size()-1) M[i] = 1;
            else {
                int min1 = INT_MAX;
                int j = 0;
                for (j = i + 1; j <= nums[i] + i; j++) {
                    if (M[j] >= 0) min1 = min(min1, M[j] + 1);
                }
                if (j > nums[i] + i) M[i] = -1;
                else M[i] = min1;
            }
        }
        return M[0];
    }
};

M2：
优化DP： time complexity: O(n). space complexity: O(1)
class Solution {
public:
    int jump(vector<int>& nums) {
        //sanity checkc
        if (nums.size() == 0) return -1;
        int reach = 0;
        int step = 0;
        int lastReach = 0;
        for (int i = 0; i <= reach && i < nums.size(); i++) {
           
            if (i > lastReach) {
                lastReach = reach;
                step += 1;
            }
            reach = max(reach, i + nums[i]);
           
        }
        if (reach < nums.size()-1) return 0;
        return step;
    }
};