Jump Game II

Jump Game II

Description:

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.

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

分析：

We can find that there are “optimal substructure” and “greedy choice” in this problem. So we can apply “Greedy Algorithm” to solve it.

  • optimal substructure: Assume that the index of optimal solution from A[0] to A[ik] is：i1, i2,…,ik-1, ik, then one of the optimal solution’s index from A[0] to A[ik-1] must be i1, i2,…,ik-1.
     
    if not, i1, i2,…,ik-1, ik would not be the optimal solution.
     

  • greedy choice: Every time we choose a index where we jump, the index (assuming ilm) must be the left most from which we can jump to the destination A[ik] by only one jump.
     
    If not, which means we choose the index between left most and destination, assuming it’s it . Let p be the minimal jump from A[0] to A[ilm], and q be the minimal jump from A[0] to A[it]. We can get p > q, considering the index it-1.

    • if it-1 < ilm, since we can jump from it-1 to it, then we can jump from it-1 to ilm (because ilm < it ), so p == q == jump_number(it-1)+1, this is inconsistent with p > q.
    • if ilm < it-1 < it, we can consider it-2, until it-j < ilm, and we can prove by similar method above.

The code is listed as bellow.

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    /**
     * @param A: A list of lists of integers
     * @return: An integer
     */
    int jump(vector<int> A) {
        // wirte your code here
        int curr_index = A.size()-1;
        int jump_count = 0;
        
        while (curr_index > 0) {
            int dist = 1;
            for (int i = curr_index-1; i >= 0; i--,dist++) {
                if (A[i] >= dist) {
                    curr_index = i;
                }
            }
            jump_count++;
        }
        
        return jump_count;
    }
};