983. Minimum Cost For Tickets

題目網址：https://leetcode.cn/problems/minimum-cost-for-tickets/

題意：給一整數 array days 代表旅行的日子, 其中 1 ≤ days[i] ≤ 365。

車票有三種不同的銷售方式：

一張 1-day 通行證的售價為 costs[0]

一張 7-day 通行證的售價為 costs[1]

一張 30-day 通行證的售價為 costs[2]

通行證允許數天無限制的旅行。例如, 如果我們在第 2 天獲得一張 7-day 的通行證, 則可以連著旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回滿足 days 中每一天都旅行所需的最低花費。

注意：days 是嚴格遞增的。

Solution：

想法：利用 DP

1. 定義狀態：

dp[i]：代表旅行到第 i 天所需的最小花費

2. 得到轉移方程：

若 i not in days：也就是第 i 天實際上不用旅行, 因此直接使用上一次的狀態即可
➔ dp[i] = dp[i - 1]

i in days：有三種選擇, 取其中最小的

第 i 天購買 1-day 通行證, 總花費 = 前 i - 1 天的花費 + costs[0]
➔ dp[i] = dp[i - 1] + costs[0]

第 i - 6 天購買 7-day 通行證, 總花費 = 前 i - 7 天的花費 + costs[1]
➔ dp[i] = dp[i - 7] + costs[1]

第 i - 29 天購買 30-day 通行證, 總花費 = 前 i - 30 天的花費 + costs[2]
➔ dp[i] = dp[i - 30] + costs[2]

3. 初始化：

dp[0]：旅行到第 0 天所需的最小花費為 0

4. 你可能會問：「為什麼不能用其他的組合？e.g. 第 i - 2 天時購買 7-day 的通行證, 這樣一樣可以 cover 到第 i 天」

定理：當 j < i 時, dp[j] ≤ dp[i] 恆成立

反證法：假設 dp[j] > dp[i], 那第 j 天時就使用第 i 天的方案, 剩下的天數寧可浪費掉, 這樣一來 dp[j] = dp[i] ➔ 與一開始的假設dp[j] > dp[i] 相互矛盾, 故 dp[j] ≤ dp[i]

由上述定理可得知, dp[i - 7] ≤ dp[i - 2], 故只需考慮 dp[i - 7] + costs[1] 就好, 而不需考慮 dp[i - 2] + costs[1]

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        unordered_set<int> s(days.begin(), days.end());
        vector<int> dp(days.back() + 1, 0); // + 1 是因為含第 0 天

        for (int i = 1; i <= days.back(); ++i) {
            dp[i] = dp[i - 1];

            if (s.find(i) != s.end()) {
                // 注意 i - k 時可能會越界, k = 1, 7, 30
                const int day = dp[max(0, i - 1)] + costs[0];
                const int week = dp[max(0, i - 7)] + costs[1];
                const int month = dp[max(0, i - 30)] + costs[2];
                dp[i] = min({day, week, month});
            }
        }

        return dp[days.back()];
    }
};

time：$O(1)$ ➔ $O(365)$, 因為 for loop 取決於 days.back()
space：$O(1)$ ➔ $O(365)$, 因為 dp 的大小取決於 days.back()