🔗 🟡 983. Minimum Cost For Tickets 1786

tags: `Weekly Contest 121` `陣列(Array)` `動態規劃(Dynamic Programming)` `記憶化搜尋(Memoization)`

題意

你已經提前一年計劃了搭火車的旅行。你將旅行的那些天數由一個整數陣列 $days$ 給定，其中每一天都是 $1$ 到 $365$ 之間的整��。

火車票以 三種不同的方式 出售：

1天通行證售價為 $\text{costs[0]}$ 元，
7天通行證售價為 $\text{costs[1]}$ 元，
30天 通行證售價為 $\text{costs[2]}$ 元。

通行證在期限內可以無限次搭乘。例如，如果我們在第 $2$ 天獲得 7天通行證，那麼我們可以旅行 $7$ 天： $2$ ， $3$ ， $4$ ， $5$ ， $6$ ， $7$ 和 $8$ 。

返回在給定的天數列表中的每天旅行所需的 最低花費。

思路：動態規劃(Dynamic Programming)

方法一：記憶化搜尋(Memoization)

首先定義問題，令 $f(i)$ 表示從第 $i$ 天開始旅行的最小花費。若在第 $i$ 天需要買票，則有以下三種選擇：

購買 1天通行證，花費為 $\text{costs[0]}$ ，並遞迴計算 $f(i + 1)$ 的最小花費。
購買 7天通行證，花費為 $\text{costs[1]}$ ，並遞迴計算 $f(i + 7)$ 的最小花費。
購買 30天 通行證，花費為 $\text{costs[2]}$ ，並遞迴計算 $f(i + 30)$ 的最小花費。

我們選擇這三種方案中的最小花費作為當前天數的最小花費。此外，若 $i$ 不在 $\text{days}$ 中，則我們可以跳過這一天，直接遞迴計算 $f(i + 1)$ 的最小花費。

故我們可以得到遞迴關係式：

$f(i) = \begin{cases} \min(f(i + 1) + \text{costs[0]}, f(i + 7) + \text{costs[1]}, f(i + 30) + \text{costs[2]}) & \text{if } i \in \text{days} \\ f(i + 1) & \text{if } i \notin \text{days} \end{cases}$

而若 $i$ 超過日期的範圍，則我們不需要再買票，故 $f(i) = 0 \quad \text{if } i > D$ ，在本題中 $D = 365$ ，作為遞迴的邊界條件。而所求為 $f(1)$ ，即從第 $1$ 天開始旅行的最小花費。

由於 $days$ 是從小到大排序的，故需要旅行的第一天 $first\_day = days[0]$ 和最後一天 $\text{last\_day} = days[-1]$ 。因此遞迴邊界的條件也能寫成 $f(i) = 0 \quad \text{if } i > \text{last\_day}$ ；所求為 $f(first\_day)$ 。

最後，由於存在重複計算的子問題，我們可以使用記憶化搜尋(Memoization) 來優化遞迴過程。在 Python 中，我們可以使用 @cache 裝飾器來實現記憶化搜索；而在 C++ 中，我們可以使用 memo 陣列來實現。

複雜度分析

時間複雜度： $\mathcal{O}(D)$ ，其中 $D$ 是日期的範圍，也可以認為是最後一天的日期值。在最壞情況下，我們需要計算從第一天到最後一天每一天的最小花費。
空間複雜度： $\mathcal{O}(D)$ ，這是記憶化搜索使用的記憶陣列（或字典）的大小，以及遞迴調用堆疊的深度。

雖然時間和空間複雜度看起來與輸入大小 $N$ （旅行天數）無關，但實際上由於 $D$ 最大為 $365$ ，所以這個演算法在實踐中仍然為高效。

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        days_set = set(days)
        first_day, last_day = days[0], days[-1]

        @cache
        def dfs(i): # dfs(i) 表示從第 i 天開始旅行的最小花費
            if i > last_day:
                return 0
            if i in days_set: # 第 i 天需要買票，則比較三種買票方案的花費，取最小值
                return min(costs[0] + dfs(i + 1), costs[1] + dfs(i + 7), costs[2] + dfs(i + 30))
            else: # 第 i 天不需要買票，可以跳過
                return dfs(i + 1)
            
        return dfs(first_day)

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        unordered_set<int> days_set(days.begin(), days.end());
        int first_day = days[0], last_day = days.back();

        // memo[i] 表示從第 i 天開始旅行的最小花費
        vector<int> memo(last_day + 1, -1);
        function<int(int)> dfs = [&](int i) -> int {
            if (i > last_day) return 0;
            int &res = memo[i];
            if (res != -1) return res;
            if (days_set.count(i)) { // 第 i 天需要買票，則比較三種買票方案的花費，取最小值
                res = min({costs[0] + dfs(i + 1), costs[1] + dfs(i + 7), costs[2] + dfs(i + 30)});
            } else { // 第 i 天不需要買票，可以跳過
                res = dfs(i + 1);
            }
            return res;
        };
        return dfs(first_day);
    }
};

方法二：填表法(Tabulation)

在方法一中我們使用的是 Top-Down 的記憶化搜索，同樣地，對於動態規劃問題，我們也可以使用 Bottom-Up 的填表法(Tabulation) 。對於問題，我們使用相同的問題定義，但與記憶化搜索的自頂向下不同，我們將從最後一天開始逆向填表，逐步計算每一天的最小花費，直到到達旅行的第一天。

具體步驟如下：

