解題說明
Minimum Cost For Tickets
題目描述：
你計劃在一年中的某些天出行（給定 days 陣列）。火車票有三種：1 天票（costs[0]）、7 天票（costs[1]）、30 天票（costs[2]）。求覆蓋所有出行日的最小花費。
解題思路：
動態規劃：定義 dp[i] = 覆蓋 days[0..i-1] 所有出行日的最小花費。
更直觀的方式：定義 dp[d] = 覆蓋到第 d 天為止所有出行日的最小花費（d 為日期，從 1 到 365）。
轉移：
- 若第
d天不出行：dp[d] = dp[d-1]（不需要額外花費）。 - 若第
d天出行：- 買 1 天票：
dp[d-1] + costs[0] - 買 7 天票：
dp[max(0, d-7)] + costs[1] - 買 30 天票：
dp[max(0, d-30)] + costs[2] - 取三者最小值。
- 買 1 天票：
C++ 解法
複雜度分析
時間複雜度：O(D) — 其中 D 是最後一個出行日（最大 365）。每天的計算為 O(1)。
空間複雜度：O(D) — DP 陣列。
虛擬碼
1. Create set of travel days for O(1) lookup.
2. Initialize dp[0..lastDay] = 0.
3. For d from 1 to lastDay:
a. If d is not a travel day: dp[d] = dp[d-1].
b. Else: dp[d] = min(
dp[d-1] + costs[0],
dp[max(0, d-7)] + costs[1],
dp[max(0, d-30)] + costs[2]
).
4. Return dp[lastDay].其他解法
以出行日為索引的 DP：O(n) 時間，其中 n 是 days 的長度。定義 dp[i] = 覆蓋 days[i..n-1] 的最小花費，從後往前遍歷。用二分搜尋找到買 7 天/30 天票後覆蓋到的位置。避免遍歷非出行日，但需要二分搜尋。
記憶化遞迴：同樣的狀態定義，用遞迴實現。程式碼更直觀但有遞迴開銷。
延伸思考
- 為什麼非出行日只需
dp[d] = dp[d-1]？為什麼不考慮在非出行日購買未來的票？ - 如果票的天數不是固定的 1/7/30，而是任意的
durations陣列，如何修改 DP？ - 如果出行日跨越多年（日期範圍很大），如何優化空間？