ধরুন একটি দেশ আছে, যা ট্রেন ভ্রমণের জন্য জনপ্রিয়, আমরা এক বছর আগে থেকে কিছু ট্রেন ভ্রমণের পরিকল্পনা করেছি। আমাদের একটি অ্যারে আছে, যেটি বছরের দিনগুলিকে ধরে রাখে যা আমরা ভ্রমণ করব। প্রতিটি দিন হল 1 থেকে 365 পর্যন্ত একটি পূর্ণসংখ্যা। ট্রেনের টিকিট তিনটি ভিন্ন উপায়ে বিক্রি হয় −
-
একটি 1-দিনের পাস খরচ[0] ডলারে বিক্রি করা হয়;
-
একটি 1-দিনের পাস খরচ[0] ডলারে বিক্রি করা হয়;
-
একটি 30-দিনের পাস খরচ[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 খরচ হয়েছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
366 আকারের dp নামে একটি অ্যারে তৈরি করুন
-
j :=0
-
আমি 1 থেকে 366 রেঞ্জের মধ্যে
-
dp[i] :=খরচ[0] + dp[i - 1]
-
যদি i – 7>=0 হয়, তাহলে dp[i] :=ন্যূনতম dp[i - 7] + খরচ[1] এবং dp[i]
-
যদি i – 30>=0, তাহলে dp[i] :=ন্যূনতম dp[i - 30] + খরচ[2] এবং dp[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
