給定一組n石頭，以彼此相等的距離排列成一排。石頭的編號從0到n-1。一只在石數上的青蛙0必須到達石數n-1。
跳躍是從石頭i到石頭的移動j（i<j）。這種跳躍的長度等于j-i。青蛙的最大跳躍長度取決于它的能量水平（不能低于 0）。跳躍的長度j-i會消耗青蛙的j-i能量。例如，初始能量為 3，石頭上的青蛙0最多可以跳到石頭3上。
在一些石頭上，可能有蠕蟲，它們為青蛙增添了能量。如果青蛙跳到上面有蟲子的石頭上，它必須吃掉蟲子。該串列T[0...n-1]包含相應石頭上的蠕蟲的能量值。如果石頭上沒有蟲子，這相當于值為 0。
青蛙一開始能量為0，但保證石數上有蟲0。
給定一個串列T，任務是在到達石頭之前回傳青蛙所在的石頭的索引串列n-1。但是，這必須是最短的串列。在某些情況下，可能有多個解決方案，以被接受者為準。可以保證青蛙總能找到石頭n-1。
示例編號 1：
For T = [3, 0, 2, 1, 0, 2, 5, 0] the answer is [0, 2, 5].
示例編號 2：
For T = [7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0] the answer is [0, 3, 7] or [0, 5, 7].
我不知道如何解決這個問題，我只知道我可能需要在這里使用一些動態編程或貪婪演算法，但是如何？有人有想法么？
uj5u.com熱心網友回復：
O(n log n)您可以使用貪心演算法和優先級佇列及時解決這個問題。
從可變長度的跳躍中重新構建問題是非常有幫助的。
新問題框架：
- 假設您在第 0 塊石頭上，并且必須從到走每塊石頭。
0n-1 - 您
T[0]最初擁有當前的能量單位，每一步都需要消耗 1 個能量單位。 - 在您通過的每一塊石
T[i]頭上，您可以選擇支付一美元并獲得T[i]能量單位，最多一次。您的目標是最大限度地降低跳躍美元的成本。 - 當您邁出一步時，您的能量單位不允許為零。
關鍵的觀察是，在我們下一步真正需要能量之前，我們不必決定我們降落在哪些石頭上（從哪些石頭上購買了能量）。
因此，保留T[i]我們已通過但尚未購買的所有（能量單位銷售）的最大堆（優先級佇列）。如果我們當前的能量是0，貪婪地洗掉最大的T[i]（能量單位銷售），將其添加到我們當前的能量中，并附i加到我們從中購買能量的石頭串列中。
這類似于追溯決定停在ith石頭上，這沒關系，因為除了我們當前的能量和可用能量選擇串列之外，沒有任何東西受到影響。這種貪心演算法之所以有效，是因為我們只會在不可避免的情況下訪問一塊石頭，并且選擇任何其他石頭來訪問（而不是未使用的最高能量的石頭）永遠不會增加我們當前的能量。
Python 代碼（使用 heapq 模塊）
def min_jump_path(stones: list[int]) -> list[int]:
"""Return a shortest valid path to end of the array.
We must walk from index 0 to n-1, at a cost of 1 energy unit per step.
Energy cannot be 0 when taking a step.
Runtime: O(n log n). Space: O(n)"""
used_stones: list[int] = [0]
current_energy: int = stones[0]
available_energy_choices: list[tuple[int, int]] = []
for idx, energy_offered in enumerate(stones[1:], 1):
current_energy -= 1
# If we need to use some stone's energy to continue
if current_energy < 0:
# Return some 'error-value' if impossible
if len(available_energy_choices) == 0:
return []
energy_gain, stone_used = heapq.heappop(available_energy_choices)
energy_gain = -energy_gain # Negated for max-heap
current_energy = energy_gain
used_stones.append(stone_used)
if energy_offered > 0:
heapq.heappush(available_energy_choices,
(-energy_offered, idx)) # Negated for max-heap
# Used stone list may be out of order initially
return sorted(used_stones)
用法：
print(min_jump_path([3, 0, 2, 1, 0, 2, 5, 0]))
# [0, 2, 5]
print(min_jump_path([7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]))
# [0, 5, 7]
uj5u.com熱心網友回復：
請注意，最佳解決方案永遠不會向后跳躍：在向后轉向之前立即移除跳躍以使其更優化，從而反駁初始解決方案的最優性。這給了我們一個考慮位置的自然順序。
考慮問題世界的狀態：
- 青蛙在位置p，
- 有能量，
- 并使用k跳躍到達那里。
所以，一個簡單的解決方案是：給定p、e和k，是否有可能達到這樣的狀態？
現在，我們可以只詢問f(p,e,k)，它是true還是false，對于每個可能的引數集，考慮前一個或下一個跳轉到達這樣的狀態，也許會得到一個低效但有效的解決方案，遞回或迭代。基數為f(0,T[0],0) = true，所需狀態為f(n-1,?,?)。
為了提高效率，也許我們可以將一些引數（p、e或k）設為目標函式。
例如，考慮g(p,e) = min k：對于給定的位置和能量，計算具有這種位置和能量的最小跳躍次數。為方便起見，如果這種狀態(p,e)不能通過任意數量的跳轉到達，則將k定義為正無窮大。
或者考慮h(p,k) = max e：如果我們恰好在k次跳躍中到達位置p ，我們可以剩余多少能量作為剩余能量？同樣，如果(p,k)根本不可達，則定義為負無窮大。
最后，我們甚至可以做a(p) = best pair (k,e)：對于給定的位置p ，到達那里的最小跳躍次數k是多少，并且有了這個確切的跳躍次數，什么是青蛙還能擁有的最大剩余能量e ？（也許這行不通，但想想為什么它到底行不通仍然很有教育意義。）
考慮這個串列，或者擴展它，來決定哪種方法適合你——或者根本不適合。
uj5u.com熱心網友回復：
在決定跳到哪塊石頭時，我可以想到 2 種啟發式方法：“可能的最遠石頭”和“可能最有價值的石頭”。
最遠的石頭
- 計算到達終點所需的最小能量，例如
M，在每塊石頭上。 - 跳到最遠的石頭上，您至少可以在石頭上保持所需的最低能量。
- 重復步驟 2，直到到達最后一塊石頭。
最有價值的石頭
- 計算到達終點所需的最小能量，例如
M，在每塊石頭上。 - 在每次跳躍時，計算獎勵函式：
Reward of the jump (R) = Energy to be earned by the jump - Energy to be spent by the jump
跳到可能的下一個石頭中最有價值的石頭，同時滿足下一個石頭的最低能量需求。如果多顆石頭的回報相同，請選擇最遠的一顆。此外，如果可能，請始終選擇最后一塊石頭。
重復步驟 2-3，直到到達最后一塊石頭。
示例 2 與最遠的石頭可能啟發式：
Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]
腳步
1. 在 Idx 0 - 能量 7
-> 跳到 5，因為這是你在滿足最低能量要求的情況下可以獲得的最遠的石頭。
2. 在 Idx 5 - 能量 5
-> 跳至 7，原因與步驟 1 相同。
3. 在 Idx 7 - 能量 9
-> 跳到最后一塊石頭，原因與步驟 1 相同。
示例 2 與最有價值的石頭可能啟發式：
Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]
腳步
1. 在 Idx 0 - 能量 7
| 下一個 Idx 可能 | 報酬 |
|---|---|
| 1 | -1 |
| 2 | -2 |
| 3 | -2 |
| 4 | -4 |
| 5 | -2 |
-> 選擇 5
2. 在 Idx 5 - 能量 5
| 下一個 Idx 可能 | 報酬 |
|---|---|
| 6 | -1 |
| 7 | 4 |
| 8 | -3 |
| 9 | -4 |
| 10 | -5 |
-> 選擇 7
3. 在 Idx 7 - 能量 9
-> 選擇最后一塊石頭，因為它是可能的
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/466278.html