Description

Submission

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() < 2) return 0;
        int count = 0;
        for(int ptr = 0; ptr < nums.size();) {
            int max_index = 0, max_ptr = 0;
            for(int i = 1; i <= nums[ptr]; ++i) {
                if(ptr+i >= nums.size() - 1) return count + 1;
                int index = nums[ptr+i] + ptr + i;
                if(index > max_index) {
                    max_index = index;
                    max_ptr = ptr + i;
                }
            }
            ptr = max_ptr;
            count++;
        }
        return count;
    }

};

The index is a measurement for which one to go. It measures how far a candidate position can go, and always choosing the one with highest score will get the optimum solution.

Submission II 200930

class Solution {
public:
    int jump(vector<int>& nums) {
        int start = 0, end = 0;
        int count = 0;
        int new_end = 0;
        
        if(nums.size() == 1) return 0;

        while(start <= end) {
            
            for(int i = start; i <= end; ++i) {
                new_end = max(nums[i] + i, new_end);
                if(new_end >= nums.size() - 1)
                    return count + 1;
            }

            count++;
            start = end + 1;
            end = new_end;
        }

        return -1;
    }
};