跳跃游戏II

1、题目

图1

2、题解

动态规划+贪心

图2

图3

class Solution:
    def jump(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [float("inf") for _ in range(size)]
        dp[0] = 0

        j = 0
        for i in range(1, size):
            while j + nums[j] < i:
                j += 1
            dp[i] = dp[j] + 1

        return dp[size - 1]

贪心

图4

class Solution:
    def jump(self, nums: List[int]) -> int:
        end,max_step = 0, 0
        step = 0

        for i in range(len(nums)-1):
            max_step = max(max_step, nums[i]+i)

            if i == end:
                end = max_step
                step += 1

        return step