45. Jump Game II (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # greedy
        result = furthest = cur = 0
        for i, num in enumerate(nums):
            if i > cur:
                result += 1
                cur = furthest
            furthest = max(furthest, i + num)
        return result
            
        # # dp
        # n = len(nums)
        # dp = [float("inf")] * n
        # dp[0] = 0
        # for i in range(1, n):
        #     for j in range(i, min(n, i + nums[i - 1])):
        #         dp[j] = min(dp[j], dp[i - 1] + 1)
        # return dp[-1]