C++ এ কয়েন পাথ

ধরুন আমাদের একটি অ্যারে রয়েছে (সূচী 1 থেকে শুরু হয়) N সংখ্যাগুলির সাথে:A1, A2, ..., AN এবং আরেকটি পূর্ণসংখ্যা B। পূর্ণসংখ্যা B নির্দেশ করে যে যেকোন সূচক থেকে আমি অ্যারেতে আছে, আমরা যে কোনোটিতে যেতে পারি। অ্যারের মধ্যে একটি স্থান সূচীকৃত i+1, i+2, …, i+B যদি এই স্থানে লাফ দেওয়া যায়। এছাড়াও, যদি আমরা সূচক i-এ পা রাখি, তাহলে আমাদের Ai পরিমাণ কয়েন দিতে হবে। Ai যদি -1 হয়, তাহলে এর মানে আমরা অ্যারেতে i সূচীকৃত স্থানে যেতে পারব না।

এখন, যখন আমরা অ্যারে এ সূচীকৃত 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 এর মত হয়, তাহলে −

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • j এর জন্য i + 1 থেকে সর্বনিম্ন (n - 1) এবং i + B এর মধ্যে, j 1 দ্বারা বাড়ান −

    • যদি খরচ[j] + A[i] <খরচ[i] হয়, তাহলে −

      • খরচ[i] :=খরচ[j] + A[i]

      • পরবর্তী[i] :=j

      • endPoint :=i

• যদি endPoint 0 এর সমান না হয়, তাহলে −

  • খালি অ্যারে ফেরত দিন

• endPoint-এর জন্য -1 এর সমান নয়, endPoint =পরবর্তী[endPoint], করুন −

  • ret এর শেষে endPoint + 1 সন্নিবেশ করুন

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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