給定旅行天數陣列
days和三種票價costs（1 天、7 天、30 天通行證），求覆蓋所有旅行日的最小花費。
Example:
Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11
Intuition
TIP
以天數為狀態的 DP：每個旅行日選擇買 1/7/30 天票，取最小成本。
dp[i]= 覆蓋到第i天的最小花費- 非旅行日不需要買票：
dp[i] = dp[i-1] - 旅行日：
dp[i] = min(dp[i-1] + costs[0], dp[max(0,i-7)] + costs[1], dp[max(0,i-30)] + costs[2])
Approaches
1. Top-Down Memoization — O(maxDay) / O(maxDay)
- Idea: 從最後一天往回遞迴，每個旅行日嘗試三種票
- Time:
O(maxDay) - Space:
O(maxDay)
class Solution {
fun mincostTickets(days: IntArray, costs: IntArray): Int {
val daySet = days.toHashSet()
val lastDay = days.last()
val memo = IntArray(lastDay + 1) { -1 }
fun dp(d: Int): Int {
if (d <= 0) return 0
if (memo[d] != -1) return memo[d]
if (d !in daySet) {
memo[d] = dp(d - 1)
} else {
memo[d] = minOf(
dp(d - 1) + costs[0],
dp(d - 7) + costs[1],
dp(d - 30) + costs[2]
)
}
return memo[d]
}
return dp(lastDay)
}
}⭐ 2. Bottom-Up DP — O(maxDay) / O(maxDay)
- Idea: 從第 1 天到最後一天逐日計算最小花費
- Time:
O(maxDay) - Space:
O(maxDay)
class Solution {
fun mincostTickets(days: IntArray, costs: IntArray): Int {
val lastDay = days.last()
val daySet = days.toHashSet()
val dp = IntArray(lastDay + 1)
for (i in 1..lastDay) {
if (i !in daySet) {
dp[i] = dp[i - 1]
} else {
dp[i] = minOf(
dp[i - 1] + costs[0],
dp[maxOf(0, i - 7)] + costs[1],
dp[maxOf(0, i - 30)] + costs[2]
)
}
}
return dp[lastDay]
}
}🔑 Takeaways
- Pattern: 日期型線性 DP — 以天數為狀態，非事件日直接繼承前一天
- Key trick: 用 HashSet 快速判斷是否為旅行日；
maxOf(0, i-k)處理邊界避免負索引