Time: 
For a sub-problem nums[0:j] find furthest reachable index given 1, 2, ..., j jumps. Keep extending the sub-problem to nums[0:n]. Now, find the least jump_count to reach the last index.
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
furthest = [0] * (n+1)
for coord, max_jump in enumerate(nums):
for jump_count in range(coord, -1, -1):
if furthest[jump_count] < coord:
continue
furthest[jump_count+1] = max( furthest[jump_count+1], coord + max_jump )
return next( (jump_count for jump_count, coord in enumerate(furthest) if coord >= n-1) )
With one jump, the furthest we can go is nums[0]. We keep moving to indices (1, 2, …, n-1) in sequence. We use a jump only if we cannot reach an index (say i) and at that time we retrospectively use the best jump seen so far. Since, by definition a solution is guaranteed, this boost must enable us to move to the index i.
Time: 
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) == 1:
return 0
furthest, jump_count = nums[0], 1
boost = 0
for i in range(1, len(nums)):
if furthest < i:
jump_count += 1
furthest = boost
boost = max(boost, i+nums[i])
return jump_count
unreasonably effective 
Leave a comment