710 - Python LeetCode

【Leetcode】python - [45] Jump Game II 個人解法筆記 #重要題型

題目出處

45. Jump Game II

難度

Medium

個人範例程式碼

class Solution:
    def jump(self, nums: List[int]) -> int:

        # record min jump, init
        dp = [float("inf")] * len(nums)

        dp[0] = 0 # start
        # function
        for i in range(len(nums)):
            for j in range(i+1, i+1 + nums[i]): # 1:3 = 12, 1:1 = 0
                if j < len(nums):
                    dp[j] = min(dp[j], dp[i]+1) # jump+1 from dp[i] 
                else: # over range
                    break

        # print(dp)
        return dp[-1]

        # 2 3 1 1 4
        # 1 inf inf inf inf
        # 1 1 1 inf inf
        # 1 1 1 2 2

算法說明

  • 此題的前一題為不需要算步數的版本，只需要知道可不可抵達，可參考 (啊怎麼第二題的題號還比較前面?) ：

https://wongwongnotes-github-io.pages.dev/python/leetcode-python-55/

計算步數，我們一樣使用 DP，「紀錄最小抵達該樓層時使用步數」

  • function: dp[i] = min(dp[i], dp[j] + 1)

我們要比較的是，第 j 樓可以一步到此(+1) 的步數，是否比原來紀錄的可能步數還要少。

  • init: dp[0] = 1, 其他初始化 float(“inf”) (會被比較小的步數取代)
  • ans: dp[-1]

DP 變化如下

# 2 3 1 1 4 
# 0 inf inf inf inf (init)
# 0 1 1 inf inf (1F)
# 0 1 1 2 2 (2F)

優化

這裡可以做一些小優化，
因為到接近終點的樓層時， i + jump 會超過終點很多，
此時我們可以「提早先 break 迴圈」 (因為超過終點的範圍都不重要)

input handling

一同在 for 裡面處理掉

Boundary conditions

用 for 來控制 DP 的範圍

Reference