মনে করুন একটি দেশ আছে যেখানে ট্রেন ভ্রমণ জনপ্রিয়। আমরা এক বছর আগে থেকে কিছু ট্রেন ভ্রমণ পরিকল্পনা করেছি। আমাদের কাছে একটি অ্যারে আছে যা বছরের যেসব দিনে আমরা ভ্রমণ করবো সেগুলো ধারণ করে। প্রতিটি দিন ১ থেকে ৩৬৫ পর্যন্ত একটি পূর্ণসংখ্যা। ট্রেন টিকেট তিন ভিন্ন প্যাকেজে বিক্রি হয়:
- ১-ডে পাস:
costs[0]ডলার - ৭-ডে পাস:
costs[1]ডলার - ৩০-ডে পাস:
costs[2]ডলার
এই পাসগুলো ক্রমাগত 그만 দিন ভ্রমণের অনুমতি দেয়। উদাহরণস্বরূপ, যদি আমরা দিন ২-তে একটি ৭-ডে পাস কিনি, তবে আমরা দিন ২ থেকে ৮ পর্যন্ত (২, ৩, ৪, ৫, ৬, ৭, ৮) ভ্রমণ করতে পারব। দো দিনের লিস্ট অনুযায়ী প্রতিটি দিনে ভ্রমণের জন্য ন্যূনতম কত ডলার খরচ হবে তা বের করতে হবে।
উদাহরণ
ইনপুট: days = [1,4,6,7,8,20], costs = [2,7,15]
আউটপুট: 11
ব্যাখ্যা: দিন ১-তে ১-ডে পাস কেনা হয় (costs[0] = $2), দিন ৩-তে ৭-ডে পাস কেনা হয় (costs[1] = $7, যা দিন ৩-৯ কভার করে), এবং দিন ২০-তে আবার ১-ডে পাস (costs[0] = $2)। মোট খরচ = $11।
ডাইনামিক প্রোগ্রামিং সমাধান
dpনামক একটি অ্যারে তৈরি করুন সাইজ ৩৬৬ (দিন ১ থেকে ৩৬৫)।j := 0(ভ্রমণের দিনের অ্যারে ট্র্যাক করার জন্য)।i = 1থেকে365পর্যন্ত লুপ চালান:dp[i] = costs[0] + dp[i-1](১-ডে পাস কেনার খরচ)।- যদি
i-7 >= 0হয়, তবেdp[i] = min(dp[i], dp[i-7] + costs[1])(৭-ডে পাস কেনার খরচ)। - যদি
i-30 >= 0হয়, তবেdp[i] = min(dp[i], dp[i-30] + costs[2])(৩০-ডে পাস কেনার খরচ)। - যদি
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> v = {1, 4, 6, 7, 8, 20};
vector<int> v1 = {2, 7, 15};
Solution ob;
cout << ob.mincostTickets(v, v1);
return 0;
}
ইনপুট
[1,4,6,7,8,20] [2,7,15]
আউটপুট
11
