C++ . में सिक्का पथ

मान लीजिए कि हमारे पास एन संख्याओं के साथ एक सरणी ए (सूचकांक 1 से शुरू होता है:ए 1, ए 2, ..., एएन और एक अन्य पूर्णांक बी। पूर्णांक बी दर्शाता है कि किसी भी इंडेक्स से सरणी ए में है, हम किसी भी पर जा सकते हैं सरणी में एक स्थान A अनुक्रमित i+1, i+2,…, i+B यदि इस स्थान पर छलांग लगाई जा सकती है। इसके अलावा, यदि हम सूचकांक i पर कदम रखते हैं, तो हमें एआई राशि के सिक्कों का भुगतान करना होगा। अगर एआई -1 है, तो इसका मतलब है कि हम एरे में इंडेक्स किए गए स्थान पर नहीं जा सकते।

अब, जब हम एरे ए में अनुक्रमित 1 स्थान से शुरू करते हैं, और हमारा उद्देश्य न्यूनतम सिक्कों का उपयोग करके अनुक्रमित एन स्थान तक पहुंचना है। हमें न्यूनतम सिक्कों का उपयोग करके अनुक्रमित एन के स्थान पर पहुंचने के लिए हमें जिस सरणी में ले जाना चाहिए, उसमें अनुक्रमित का पथ (1 से एन तक) वापस करना होगा। यदि हमारे पास एक ही लागत के साथ कई पथ हैं, तो हमें शब्दकोष की दृष्टि से सबसे छोटा ऐसा पथ खोजना होगा। और अगर हमारे पास अनुक्रमित एन स्थान तक पहुंचने के लिए ऐसा कोई संभावित मार्ग नहीं है तो हम एक खाली सरणी वापस कर देंगे।

इसलिए, यदि इनपुट [1,2,4,-1,2], 2 जैसा है, तो आउटपुट [1,3,5]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=A का आकार

• एक सरणी रिट परिभाषित करें

• आकार n की एक सरणी लागत को परिभाषित करें, और इसे inf से भरें

• आकार n के आगे एक सरणी परिभाषित करें, और इसे -1 से भरें

• यदि नहीं n गैर-शून्य है या A[n - 1] -1 के समान है, तो -

  • समापन बिंदु :=n - 1

• लागत [एन - 1] =ए [एन -1]

• इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −

  करें

  • अगर A[i] -1 के समान है, तो -

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • j की श्रेणी में i + 1 से न्यूनतम (n - 1) और i + B के लिए, j को 1 से बढ़ाएँ -

    • अगर लागत [जे] + ए [i] <लागत [i], तो -

      • लागत[i] :=लागत[j] + A[i]

      • अगला[i] :=j

      • समापन बिंदु:=मैं

• अगर एंडपॉइंट 0 के बराबर नहीं है, तो -

  • खाली सरणी लौटाएं

• एंडपॉइंट के लिए -1 के बराबर नहीं है, एंडपॉइंट अपडेट करें =अगला [एंडपॉइंट], करें -

  • रिट के अंत में एंडपॉइंट + 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, ]