数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
