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

सॉर्ट की गई दिनों की सूची days दी गई है जिन दिनों बस यात्रा करनी है। तीन प्रकार के टिकट उपलब्ध हैं:

• 1-दिन पास: ₹2
• 7-दिन पास: ₹7
• 30-दिन पास: ₹25

सभी दिनों की यात्रा के लिए न्यूनतम लागत ढूंढें।

उदाहरण

इनपुट: days = [1, 3, 5, 6, 28]

आउटपुट: 9

व्याख्या: दिन 1 पर 7-दिन पास खरीदें (दिन 1-7 कवर), दिन 28 पर 1-दिन पास खरीदें। कुल = 7 + 2 = 9।

एल्गोरिदम (डायनामिक प्रोग्रामिंग)

1. n = max(days) (अंतिम दिन)।
2. days को सेट में बदलें O(1) लुकअप के लिए।
3. dp सरणी आकार n+1 बनाएं, dp[i] = दिन i तक की न्यूनतम लागत।
4. i = 1 से n तक:
   • यदि i यात्रा दिन नहीं है: dp[i] = dp[i-1]।
   • यदि यात्रा दिन है:
     • dp[i] = min(dp[i-1] + 2, dp[max(0,i-7)] + 7, dp[max(0,i-30)] + 25)
5. dp[n] वापस करें।

पायथन कार्यान्वयन

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

# परीक्षण
ob = Solution()
print(ob.solve([1, 3, 5, 6, 28]))  # 9
print(ob.solve([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31]))  # 17

समय जटिलता

• O(n) जहां n = max(days)।
• स्थान: O(n)।

अनुकूलन

यदि दिन बहुत बड़े हैं (जैसे 10^9), तो केवल यात्रा दिनों पर DP करें और बाइनरी सर्च का उपयोग करके पिछले वैध दिन ढूंढें। लेकिन दिए गए प्रतिबंधों के लिए यह दृष्टिकोण ठीक है।