Jump Game II
Medium · greedy
A frog sits on the first stone of a row of stones, one per item of nums. The number nums[i] is the longest hop the frog can make from stone i: it may land on any stone from 1 up to nums[i] places further along the row.
Return the fewest hops the frog needs to land on the last stone.
You may assume the last stone can always be reached. If the row has only one stone, the frog is already there and the answer is 0.
Examples
Example 1
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Hop 1 place to index 1, then 3 places to the last index. No single hop reaches it.
Example 2
Input: nums = [1, 1, 1]
Output: 2
Every hop can only move one place, so two hops are needed to go from index 0 to index 2.
Example 3
Input: nums = [0]
Output: 0
The frog starts on the last stone.
Constraints
- 1 <= len(nums) <= 3000
- 0 <= nums[i] <= 10^5
- The last index can always be reached from index 0.