Leetcode # 45. Jump Game II

https://leetcode.com/problems/jump-game-ii/

Solution (Dynamic Programming)

class Solution:
  def jump(self, nums: List[int]) -> int:
    DP = [0] + [float("inf")]* (len(nums) - 1)
    for i in range(len(nums) - 1):
      for j in range(i + 1, min(i + nums[i] + 1, len(nums))):
        DP[j] = min(DP[j], DP[i] + 1)
    return DP[-1]

Better Solution (Greedy Method)

從 index: 0 開始
每次前進至範圍之內 num 最大的那格
（若有複數格為最大則選擇最遠的那格）

Time Complexity: O(n)
Space Complexity: O(1)

class Solution:
  def jump(self, nums: List[int]) -> int:
    cur, jumps = 0, 0
    while cur < len(nums) - 1:
      if nums[cur] == 0:
        return -1
      
      jumps += 1
      if cur + nums[cur] < len(nums) - 1:
        max_dist, candicate = 0, cur
        for step in range(1, nums[cur] + 1):
          next_i = cur + step
          if max_dist < nums[next_i] + step:
            max_dist = nums[next_i] + step
            candicate = next_i
        cur = candicate
      else:
        break
    
    return jumps

Last Updated on 2023/08/16 by A1go