題目敘述
題目會給我們一個輸入陣列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:
