Jump Game

You get an array nums of non-negative integers. You start at index 0.

Return the smallest number of jumps that gets you to the last index.

From index i, you can jump forward any number of steps from 1 to nums[i].

Example 1:

Input: [3,1,4,1,1,2,1]
Output: 2
Explanation: Jump 2 steps, from index 0 to index 2.
Then jump 4 steps, from index 2 to index 6, the last index.
Both jumps are allowed: nums[0] = 3 and nums[2] = 4.

Example 2:

Input: [1,2,1,1,1]
Output: 3
Explanation: The best route is 0 → 1 → 3 → 4.

Example 3:

Input: [6,2,1]
Output: 1
Explanation: A jump can be shorter than nums[i].
One jump of 2 steps goes from index 0 to the last index.

Constraints:

• 1 to 110,000 numbers.
• Each number is from 0 to 1,000.
• The last index can always be reached.