You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. Return the minimum number of jumps to reach the last position.
nums
nums[0]
nums[i]
i
There is a DP approach which takes $O(n^2)$ steps[i] = 1+min(steps[j], 0<=j<i)
steps[i] = 1+min(steps[j], 0<=j<i)
max(nums[i]+i for i in [left, right])
def min_jump(nums: List[int]) -> int: n = len(nums) if n == 1: return 0 left, right, jumps = 0, 0, 0 while right < n - 1: max_reach = max(nums[i] + i for i in range(left, right + 1)) left = right right = max_reach jumps += 1 return jumps