C++のコインパス

N個の数値（A1、A2、...、AN、および別の整数B）を持つ配列A（インデックスは1から始まる）があるとします。整数Bは、任意のインデックスから配列A内のiである場合、任意の配列にジャンプできることを示します。配列Aの場所の1つは、この場所にジャンプできる場合、i + 1、i + 2、…、i+Bのインデックスが付けられます。また、インデックスiを踏むと、Aiのコインを支払う必要があります。 Aiが-1の場合、配列内のインデックスが付けられたiの場所にジャンプできないことを意味します。

ここで、配列Aのインデックス1の場所から開始し、最小のコインを使用してインデックスNの場所に到達することを目的としています。最小のコインを使用してNのインデックスが付けられた場所に到達するために、配列内のインデックスのパス（1から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

• コスト[n-1]=A [n-1]

• 初期化i：=n-2の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • A [i]が-1と同じ場合、-

    • 次の部分を無視し、次の反復にスキップします

  • 範囲i+1から最小値（n --1）およびi + Bのjの場合、jを1-

    増やします。

    • cost [j] + A [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, ]