[LeetCode] Jump Game II

前幾天那題的延伸

一開始想說DFS去traversal

但這樣有可能最佳解(最短的)落在最後一條branch

後來想想找最短的branch應該是用BFS比較快

再後來想想 好像只要當前可以走最遠的那個branch就可以惹，也不用每個分支都跑

[2,3,1,1,4] 這個example

第一步在root點上最多走到nums[2]

第二步從3,1這兩個branch來看，3可以走更遠所以選3

而且這個分支最遠可以到nums[4]的位置，就是終點的位置，就到惹

所以總共兩步

class Solution {
public:
    int jump(vector<int>& nums) {
    
        int pos = 0, len = nums.size(), count = 0, i = 0;
        
        if(len == 1)
            return 0;
             
        while(pos < len-1)
        {    
            int next_pos = 0;
            
            for(; i <= pos; i++)
                next_pos = max(next_pos, nums[i]+i);
            
            pos = next_pos;
            count++;
        }
        
        return count;
    }
};

ML好多RRR看不完惹QQ