Chương trình tìm chi phí vé xe buýt tối thiểu cho tất cả ngày đi trong Python

Cho danh sách ngày days (đã sắp xếp) cần đi xe buýt. Có 3 loại vé:

• Vé 1 ngày: $2
• Vé 7 ngày: $7
• Vé 30 ngày: $25

Tìm chi phí tối thiểu để đi xe tất cả các ngày trong danh sách.

Ví dụ

Đầu vào: days = [1, 3, 5, 6, 28]

Mua vé 7 ngày từ ngày 1 (giá $7) + vé 1 ngày ngày 28 ($2) → tổng $9.

Thuật toán (Dynamic Programming)

1. n = max(days), tạo set travel_days để tra cứu O(1).
2. Mảng dp kích thước n+1, dp[i] = chi phí tối thiểu đến ngày i.
3. Duyệt i = 1..n:
   • Nếu i không phải ngày đi: dp[i] = dp[i-1].
   • Nếu là ngày đi:
     • dp[i] = min(dp[i-1] + 2, dp[max(0,i-7)] + 7, dp[max(0,i-30)] + 25)
4. Trả về dp[n].

Triển khai Python

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]

# Test
ob = Solution()
print(ob.solve([1, 3, 5, 6, 28]))  # Output: 9

Độ phức tạp

• Thời gian: O(max_day) ≈ O(365) thực tế.
• Không gian: O(max_day).

Đây là bài toán "Minimum Cost For Tickets" (LeetCode 983).