遊戲模擬 Jump Game II 青蛙過河 II Leetcode_#45

Vianney CAHEN on Unsplash

題目敘述

題目會給我們一個輸入陣列nums，每個元素值代表那個格子點可以跳躍的最大長度。

題目保證從最左邊的格子點出發開始跳，一定可以成功抵達終點，請問最少跳躍次數是說少?

題目的原文敘述

測試範例

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: 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.

第 0 格跳一格到第 1 格
第 1 格跳三格到第 4 格
總共跳兩次​

Example 2:

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

第 0 格跳一格到第 1 格
第 1 格跳三格到第 4 格
總共跳兩次​

約束條件

Constraints:

• 1 <= nums.length <= 10^4

輸入陣列nums長度介於1~10^4之間。

• 0 <= nums[i] <= 1000

每個格子點最小可以跳0格，相當於留在原地。代表題目可能會給陷阱格子。

最大可以跳1000個格子。

• It's guaranteed that you can reach nums[n - 1].

題目保證一定可以從起點抵達終點。

第一直覺想到就是依照遊戲規則去模擬，盡量往右邊跳，看看跳到終點的最少跳躍次數是多少?

當然是可以的，但是仔細留意一下，nums[i]最大可以有1000，代表每個格子點可能的選擇(也就是分枝)可以有一千條路徑，顯然用直接進行模擬會存在執行速度太慢或者time-out超過時間限制的風險，因為是指數級別的枚舉所有跳躍路徑。

這題其實用DFS模擬，或者BFS模擬跳躍，還是勉強可以通過平台的測試。

但是，後面我們會介紹一個更好的演算法，採用貪心策略Greedy strategy的演算法來提升速度。

程式法 DFS模擬跳躍

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

        def min_jumps(index):

            # Base case, already reach destination
            if index>=len(nums)-1:
                return 0

            # Look-up DP table
            if index in dp:
                return dp[index]

            # DFS to explore all paths, update minimal jump times
            step=math.inf
            for i in range(index+1,index+nums[index]+1):
                step=min(step,1+min_jumps(i))
            dp[index]=step
            return step
        # ---------------------------------------------
        return min_jumps(0)

程式碼 BFS模擬跳躍

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        destination = len(nums)-1
        bfs_q = deque([ (0,0) ])
        seen = {0}

        while bfs_q:

            cur, step = bfs_q.popleft()
            if cur >= destination:
                return step

            for jump in range( nums[cur], 0, -1):
                
                next_pos = (cur + jump)
                
                if next_pos not in seen:
                    seen.add( next_pos )
                    bfs_q.append( (next_pos, step+1) )

        return -1

演算法 Greedy 策略 盡量去延伸我能抵達的地方，而且到最後非跳不可的時候才跳，盡量減少跳躍次數。

一開始，從起點0出發，在起點做個記號。

從起點開始，往右逐一檢查每個格子點，去延伸目前我最遠能跳到哪裡，做個記號。

一旦我跳了一步，jump的計數器累加1。

接下來看看目前能跳到哪裡，一旦發現要跨過最後一個記號的時候，才不得已再跳新的一步。

當某一步發現能跳到終點時，當下的步數就是最少的跳躍次數。

程式碼 Greedy 策略 盡量去延伸我能抵達的地方，而且到最後非跳不可的時候才跳，盡量減少跳躍次數。

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        n = len(nums)
        destination = n - 1

        if destination == 0:
        # 邊界條件處理，當只有一個格子時，不用跳就已經在終點。
            return 0

        max_reach = 0
        last_jump_idx = 0
        jump_count = 0

        for i in range( n ):

            max_reach = max(max_reach, i + nums[i] )
            
            # 跨過當下有做記號的最後一格，非不得已才跳一次去延伸跳躍的覆蓋範圍
            if i == last_jump_idx:
                jump_count += 1
                last_jump_idx = max_reach

                if max_reach >= destination:
                    return jump_count
        
        return jump_count        

複雜度分析 Greedy 策略 盡量去延伸我能抵達的地方

令n=輸入陣列nums的長度

時間複雜度:

從左邊到右邊逐一檢查每個格子點，盡量去延伸跳躍能覆蓋的範圍爾且盡量節省跳躍是數，總共所需時間為O(n)。

空間複雜度:

用到的都是固定尺寸的臨時變數，總共所需空間為O(1)。

關鍵知識點

演算法 Greedy 策略 盡量去延伸我能抵達的地方，而且到最後非跳不可的時候才跳，盡量減少跳躍次數。

和前一題 Jump Game I 有著類似的Greedy策略結構，可以好好互相參照，吸收沉澱，

了解Greedy的涵義: 局部最佳解 推演出 全域的最佳解。

Reference:

[1] Jump Game II_Python O(n) by greedy of coverage