पायथन में सभी दिनों की यात्रा के लिए न्यूनतम बस किराया खोजने का कार्यक्रम?

मान लीजिए कि हमारे पास क्रमबद्ध संख्याओं की एक सूची है, जिन्हें दिन कहा जाता है, जहां हमें प्रत्येक दिन के लिए बस लेनी चाहिए। हमें सभी दिनों के लिए यात्रा करने में लगने वाली न्यूनतम लागत का पता लगाना होगा। 3 प्रकार के बस टिकट हैं। 2 रुपये में 1 दिन का पास 7 रुपये में 7 दिन का पास 25 रुपये में 30 दिन का पास

इसलिए, यदि इनपुट दिनों की तरह है =[1, 3, 5, 6, 28], तो आउटपुट 9 होगा, क्योंकि शुरुआत में 7-दिन का पास खरीदकर सबसे कम लागत प्राप्त की जा सकती है और फिर 1- 29वें दिन दिन बीतता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• n :=अधिकतम दिन

• दिन :=दिनों से एक नया सेट

• डीपी:=[0] *(एन + 1)

• 1 से n + 1 की श्रेणी में i के लिए, करें

  • अगर मैं दिनों में गैर-शून्य है, तो

    • अगर मैं>=30, तो

      • डीपी [i]:=न्यूनतम डीपी [i - 1] + 2, डीपी [i - 7] + 7, डीपी [i - 30] + 25

    • अन्यथा जब मैं>=7, तब

      • डीपी [i]:=न्यूनतम डीपी [i - 1] + 2, डीपी [i - 7] + 7, 25

    • अन्यथा,

      • dp[i] :=न्यूनतम dp[i - 1] + 2, 7

  • अन्यथा,

    • डीपी [i]:=डीपी [i - 1]

• वापसी डीपी [एन]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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