文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個(gè)數(shù)組 A（下標(biāo)從 1 開(kāi)始）包含 N 個(gè)整數(shù)：A1，A2，……，AN 和一個(gè)整數(shù) B。
你可以從數(shù)組 A 中的任何一個(gè)位置（下標(biāo)為 i）跳到下標(biāo) i+1，i+2，……，i+B 的任意一個(gè)可以跳到的位置上。
如果你在下標(biāo)為 i 的位置上，你需要支付 Ai 個(gè)金幣。
如果 Ai 是 -1，意味著下標(biāo)為 i 的位置是不可以跳到的。

現(xiàn)在，你希望花費(fèi)最少的金幣從數(shù)組 A 的 1 位置跳到 N 位置，你需要輸出花費(fèi)最少的路徑，依次輸出所有經(jīng)過(guò)的下標(biāo)（從 1 到 N）。

如果有多種花費(fèi)最少的方案，輸出字典順序最小的路徑。

如果無(wú)法到達(dá) N 位置，請(qǐng)返回一個(gè)空數(shù)組。

樣例 1 : 輸入: [1,2,4,-1,2], 2 輸出: [1,3,5]樣例 2 : 輸入: [1,2,4,-1,2], 1 輸出: []注釋 : 路徑 Pa1，Pa2，……，Pan 是字典序小于 Pb1，Pb2，……，Pbm 的，當(dāng)且僅當(dāng)?shù)谝粋€(gè) Pai 和 Pbi 不同的 i 滿足 Pai < Pbi，如果不存在這樣的 i 那么滿足 n < m。 A1 >= 0。 A2, ..., AN （如果存在） 的范圍是 [-1, 100]。 A 數(shù)組的長(zhǎng)度范圍 [1, 1000]. B 的范圍 [1, 100].

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/coin-path
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

class Solution { public:vector<int> cheapestJump(vector<int>& A, int B) {int n = A.size(), i, len, cost, idx = n-1;vector<int> dp(n, INT_MAX);vector<vector<int>> path(n);dp[0] = A[0];path[0] = {1};for(i = 0; i < n-1; i++) {if(dp[i] == INT_MAX)//狀態(tài)不存在continue;for(len = 1; len <= B; len++){if(i+len < n && A[i+len] != -1)//可以到達(dá){if(dp[i+len] > dp[i]+A[i+len]){ //取最小的花費(fèi)的路徑dp[i+len] = dp[i]+A[i+len];path[i+len] = path[i];path[i+len].push_back(i+len+1);}else if(dp[i+len] == dp[i]+A[i+len]){ //花費(fèi)相同auto temp = path[i];temp.push_back(i+len+1);if(temp < path[i+len])//取字典序小的路徑path[i+len] = temp;}}}}return path[n-1];} };

52 ms 22 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 656. 金币路径（DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。