C++ में कॉइन पाथ (Coin Path)

मान लीजिए हमारे पास एक सरणी A (इंडेक्स 1 से शुरू) है जिसमें N संख्याएं हैं: A1, A2, ..., AN और एक पूर्णांक B। पूर्णांक B दर्शाता है कि सरणी A में किसी भी इंडेक्स i से, हम सरणी में 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 से 0 तक घटाते हुए लूप चलाएं:
  • यदि A[i] -1 के समान है, तो अगले पुनरावृत्ति पर जाएं
  • j को i+1 से min(n-1, i+B) तक लूप में चलाएं:
    • यदि 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; 
    } 
}; 
int 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, ]