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的数组成本，并用inf填充
定义大小为n的数组，并以-1填充
如果非n为非零或A[n-1]与-1相同，则-
endPoint：=n-1
cost[n-1]=A[n-1]
对于初始化i：=n-2，当i>=0时，更新（将i减1），执行-
如果cost[j]+A[i]<cost[i]，则-
成本[i]：=成本[j]+A[i]
next[i]：=j
endPoint：=我
忽略以下部分，跳至下一个迭代
如果A[i]与-1相同，则-
对于范围在i+1至最小值(n-1)和i+B中的j，将j增加1-
如果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, ]