Programming Skills: Jump Game II

[題目]
https://leetcode.com/problems/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:

Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

Note:

You can assume that you can always reach the last index.

數字代表你一跳最多可以跨幾格，比如3代表你一跳可以跨1 or 2 or 3格。求跳到尾巴所需的最小跳躍次數。

[思路]
這也是一個hard的題目，首先你必須擁有BFS和shortest path的這兩個基礎知識。
如此你就可以把本題的array看待成一個Graph。
1.array size＝圖中的node數。例如[2,3,1,1,4]代表有五個node 0~4。
2.你從node i可以跳到node k的話，代表這兩人之間有edge。
例如[2,3,1,1,4]
node 0 和 node 1 & 2之間有edge。
node 1 和 node 2 & 3 & 4之間有edge。

由於edge長度都是相同的，因此你套用BFS，求圖中node 0從到node 4的最短路徑，就等於是求原題的解。（如果edge長度不同的話就要用dynamic programming的Dijkstra algorithm了）


class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() <= 1) return 0;
        
        int jumps=0;
        int L=0,R=0;//L & R bound of BFS level.
        queue<int> idxq;
        idxq.push(0); L=R+1;

        while(!idxq.empty()){
            int k=idxq.size();
            jumps++;
            for(int i=0;i < k;i++){ //k is the number of this BFS level
                //find the right bound of BFS level
                R=max(R, idxq.front()+nums[idxq.front()]);
                if(R>=nums.size()-1) return jumps;
                idxq.pop();                
            }
                        
            for(int i=L;i<=R;i++)
                idxq.push(i);
            L=R+1;
        }

    }
};