初始化動態規劃表：建立一個大小為 $last\_day + 31$ 的陣列 $dp$ ，其中 $dp[i]$ 表示從第 $i$ 天開始旅行的最小花費。這裡多開了 30 天的空間，是為了避免在計算 $i + 30$ 時發生索引越界的情況。
逆序計算：從 $last\_day$ 開始，依次向前迭代到 $first\_day$ 。對於每一天 $i$ ：
- 如果 $i$ 是旅行的某一天（即 $i$ 在 $days\_set$ 中），則計算購買 1天、7天或 30天 通行證後的總花費，並選擇其中的最小值賦給 $dp[i]$ 。
- 如果 $i$ 不是旅行的某一天，則 $dp[i]$ 等於 $dp[i + 1]$ ，表示不需要額外花費。
返回結果：最後， $dp[first\_day]$ 即為從第一天開始旅行的最小花費。

這種方法避免了遞迴調用的額外開銷，通過迭代的方式有效地計算出每一天的最小花費。

複雜度分析

時間複雜度： $\mathcal{O}(D)$ 。
空間複雜度： $\mathcal{O}(D)$ ，但方法二不需要額外的遞迴調用堆疊空間。

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        days_set = set(days)
        first_day, last_day = days[0], days[-1]
        # dp[i] 表示從第 i 天開始旅行的最小花費
        dp = [0] * (last_day + 31) # 多開 30 天，避免索引越界
        for i in range(last_day, first_day - 1, -1):
            if i in days_set:
                dp[i] = min(costs[0] + dp[i + 1], costs[1] + dp[i + 7], costs[2] + dp[i + 30])
            else:
                dp[i] = dp[i + 1]
        return dp[first_day]

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        unordered_set<int> days_set(days.begin(), days.end());
        int first_day = days[0], last_day = days.back();
        // dp[i] 表示從第 i 天開始旅行的最小花費
        vector<int> dp(last_day + 31, 0); // 多開 30 天，避免索引越界
        for (int i = last_day; i >= first_day; --i) {
            if (days_set.count(i)) {
                dp[i] = min({costs[0] + dp[i + 1], costs[1] + dp[i + 7], costs[2] + dp[i + 30]});
            } else {
                dp[i] = dp[i + 1];
            }
        }
        return dp[first_day];
    }
};

方法三：三指標優化

在方法一和方法二中，時間複雜度都是基於值域 $D$ 的，而實際上我們只需要遍歷實際的旅行天數，而不需要遍歷整個日期範圍。因此，我們可以使用指標優化的填表法來減少不必要的計算。

在方法二的基礎上，我們可以進一步優化動態規劃的實現方式，通過使用指標來跟蹤購買 7天和 30天 通行證後的有效期，可以減少不必要的計算。令 $j$ 和 $k$ 分別表示若當前購買 7天和 30天 通行證，則可以不用買票的「最大」日期下標。初始化 $j$ 和 $k$ 為 $n - 1$ ，即最後一天的索引。在迭代過程中，對於每個當前的旅行日 $days[i]$ ，通過移動 $j$ 和 $k$ 指標來找到下一個需要購票的日期的位置。具體而言：

$j$ 指標移動到第一個不在 $days[i] + 7$ 天範圍內的日期，則 $j+1$ 是在 $days[i]$ 購買 7天通行證後，下次需要買票的日期下標
$k$ 指標移動到第一個不在 $days[i] + 30$ 天範圍內的日期，則 $k+1$ 是在 $days[i]$ 購買 30天 通行證後，下次需要買票的日期下標

在轉移方程中，我們只需要考慮 $j$ 和 $k$ 指標所指向的日期，而不需要遍歷整個日期範圍。

$dp[i] = \min(costs[0] + dp[i + 1], costs[1] + dp[j + 1], costs[2] + dp[k + 1])$

接著考慮如何移動 $j$ 和 $k$ 指標，對於越左邊的日期下標 $i$ ，顯然 $j$ 和 $k$ 只會越來越小，因此我們只需要在 $j$ 和 $k$ 指標所指向的日期小於 $days[i] + 7$ 和 $days[i] + 30$ 時，不斷遞減指標即可。

最後， $dp[0]$ 即為從第 $days[0]$ 天開始旅行的最小花費。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ $O (n)$ ，其中 $n$ $n$ 是 $days$ $d a ys$ 的長度。
- 雖然有兩個內部的 while 循環，但 $j$ 和 $k$ 都最多只會從 $n-1$ 減少到 $0$ ，所以總的時間複雜度仍然是 $O(n)$ 。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        # dp[i] 表示從 days[i] 開始旅行的最小花費
        dp = [0] * (n + 1)
        # j 和 k 分別表示若當前購買 7 天票和 30 天票，則可以不用買票的「最大」日期下標
        j = k = n - 1
        for i in range(n - 1, -1, -1):
            d = days[i]
            while days[j] >= d + 7:
                j -= 1
            while days[k] >= d + 30:
                k -= 1
            # 轉移方程，j + 1 和 k + 1 是下次需要買票的���期
            dp[i] = min(costs[0] + dp[i + 1], costs[1] + dp[j + 1], costs[2] + dp[k + 1])
        return dp[0]

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        // dp[i] 表示從 days[i] 開始旅行的最小花費
        vector<int> dp(n + 1, 0);
        // j 和 k 分別表示若當前購買 7 天票和 30 天票，則可以不用買票的「最大」日期下標
        int j = n - 1, k = n - 1; 
        for (int i = n - 1; i >= 0; --i) {
            while (days[j] >= days[i] + 7) --j;
            while (days[k] >= days[i] + 30) --k;
            // 轉移方程，j + 1 和 k + 1 是下次需要買票的日期
            dp[i] = min({costs[0] + dp[i + 1], costs[1] + dp[j + 1], costs[2] + dp[k + 1]});
        }
        return dp[0];
    }
};