45. 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.)

class Solution {
public:
    int jump(vector<int>& nums) {
        int cur_can_jump = 0;
        int step = 0;
        int last_can_jump = 0;

        for(int i = 0; i < nums.size() - 1; i++){
            cur_can_jump = max(cur_can_jump, i + nums[i]);
            //如果到达了上次能到达的最大距离，就更新
            if( i == last_can_jump) {
                step++;
                last_can_jump = cur_can_jump;
            } 
        }
        return step;
    }
};

写成这样可能比较容易理解，cur_can_jump记录当前能跳到的最远节点处，last_can_jump记录上一个能到达的最远节点处。遍历节点i(0<=i<nums.size())时，当i > cur_can_jump，说明不能到达i，而当i > last_can_jump时，说明需要在last_can_jump能到达的节点中"加油"一次

实际上就是一次BFS的过程，可以这样理解，状态表示为(i，能到达的节点处)，初始状态
以[2, 3, 1, 1, 4]为例
                   (0,2)                     0
                     | 
                     |
               (1,4)   (2, 3)                1
                  |
                  |
          (2, 3) (3, 4) (4)[终止状态]         2

class Solution {
public:
    int jump(vector<int>& nums) {
        int cur_can_jump = 0;
        int step = 0;
        int last_can_jump = 0;

        for(int i = 0; i < nums.size(); i++){
            if(i > cur_can_jump){
                return -1;
            }

            if(i > last_can_jump){
                step++;
                last_can_jump = cur_can_jump;
            }

            cur_can_jump = max(cur_can_jump, i + nums[i]);
        }
        return step;
    }
};