线性动态规划：最低票价问题 题目描述 你计划在一年中的某些天（用严格递增的整数数组 days 表示）进行旅行。火车票有三种销售方式： 1 日票： costs[0] 元，有效期为 1 天。 7 日票： costs[1] 元，有效期为连续的 7 天。 30 日票： costs[2] 元，有效期为连续的 30 天。 票允许在有效期内的任意一天开始使用。例如，购买 7 日票后，可以在第 1 天开始使用，覆盖第 1~7 天；或在第 2 天开始使用，覆盖第 2~8 天。 你的目标是用最少的钱覆盖所有旅行天数（ days 中的所有天）。返回最低总花费。 示例 输入： days = [1,4,6,7,8,20] , costs = [2,7,15] 输出： 11 解释：购买 7 日票（覆盖第 1~7 天，花费 7 元）和 1 日票（覆盖第 20 天，花费 2 元），总花费 11 元。 解题过程 步骤 1：定义状态 设 dp[i] 表示覆盖从第 1 天到第 i 天（ i 为 days 中的某个旅行日）所需的最低花费。注意： i 是 days 的索引，但实际计算中需按日历天数处理。 步骤 2：状态转移思路 对于每个旅行日 days[i] ，考虑三种购票方式： 买 1 日票 ：花费 costs[0] ，覆盖当天，则总花费为 dp[i-1] + costs[0] 。 买 7 日票 ：花费 costs[1] ，覆盖包括 days[i] 在内的连续 7 天。找到最早无法被此票覆盖的旅行日索引 j （即 days[j] < days[i] - 6 的最大 j ），则总花费为 dp[j] + costs[1] 。若所有旅行日都在 7 天内，则 j = -1 ，花费为 costs[1] 。 买 30 日票 ：同理，花费 costs[2] ，找到 days[j] < days[i] - 29 的最大 j 。 转移方程 ： dp[i] = min(dp[i-1] + costs[0], dp[j7] + costs[1], dp[j30] + costs[2]) 其中 j7 和 j30 是对应票覆盖范围前的最后一个旅行日索引。 步骤 3：处理边界 若 i=0 （第一个旅行日）， dp[-1] 视为 0（表示第 0 天之前无花费）。 需快速找到 j7 和 j30 ：由于 days 严格递增，可用二分查找或指针遍历。 步骤 4：具体计算（以示例为例） days = [1,4,6,7,8,20] , costs = [2,7,15] i=0 （第 1 天）： 1 日票： dp[-1] + 2 = 0 + 2 = 2 7 日票：覆盖第 1~7 天， j7 = -1 ，花费 7 30 日票：覆盖第 1~30 天， j30 = -1 ，花费 15 dp[0] = min(2,7,15) = 2 i=1 （第 4 天）： 1 日票： dp[0] + 2 = 2 + 2 = 4 7 日票：覆盖第 4~10 天，检查第 4 天前是否有旅行日不在覆盖内？第 1 天（1 < 4-6? 4-6=-2，1>-2，说明第 1 天在覆盖内？不对！覆盖开始于第 4 天时，覆盖区间为 [ 4,10]，第 1 天不在内）。正确方法：找 days[j] < 4-6 = -2 的最大 j ，无，故 j7 = -1 ，花费 7。 30 日票：同理， j30 = -1 ，花费 15 dp[1] = min(4,7,15) = 4 i=2 （第 6 天）： 1 日票： dp[1] + 2 = 4 + 2 = 6 7 日票：覆盖开始于第 6 天，区间 [ 6,12]。找 days[j] < 6-6=0 的最大 j ，无， j7=-1 ，花费 7。 dp[2] = min(6,7,15) = 6 i=3 （第 7 天）： 1 日票： dp[2] + 2 = 6 + 2 = 8 7 日票：覆盖 [ 7,13]。找 days[j] < 7-6=1 的最大 j ，即第 1 天（1）满足，但 1>=1? 不，1<1 不成立？注意： days[j] < 1 的天数不存在（最小为 1），所以 j7=-1 ，花费 7。 但若从第 1 天开始买 7 日票，覆盖 [ 1,7]，则第 7 天已被覆盖。正确做法： 允许票从任意早于等于当前天的日期开始 。因此需检查三种情况： 票从第 7 天开始：覆盖 [ 7,13]，未覆盖第 1、4、6 天，需额外覆盖这些天，但这样不如直接算 dp[j] + cost 。我们之前的方法实际已隐含此意：找 j 使得 days[j] < days[i] - duration + 1 （即票覆盖开始于 days[i]-duration+1 时，最早未覆盖的旅行日）。 更准确：对于 7 日票，覆盖区间为 [days[i]-6, days[i]] （因为票可从区间内任意天开始，但为覆盖 days[i] ，最晚开始日为 days[i] ，最早为 days[i]-6 。为最小化花费，我们让票尽可能覆盖更多已处理的天，即从最早可能开始日（ days[i]-6 ）开始覆盖）。因此找 days[j] < days[i]-6 的最大 j ，此 j 之前的日期需单独覆盖， j+1 到 i 的日期被此票覆盖。 对第 7 天： days[i]-6=1 ，找 days[j] < 1 的 j ，无， j7=-1 ，花费 7。 30 日票： days[i]-29=-22 ， j30=-1 ，花费 15 dp[3] = min(8,7,15) = 7 i=4 （第 8 天）： 1 日票： dp[3] + 2 = 7 + 2 = 9 7 日票：覆盖区间 [ 2,8]（从第 8 天倒推 6 天到第 2 天）。找 days[j] < 2 的最大 j ，无， j7=-1 ，花费 7？但第 1 天（1）不在 [ 2,8] 内！所以 j7 应为 0（第 1 天需单独覆盖）。错误： days[j] < 2 的最大 j 应满足 days[j] < 2 ， days[0]=1 < 2 成立，所以 j7=0 ，花费 dp[0] + 7 = 2 + 7 = 9 。 30 日票： j30=-1 ，花费 15 dp[4] = min(9,9,15) = 9 i=5 （第 20 天）： 1 日票： dp[4] + 2 = 9 + 2 = 11 7 日票：覆盖 [ 14,20]，找 days[j] < 14 的最大 j 。 days[4]=8 < 14 ， j7=4 ，花费 dp[4] + 7 = 9 + 7 = 16 30 日票：覆盖 [ -9,20]，找 days[j] < -9 的 j ，无， j30=-1 ，花费 15 dp[5] = min(11,16,15) = 11 最终结果： dp[5] = 11 。 关键点 票的覆盖区间是连续的，且可从区间内任意天开始。 通过找 j 将问题划分为子问题： j 是最后一个未被当前票覆盖的旅行日索引。 时间复杂度：O(n) 或 O(n log n)，取决于查找 j 的方式（可用指针优化到 O(n)）。