前幾天那題的延伸
一開始想說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