โปรแกรมหาค่าโดยสารรถบัสขั้นต่ำสำหรับการเดินทางทุกวันใน Python

สมมติว่าเรามีรายการวันที่เรียงลำดับ days ที่ต้องขึ้นรถบัส ต้องหาค่าใช้จ่ายต่ำสุด มีบัตร 3 ประเภท: บัตร 1 วัน ราคา 2, บัตร 7 วัน ราคา 7, บัตร 30 วัน ราคา 25

ตัวอย่าง

อินพุต: days = [1, 3, 5, 6, 28]

เอาต์พุต: 9

ซื้อบัตร 7 วันตั้งแต่วันที่ 1 (ครอบคลุมถึงวันที่ 7) และบัตร 1 วันสำหรับวันที่ 28 รวม 7+2=9

ขั้นตอนการแก้ปัญหา

ใช้ Dynamic Programming (DP):

1. n = max(days)
2. แปลง days เป็น set เพื่อตรวจสอบ O(1)
3. สร้างอาร์เรย์ dp ขนาด n+1 เริ่มต้น 0
4. วน i จาก 1 ถึง n:
   • ถ้า i ไม่อยู่ใน days: dp[i] = dp[i-1]
   • ถ้าอยู่:
     • ถ้า 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)
5. คืนค่า dp[n]

การนำไปใช้ใน Python

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