45. Jump Game II

Python

Bottom Up Dp

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0

        dp = [0] * len(nums)

        farthest = 0
        for i in range(1, len(nums)):
            while i > farthest + nums[farthest]:
                farthest += 1
            dp[i] = dp[farthest] + 1

        return dp[-1]