পাইথনে সকল দিন বাসে যাত্রা করার জন্য ন্যূনতম ভাড়া বের করার প্রোগ্রাম

ধরা যাক days নামক একটি সর্টেড সংখ্যার লিস্ট রয়েছে, যেখানে প্রতিটি দিন বাসে যাত্রা করতে হবে। আমাদের সব দিন যাত্রা করার জন্য ন্যূনতম খরচ বের করতে হবে। তিন ধরনের বাস টিকিট রয়েছে:

১-দিনের পাস: ২ টাকা
৭-দিনের পাস: ৭ টাকা
৩০-দিনের পাস: ২৫ টাকা

উদাহরণ

ইনপুট: days = [1, 3, 5, 6, 28]

আউটপুট: 9

ব্যাখ্যা: শুরুতে ৭-দিনের পাস কিনে এবং ২৯তম দিনে ১-দিনের পাস কিনে ন্যূনতম খরচ ৯ টাকা হয়।

সমাধানের ধাপসমূহ

n := max(days)
days := set(days) (O(1) লুকআপের জন্য)
dp := [0] * (n + 1)
i = 1 থেকে n পর্যন্ত লুপ চালান:
- যদি i in days হয়, তবে:
  - যদি i >= 30 হয়, তবে dp[i] := min(dp[i-1]+2, dp[i-7]+7, dp[i-30]+25)
  - অন্যথায় যদি i >= 7 হয়, তবে dp[i] := min(dp[i-1]+2, dp[i-7]+7, 25)
  - অন্যথায়, dp[i] := min(dp[i-1]+2, 7)
- অন্যথায়, dp[i] := dp[i-1]
dp[n] ফেরত দিন

পাইথন ইমপ্লিমেন্টেশন

class Solution:
    def solve(self, days):
        n = max(days)
        days = set(days)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            if i in days:
                if i >= 30:
                    dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, dp[i - 30] + 25)
                elif i >= 7:
                    dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, 25)
                else:
                    dp[i] = min(dp[i - 1] + 2, 7)
            else:
                dp[i] = dp[i - 1]
        return dp[n]

ob = Solution()
days = [1, 3, 5, 6, 28]
print(ob.solve(days))

ইনপুট

[1, 3, 5, 6, 28]