Jump Game II

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

-------------------------------- thinking -----------------------------------------------
the main idea, once an index is reached the first time, the minimum jump steps of this index is 1 + the jump step of its jumping index
method 1: using array to record the min_jp info, this is very easy to implement
method 2: using old_biggest and biggest to update the min_jp info gradually. Please refer to read codes for the detailed implementation
---------------------------------- codes ------------------------------------------------
class Solution {
public:
    int jump(int A[], int n) {
        int min_jp[n];
        min_jp[0] = 0;
        int biggest = 0;
        for (int i = 0; i < n; i++) {
            if (biggest >= n-1) {
                return min_jp[n-1];
            }
            if (i > biggest) {
                return -1;
            }
            if (i + A[i] > biggest) {
                for (int j = biggest + 1; j <= i + A[i] && j < n; j++) {
                    // bug here, the updating of min_jp[j] should be the previous min_jp[i] instead of min_jp[biggest]
                    min_jp[j] = min_jp[i] + 1;
                }
                biggest = i + A[i];
            }
        }
        return -1;
    }
};
------------------------------------ read codes ------------------------------------------
only using two variables to track the min_jp[] array

class Solution {
public:
    int jump(int A[], int n) {
        //if (n <= 1) return 0;
        int old_biggest = 0;
        int biggest = 0;
        int jp_step = 0;
        for (int i = 0; i < n; i++) {
            //bug here, don't return when biggest reaches the end
            //instead, we should return when the old_biggest reaches the end, because this is the time that jp_step is updated
            if (old_biggest >= n-1) {
                return jp_step;
            }
            if (i > old_biggest) {
                jp_step++;
                old_biggest = biggest;
            }
            if (i + A[i] > biggest) {
                biggest = i + A[i];
            }
            if (i > biggest) {
                return -1;
            }

        }
        return jp_step;
    }
};