動機

簡單一點也不是壞事，至少算index到找到一個完整的方式去處理之前

Problem

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

 

Example 1:

Input: nums = [2,3,1,1,4]Output: 2Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]Output: 2

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000

Sol1: DP (TLE)

原本是用DP往回刷，當然超時

class Solution:
    @functools.cache
    def f(self,i):
        if i == 0:
            return 0
        else:
            return min([self.f(j) for j in range(0, i) if (i-j) <= self.nums[j]])+1
    def jump(self, nums: List[int]) -> int:
        self.nums = nums
        #[print(self.f(x)) for x in range(0,len(nums))]
        return self.f(len(nums)-1)

Sol1.5: Wrong Greedy (…)

  1. 在可跳躍去區間中，找最大的位置
  2. 根據選出來的位置，去算可以忽略(該點到區間的終點)的距離

但是一直出事，吃WA，一直沒實作好…

class Solution:
    def jump(self, nums: List[int]) -> int:
        i = 0
        seen=0
        ans = 0
        while i < len(nums)-1:
            if nums[i] == 1:
                max_i = i + 1
                seen = 0
            else:
                if i+nums[i]+1+seen >= len(nums):
                    max_i = len(nums)
                else:
                    sub = nums[i+1+seen:i+nums[i]+1+seen]
                    #print(sub)
                    if sub:
                        max_i = i+seen+1+max(reversed(range(len(sub))), key=sub.__getitem__)
                        seen = nums[i] - max_i
                    else:
                        max_i = i+seen+1
                        seen = 0
            i = max_i
            ans += 1
            #print(i,seen,ans)
        return ans

Sol2: Greedy (AC)

只包留第一條，但改一下

  • 在可跳躍去區間中，找能跳出去的最大位置

這裡有個Python Trick，就是去找最大值的index

max(range(len(sub)), key=sub.__getitem__)

class Solution:
    def jump(self, nums: List[int]) -> int:
        i = 0
        ans = 0
        while i < len(nums)-1:
            if nums[i] == 1:
                max_i = i + 1
            else:
                if i+nums[i]+1 >= len(nums):
                    max_i = len(nums)
                else:
                    sub = [j for j in range(i+1,i+nums[i]+1) if j < len(nums)]
                    #print(sub)
                    if sub:
                        sub = [nums[j]-(i+nums[i]+1-j) for j in sub]
                        max_i = i+1+max(range(len(sub)), key=sub.__getitem__)
                    else:
                        max_i = i+1
            i = max_i
            ans += 1
            #print(i,ans)
        return ans