解題說明
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? - 如果出行日跨越多年(日期範圍很大),如何優化空間?