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, ]