[LeetCode] 45. Jump Game II

轉自LeetCode

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.

For example:
Given array A = [2,3,1,1,4]

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.

<Solution>

這題是 Jump Game 的衍生題，這次就是要求最小步數了

那有看到一個神解，圖解可以看連結

主要想法是

• 當目前 index 的位置，是在目前可到達範圍內的話，就不用移動。如果 index 超出可以到達的範圍，那麼將可達到範圍更新到下一個可以到的最遠範圍，並且將移動步數加1 (因為更新可達到範圍，就代表移動了)

• 對於每個 index 的值，都去更新可以到的最遠範圍。這邊注意一點是，更新前都會先檢查 index 是不是在可達到範圍內，如果不是，就會更新目前範圍，這就代表在找每個 index 可以到的最遠範圍時，都已經確保在目前移動步數下，可以到達的 index

code 如下
c++

kotlin