難度: Medium
類型: Array, Dynamic Programming, Greedy
CPP程式下載: 45.cpp
前情題要:
從起點跳到終點的最少跳躍數
思考方式:
1. 目前的位置加上可以跳的步數, 直到這個值超過最後一格。
2. 每跳一次, 就要找從最小步數, 到最大步數中, 可以跳到的最遠距離。
3. 直到能越過最後一格就知道需要的最少跳躍數。
4. 記得都要從最小步數(一步)開始找起, 而不是從最大步數的開始到最大步數找起, 這樣會錯過某個突然很大的步數值。
5. 每次的最小步數都是前一次的最小步數加一。
複雜度思考:
Time Complexity: O( (N+1)*N )
Space Complexity: O( x )
結果:
Runtime: 0 ms, Beats: 100%
Memory: 20.39 MB, Beats: 84.63%
