मान लीजिए एक देश है जो ट्रेन यात्रा के लिए प्रसिद्ध है। हमने एक साल पहले ही कुछ ट्रेन यात्राओं की योजना बनाई है। हमारे पास एक सरणी है जिसमें उन दिनों की सूची है जब हम यात्रा करेंगे। प्रत्येक दिन 1 से 365 तक का एक पूर्णांक है। ट्रेन टिकट तीन तरीकों से बेचे जाते हैं:
- 1-दिन का पास
costs[0]डॉलर में; - 7-दिन का पास
costs[1]डॉलर में; - 30-दिन का पास
costs[2]डॉलर में।
ये पास लगातार उतने दिनों की यात्रा की अनुमति देते हैं। उदाहरण के लिए, यदि हम दिन 2 पर 7-दिन का पास लेते हैं, तो हम लगातार 7 दिनों (2, 3, 4, 5, 6, 7, 8) तक यात्रा कर सकते हैं। हमें दिए गए दिनों की सूची में हर दिन यात्रा करने के लिए आवश्यक न्यूनतम डॉलर खोजने हैं।
उदाहरण: इनपुट days = [1,4,6,7,8,20] और costs = [2,7,15] हो, तो आउटपुट 11 होगा।
व्याख्या: दिन 1 पर 1-दिन का पास ($2), दिन 3 पर 7-दिन का पास ($7, दिन 3-9 कवर करता है), दिन 20 पर फिर 1-दिन का पास ($2)। कुल = $11।
डायनामिक प्रोग्रामिंग समाधान
dpनामक एक सरणी बनाएँ जिसका आकार 366 हो (दिन 1 से 365 तक)।j := 0(days सरणी के लिए इंडेक्स)।i = 1 से 365तक लूप चलाएँ:dp[i] = costs[0] + dp[i-1](1-दिन का पास खरीदें)।- यदि
i-7 ≥ 0, तोdp[i] = min(dp[i], dp[i-7] + costs[1])(7-दिन का पास)। - यदि
i-30 ≥ 0, तोdp[i] = min(dp[i], dp[i-30] + costs[2])(30-दिन का पास)। - यदि
j < days.size() और days[j] == i, तोj++(आज यात्रा का दिन है)। - अन्यथा
dp[i] = min(dp[i], dp[i-1])(आज यात्रा नहीं, कल की लागत आगे बढ़ाएँ)।
dp[365]लौटाएँ।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
vector<int> dp(366, 0);
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], dp[i - 7] + costs[1]);
if (i - 30 >= 0) dp[i] = min(dp[i], dp[i - 30] + costs[2]);
if (j < days.size() && days[j] == i) {
j++;
} else {
dp[i] = min(dp[i], dp[i - 1]);
}
}
return dp[365];
}
};
int main() {
vector<int> days = {1,4,6,7,8,20};
vector<int> costs = {2,7,15};
Solution ob;
cout << ob.mincostTickets(days, costs); // आउटपुट: 11
return 0;
}
इनपुट
[1,4,6,7,8,20] [2,7,15]
आउटपुट
11
