सी++ में टिकटों की न्यूनतम लागत

मान लीजिए कोई देश है, जो ट्रेन यात्रा के लिए लोकप्रिय है, हमने एक साल पहले यात्रा करने वाली किसी ट्रेन की योजना बनाई है। हमारे पास एक सरणी है, जो उस वर्ष के दिनों को पकड़ रही है जिसमें हम यात्रा करेंगे। प्रत्येक दिन 1 से 365 तक का एक पूर्णांक है। ट्रेन के टिकट तीन अलग-अलग तरीकों से बेचे जाते हैं -

• 1 दिन का पास [0] डॉलर में बेचा जाता है;

• 1 दिन का पास [0] डॉलर में बेचा जाता है;

• 30-दिन का पास [2] डॉलर में बेचा जाता है।

यहां के पास कई दिनों तक लगातार यात्रा करने की अनुमति देते हैं। उदाहरण के लिए, यदि हमें 2 दिन में एक 7-दिन का पास मिलता है, तो हम 7 दिनों के लिए यात्रा कर सकते हैं:लगातार दिन (2, 3, 4, 5, 6, 7, और 8)। हमें दी गई दिनों की सूची में प्रतिदिन यात्रा करने के लिए आवश्यक न्यूनतम डॉलर की संख्या ज्ञात करनी है। तो अगर इनपुट [1,4,6,7,8,20] जैसा है और लागत [2,7,15] है, तो आउटपुट 11 होगा।

1 दिन, हमने लागतों के लिए 1 दिन का पास खरीदा है [0] =$ 2, जो दिन 1 को कवर कर रहा है, 3 दिन पर, हमने 7 दिन का पास खरीदा है, इसलिए लागत [1] =$ 7, जो कि 3 से 9 दिनों को कवर कर रहा है , और 20वें दिन, फिर से 1 दिन के लिए पास खरीदा, इसलिए लागत[0] =$2, जो 20वें दिन को कवर कर रही है। इसलिए कुल $11 खर्च किए गए।

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

• dp नामक एक सरणी बनाएं, आकार 366

• जे:=0

• मेरे लिए 1 से 366 की सीमा में

  • डीपी [i]:=लागत [0] + डीपी [i - 1]

  • अगर मैं - 7> =0, तो डीपी [i]:=न्यूनतम डीपी [i - 7] + लागत [1] और डीपी [i]

  • अगर मैं - 30> =0, तो डीपी [i]:=न्यूनतम डीपी [i - 30] + लागत [2] और डीपी [i]

  • यदि j <दिनों की सरणी और दिनों का आकार [j] =i, तो j को 1 से बढ़ाएँ, अन्यथा dp[i] :=न्यूनतम dp[i], dp[i – 1]

• वापसी डीपी [365]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int mincostTickets(vector<int>& days, vector<int>& costs) {
      vector <int> dp(366);
      int j = 0;
      for(int i = 1; i < 366; i++){
         dp[i] = costs[0] + dp[i - 1];
         if(i - 7 >= 0){
            dp[i] = min(dp[i - 7] + costs[1], dp[i]);
         }
         if(i - 30 >= 0){
            dp[i] = min(dp[i - 30] + costs[2], dp[i]);
         }
         if(j < days.size() && days[j] == i){
            j++;
         }else
            dp[i] = min(dp[i], dp[i - 1]);
      }
      return dp[365];
   }
};
main(){
   vector<int> v = {1,4,6,7,8,20};
   vector<int> v1 = {2,7,15};
   Solution ob;
   cout << (ob.mincostTickets(v, v1));
}

इनपुट

[1,4,6,7,8,20]
[2,7,15]

आउटपुट

11