[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]的位置,就是終點的位置,就到惹

所以總共兩步

ML好多RRR看不完惹QQ