P3396. Wonderland

解题思路

令 n 表示游玩的次数。令 times = [1, 3, 7, 30]，和 cost 数组相对应，表示一张门票的有效期。 我们只能一天天旅游，只能过完前面的日子才能过后面的日子。

dp 数组的含义是什么？

dp 数组是一个长度为 n+1 的一维列表。 dp[i] 表示以第 i 次游玩完成后所需要花费的最小价格。注意这里假设 days 数组从下标 1 开始。 dp[n] 即为答案。

动态转移方程是什么？

计算 dp[i] 的值。 对于前 i 个次游玩，假设 j <= i，如果第 j 次游玩到第 i 次游玩之间的天数可以由第 k（0、1、2、3）种票完全覆盖（即 days[i] - days[j] + 1 <= times[k]），那么说明这段旅程可以花费 cost[k] 购买第 k 种票，因此有：

即从第 j-1 次游玩转移而来。

举个例子，存在 days = [0, 1, 4, 6, 8] 天都要游玩，那么第 8 天的游玩的情况即 dp[4] 的计算：

• 考虑从第 8 天即从 days[4] 开始用某种票能够覆盖 8-8 天这个区间，可以购买 1、3、7、30 日票来完成，那么应该在第 6 天的基础上即 dp[3] 转移过来。
• 考虑从第 6 天即从 days[3] 开始用某种票能够覆盖 6-8 这个区间，可以购买 3、7、30 日票来完成，那么应该在第 4 天的基础上即 dp[2] 转移过来。
• 考虑从第 4 天开始用某种票能够覆盖 4-8 这个区间，可以购买 7、30 日票来完成，那么应该在第 1 天的基础上即 dp[1] 转移过来。
• 考虑从第 1 天开始用某种票能够覆盖 1-8 这个区间，可以购买 30 日票来完成，那么应该在第 0 天的基础上即 dp[0] 转移过来。

对于第 i 次游玩，选择一个最佳的覆盖方式即可，因此反复地取最小值，即：

对应的代码框架如下：

dp 数组如何初始化？

一开始没有进行任何游玩，因此 dp[0] = 0；后来的所有值初始化成无穷大即可。

复杂度分析 设 n 为游玩日期数组的长度，即小慕需要入园的总次数（题面说明游玩计划在一年之内，n 不会超过一年的天数）。

• 时间复杂度：O(n^2)。代码主体是三层循环：外层 i 遍历每一次游玩，内层 j 枚举当前这张票从第几次游玩开始覆盖，这两层合计约 n^2/2 次；最内层 k 只遍历 4 种固定票型，是常数因子。因此瓶颈在 i 与 j 的双重循环，总时间为 O(n^2 × 4)，即 O(n^2)。
• 空间复杂度：O(n)。除输入的票价与日期数组外，只额外开了一个长度为 n+1 的一维 dp 数组，dp[i] 记录完成前 i 次游玩的最小花费。

补充说明：由于票的有效期最长为 30 天，当 days[i] - days[j] + 1 > 30 时四种票都无法覆盖，内层的 j 其实可以提前终止来剪枝；但在本题一年以内的数据规模下，O(n^2) 的朴素写法已经足够。