题目描述

某个国家流行火车出行，你已经计划好了一年中出行的日子，以一个数组 days 的形式给出。每一天都是 1 到 365 的整数。

火车票以如下三种方式售出：

• 一日通票售 costs[0] 美元；
• 七日通票售 costs[1] 美元；
• 三十日通票售 costs[2] 美元；

通过允许多天连续的出行。比如，如果我们在第二天购买了七日的通票，则我们可以在 2, 3, 4, 5, 6, 7, 8 天出行。

返回最小的花费，使得你能按照列表上的日期出行。

样例

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释：
比如，下面是一种购票方式：
第 1 天，购买一日的通票，花费 costs[0] = $2，满足第 1 天。
第 3 天，购买七日的通票，花费 costs[1] = $7，满足第 3, 4, ..., 9 天。
第 20 天，购买一日的通票，花费 costs[0] = $2，满足第 20 天。
总共花费 $11 满足了所有的出行日期。

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
比如，下面是一种购票方式：
第 1 天，购买三十日的通票，花费 costs[2] = $15，满足第 1, 2, ..., 30 天。
第 31 天，购买一日的通票，花费 costs[0] = $2，满足第 31 天。
总共花费 $17 满足了所有的出行日期。

注意

• 1 <= days.length <= 365
• 1 <= days[i] <= 365
• days 是严格递增的。
• costs.length == 3
• 1 <= costs[i] <= 1000

算法

(动态规划) $O(n)$

1. 状态 $f(i)$ 表示满足了前 $i$ 个日期的最少花费。日期和状态的下标都从 1 开始。
2. 初始值 $f(0) = 0$，其余为正无穷。可以想到，每次买票一定选在某个存在的日期。
3. 转移时，倒序枚举 $j$，使得 days[j] 和 days[i] 小于 30 天，则转移，$f(i) = \min(f(i), f(j - 1) + cost(k))$，$k$ 表示对应的价钱。如果两个日期差距大于等于 30 天，则无需继续枚举。
4. 最终答案为 $f(n)$。

时间复杂度

• 状态数为 $O(n)$ 个，注意到每次转移最多只有 30 个，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的数组存储状态，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> f(n + 1, INT_MAX);

        f[0] = 0;
        days.insert(days.begin(), 0);

        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 1 && days[i] - days[j] < 30; j--) {
                if (days[i] - days[j] < 1)
                    f[i] = min(f[i], f[j - 1] + costs[0]);

                if (days[i] - days[j] < 7)
                    f[i] = min(f[i], f[j - 1] + costs[1]);

                if (days[i] - days[j] < 30)
                    f[i] = min(f[i], f[j - 1] + costs[2]);
            }
        }

        return f[n];
    }
};