পাইথনে সারাদিন ভ্রমণের জন্য ন্যূনতম বাস ভাড়া খুঁজে বের করার প্রোগ্রাম?

ধরুন আমাদের কাছে দিন নামে সাজানো সংখ্যার একটি তালিকা রয়েছে, যেখানে আমাদের প্রতিটি দিনের জন্য বাস নিতে হবে। আমাদের খুঁজে বের করতে হবে সর্বনিম্ন খরচ সব দিনের জন্য ভ্রমণ করতে। বাসের টিকিট ৩ ধরনের। 2 টাকায় 1-দিনের পাস 7 টাকায় 7-দিনের পাস 25 টাকায় 30-দিনের পাস

সুতরাং, যদি ইনপুটটি দিনের মত হয় =[1, 3, 5, 6, 28], তাহলে আউটপুট হবে 9, কারণ সর্বনিম্ন খরচটি শুরুতে 7-দিনের পাস ক্রয় করে অর্জন করা যেতে পারে এবং তারপর একটি 1- 29 তম দিনে দিন পাস।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

• n :=সর্বাধিক দিন

• দিন :=দিন থেকে একটি নতুন সেট

• dp :=[0] *(n + 1)

• 1 থেকে n + 1 রেঞ্জের জন্য, করুন

  • যদি আমি দিনের মধ্যে অ-শূন্য হয়, তাহলে

    • যদি আমি>=30, তাহলে

      • dp[i] :=ন্যূনতম dp[i - 1] + 2, dp[i - 7] + 7, dp[i - 30] + 25

    • অন্যথায় যখন i>=7, তারপর

      • dp[i] :=ন্যূনতম dp[i - 1] + 2, dp[i - 7] + 7, 25

    • অন্যথায়,

      • dp[i] :=ন্যূনতম 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]

আউটপুট

9