# Question

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.

Example:

```
Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

# \(O(n)\) Greedy Solution

This solution maintains three variables:

- the maximum index reachable from
`0`

to`i`

, denoted as`max_reachable`

; - the furthest we can reach within the current number of jumps, denoted as
`furthest`

. In other words, you can go`0`

to`j`

where`j <= furthest`

in less than or equal to`jumps`

steps. - the number of jumps made so far, denoted as
`jumps`

.

When `i == furthest`

, we have to make another jump, and the furthest within that jump is the current `max_reachable`

. If `max_reachable`

is beyond the last index, then we know we can reach the last index within the next jump.

The invariant for the loop is that given the number of jumps, our jumps can reach farther than, or as far as any other jumps (`furthest`

holds the jumping distance). So If there is an optimal solution and the minimal jumps needed is `jumps`

, then we could argue that given jumps, our jumps can reach as far as the optimal solution, thus our solution is also optimal.

```
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return 0
jumps = 0
furthest = 0
max_reachable = 0
for i in range(len(nums) - 1):
max_reachable = max(max_reachable, i + nums[i])
if i == furthest:
jumps += 1
if max_reachable >= len(nums) - 1:
return jumps
else:
furthest = max_reachable
return jumps
```

# \(O(n^2)\) DP Solution

```
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return 0
dp = [0 for _ in range(len(nums))]
for i in range(len(dp) - 2, -1, -1):
if i + nums[i] >= len(nums):
dp[i] = 1
elif nums[i] == 0:
dp[i] = float('inf')
else:
dp[i] = min(dp[i+1: i + nums[i] + 1]) + 1
return dp[0]
```