資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的硬幣路徑
假設我們有一個數組 A（索引從 1 開始）包含 N 個數字：A1、A2、…、AN 和另一個整數 B。整數 B 表示從陣列 A 中的任何索引 i，我們可以跳到陣列 A 中索引為 i+1、i+2、…、i+B 的任何一個位置，如果可以跳到該位置。此外，如果我們踏上索引 i，我們必須支付 Ai 個硬幣。如果 Ai 為 -1，則表示我們無法跳到陣列中索引為 i 的位置。
現在，當我們從陣列 A 中索引為 1 的位置開始，我們的目標是使用最少的硬幣到達索引為 N 的位置。我們必須返回我們應該採取的陣列中索引的路徑（從 1 到 N 開始），以使用最少的硬幣到達索引為 N 的位置。如果我們有多條成本相同的路徑，我們必須找到字典序最小的路徑。如果我們沒有這樣的到達索引為 N 的可能路徑，我們將返回一個空陣列。
因此，如果輸入類似於 [1,2,4,-1,2]，2，則輸出將為 [1,3,5]
為了解決這個問題，我們將遵循以下步驟：
n := A 的大小
定義一個數組 ret
定義一個大小為 n 的陣列 cost，並用 inf 填充它
定義一個大小為 n 的陣列 next，並用 -1 填充它
如果 n 非零或 A[n - 1] 與 -1 相同，則：
endPoint := n - 1
cost[n - 1] = A[n - 1]
對於初始化 i := n - 2，當 i >= 0 時，更新（將 i 減小 1），執行：
如果 A[i] 與 -1 相同，則：
忽略以下部分，跳到下一個迭代
對於 j 在範圍 i + 1 到最小值（n - 1）和 i + B 之間，將 j 增加 1：
如果 cost[j] + A[i] < cost[i]，則：
cost[i] := cost[j] + A[i]
next[i] := j
endPoint := i
如果 endPoint 不等於 0，則：
返回空陣列
對於 endPoint 不等於 -1，更新 endPoint = next[endPoint]，執行：
在 ret 的末尾插入 endPoint + 1
返回 ret
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> cheapestJump(vector<int>& A, int B) {
int n = A.size();
vector <int> ret;
vector <int> cost(n, 1e9);
vector <int> next(n, -1);
if(!n || A[n - 1] == -1) return {};
int endPoint = n - 1;
cost[n - 1] = A[n - 1];
for(int i = n - 2; i >= 0; i--){
if(A[i] == -1) continue;
for(int j = i + 1 ; j <= min(n - 1, i + B); j++){
if(cost[j] + A[i] < cost[i]){
cost[i] = cost[j] + A[i];
next[i] = j;
endPoint = i;
}
}
}
if(endPoint != 0) return {};
for(;endPoint != - 1; endPoint = next[endPoint]){
ret.push_back(endPoint + 1);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,4,-1,2};
print_vector(ob.cheapestJump(v, 2));
}輸入
{1,2,4,-1,2}, 2輸出
[1, 3, 5, ]
183 次檢視
