983. Minimum Cost For Tickets

Medium

Description

給定旅行天數陣列 days 和三種票價 costs（1 天、7 天、30 天通行證），求覆蓋所有旅行日的最小花費。

Example:

Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11

Intuition#

以天數為狀態的 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)

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#

概念: 從第 1 天到最後一天逐日計算最小花費
時間複雜度: O(maxDay)
空間複雜度: 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 — 以天數為狀態，非事件日直接繼承前一天
關鍵技巧: 用 HashSet 快速判斷是否為旅行日；maxOf(0, i-k) 處理邊界避免負索引