2022-03-06：金幣路徑。
給定一個數組 A（下標從 1 開始）包含 N 個整數：A1，A2，……，AN 和一個整數 B。
你可以從數組 A 中的任何一個位置（下標為 i）跳到下標 i+1，i+2，……，i+B 的任意一個可以跳到的位置上。
如果你在下標為 i 的位置上，你需要支付 Ai 個金幣。
如果 Ai 是 -1，意味著下標為 i 的位置是不可以跳到的。
現在，你希望花費最少的金幣從數組 A 的 1 位置跳到 N 位置，你需要輸出花費最少的路徑，依次輸出所有經過的下標（從 1 到 N）。
如果有多種花費最少的方案，輸出字典順序最小的路徑。
如果無法到達 N 位置，請返回一個空數組。
樣例 1 :
輸入: [1,2,4,-1,2], 2
輸出: [1,3,5]
注釋 :
路徑 Pa1，Pa2，……，Pan 是字典序小于 Pb1，Pb2，……，Pbm 的，
當且僅當第一個 Pai 和 Pbi 不同的 i 滿足 Pai < Pbi，
如果不存在這樣的 i 那么滿足 n < m。
A1 >= 0。
A2, …, AN （如果存在） 的范圍是 [-1, 100]。
A 數組的長度范圍 [1, 1000].
B 的范圍 [1, 100].
力扣656。

答案2022-03-06：

時間緊，具體見代碼。

代碼用python編寫。代碼如下：

# -*-coding:utf-8-*- # Time: O(n * B) # Space: O(n) class Solution(object):def cheapestJump(self, A, B):""":type A: List[int]:type B: int:rtype: List[int]"""result = []if not A or A[-1] == -1:return resultn = len(A)dp, next_pos = [float("inf")] * n, [-1] * ndp[n-1] = A[n-1]for i in reversed(range(n-1)):if A[i] == -1:continuefor j in range(i+1, min(i+B+1,n)):if A[i] + dp[j] < dp[i]:dp[i] = A[i] + dp[j]next_pos[i] = jif dp[0] == float("inf"):return resultk = 0while k != -1:result.append(k+1)k = next_pos[k]return resultif __name__ == '__main__':obj = Solution();A = [1,2,4,-1,2];B = 2;C = obj.cheapestJump(A,B);print(C);

執行結果如下：

---

左神java代碼

總結

以上是生活随笔為你收集整理的2022-03-06：金币路径。 给定一个数组 A（下标从 1 开始）包含 N 个整数：A1，A2，……，AN 和一个整数 B。 你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。