1. 問題描述：
給你一個下標從 0 開始的整數陣列 nums 和一個整數 k ，一開始你在下標 0 處，每一步，你最多可以往前跳 k 步，但你不能跳出陣列的邊界，也就是說，你可以從下標 i 跳到 [i + 1， min(n - 1, i + k)] 包含兩個端點的任意位置，你的目標是到達陣列最后一個位置（下標為 n - 1 ），你的得分為經過的所有數字之和，請你回傳你能得到的最大得分 ，
示例 1：
輸入：nums = [1,-1,-2,4,-7,3], k = 2
輸出：7
解釋：你可以選擇子序列 [1,-1,4,3] （上面加粗的數字），和為 7 ，
示例 2：
輸入：nums = [10,-5,-2,4,0,3], k = 3
輸出：17
解釋：你可以選擇子序列 [10,4,3] （上面加粗數字），和為 17 ，
示例 3：
輸入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
輸出：0
提示：
-
1 <= nums.length, k <= 105 -104 <= nums[i] <= 104
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/jump-game-vi
2. 思路分析：
① 分析題目可以知道我們可以嘗試所有從起點到達終點的所有路徑，在所有路徑中找到經過數字之和的最大的那條路徑這個思路是最容易想到也是解決起來最簡單的是使用dfs搜索的方法，但是從起點到終點所有的路徑的資料量是非常龐大的，所以當資料量超過某一個范圍的時候是根本計算不出結果的（不管是dfs還是bfs都是無法解決資料量在10 ^ 5范圍的）所以提交上去也是超時的
② 除了搜索所有的路徑方法之外，我們想是否可以在遞回所有路徑的基礎上進行優化從而降低某些不必要的搜索呢？答案是肯定的，我們根據遞回可以聯想到的是記憶性的遞回，對于這道題目來說其實就是動態規劃，其實動態規劃理解起來應該屬于記憶型的迭代吧，暴力列舉不管是什么情況都會列舉所有的可能但是動態規劃是在暴力的基礎上使用陣列或者串列等資料結構來記錄中間的結果使得我們可以根據這個資料結構記錄的上一次結果遞推遞推出當前狀態狀態下最優的結果（感覺應該屬于優化的暴力列舉吧），動態規劃的核心就是dp陣列的定義與狀態方程式的撰寫，對于這道題目來說其實思路還是可以想出來的，我們無非是需要利用上一次的結果遞推出當前的結果，如果當前我的位置為i，我們是需要從上一個位置到達這個當前的i位置的，而上一個位置存在多個也即對應著多條路徑，而題目的限制條件是最多能夠在k步的條件下到從一個位置到達另外一個位置所以我的任務是需要計算出j = 1，2，3...k的步數的條件下計算所有的上一個位置到達j這個位置的得分在這些得分中取最大的那個就是到達當前i位置的最大得分，所以很容易得到狀態轉移方程為：f[i] = max{f[i - j]} + nums[i]，其中j = 1, 2...k，dp[i]的含義為到達當前i位置的最大得分，其實簡單來說就是我目前得到了當前j位置之前的位置的最大得分，所以我的任務是能夠從在到達當前j位置的上一個位置的得分中選擇一個最大的得分那么對于所有能夠到達j位置的路徑來這個得分肯定是最大的，所以最終dp[n - 1]就是能夠到達終點的最大得分，其實這一點也很好理解，但是因為是雙重回圈所以提交上去還是超時了（從第一個位置遞推到最后一個位置）
③ 力扣題解中提供了一種優化動態規劃的代碼，思路挺好的可以學習學習，在動態規劃的思路上借助于優先佇列來存盤所有能夠到達當前位置j的上一個位置的最大得分，因為是優先佇列所以元素會被賦予優先級我們可以利用這個優先級優先處理上一次能夠到達當前位置j的最大得分，因為使用的是python語言所以可以使用PriorityQueue宣告一個優先佇列，佇列的元素型別為元組，這樣一個元組可以表達多個資訊，元組可以包含兩個元素，第一個是優先級別，因為元素值越小優先級越高所以我們可以利用得分的相反數作為優先級，第二個到達當前元素的位置，這樣在回圈中我們可以在雙端佇列中移除掉一些不能夠到達當前j位置的元素，也即保證佇列中的元素都是可以到達j位置的，而使用優先佇列隊首元素保存就是上一個位置的最大得分，所以我們在回圈中可以更新對應的答案更新到最后就是最終的答案
3. 代碼如下：
動態規劃（超時）：
import sys
from typing import List
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
n = len(nums)
# dp[i]表示到i位置的最大得分
dp = [-sys.maxsize] * n
dp[0] = nums[0]
for i in range(1, n):
for j in range(1, k + 1):
if i - j < 0: break
elif dp[i - j] != -sys.maxsize:
# 計算dp[i]的最大值
dp[i] = max(dp[i], dp[i - j] + nums[i])
return dp[n - 1]優先佇列優化：
from typing import List
import queue
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
q = queue.PriorityQueue()
q.put((-nums[0], 0))
res = nums[0]
for i in range(1, len(nums)):
# 洗掉不能夠到達i位置的元素
while not q.empty():
# 移除優先佇列中的元素
top = q.get()
if i - top[-1] <= k:
# 移除了滿足條件的元素這個時候需要再一次加入進來
q.put(top)
break
# 更新答案, 優先佇列中的隊首元素就是上一個位置的最大得分
res = -top[0] + nums[i]
q.put((-res, i))
return res
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/249903.html
標籤：python
上一篇：Leetcode 110: Balanced Binary Tree
下一篇：Python 例外處理