LeetCode 45 [Jump Game II]

原题

给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。　　　
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

给出数组A =** [2,3,1,1,4]**，最少到达数组最后一个位置的跳跃次数是2(从数组下标0跳一步到数组下标1，然后跳3步到数组的最后一个位置，一共跳跃2次)

解题思路

• 方法一：贪心(Greedy)
• 维护一个farthest变量，每次在遍历start到end之间的元素，尝试更新farthest变量
• start = end + 1
• end = farthest
• 比较end时候大于数组长度，大于返回结果，否则steps += 1
• 方法二：动态规划(领会思路，OJ会超时)
• �开辟一个steps数组长度与input数组相同，初始值为maxint
• steps[0] = 0
• steps[i]等于遍历steps[0] ~ steps[i-1]，如果存在nums[x] + x > i，则更新steps[i] = steps[x] + 1

完整代码

# 方法一：贪心
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return -1
        
        start, end, steps = 0, 0, 0
        while end < len(nums) - 1:
            steps += 1
            farthest = end
            for i in range(start, end + 1):
                if nums[i] + i > farthest:
                    farthest = nums[i] + i
            start = end + 1
            end = farthest
        
        return steps
# 方法二：动态规划
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        steps = [sys.maxint for i in range(len(nums))]
        
        steps[0] = 0
        for i in range(1, len(nums)):
            for j in range(i):
                if steps[j] != sys.maxint and j + nums[j] >= i:
                    steps[i] = steps[j] + 1
                    break
        
        return steps[len(nums) - 1]