最低票价

难度: Medium

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

提示：

1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp=[0]*(days[-1]+1)
        day_index=0
        for i in range(1,len(dp)):
            if i!=days[day_index]:
                dp[i]=dp[i-1]
            else:
                
                dp[i]=min((dp[max(0,i-1)]+costs[0]),(dp[max(0,i-7)]+costs[1]),(dp[max(0,i-30)]+costs[2]))
                day_index+=1
        return dp[-1]

Explain

此题解采用动态规划的方法来确定一年中各天的最低票价。定义 dp[i] 为直到第 i 天（包括第 i 天）所需的最低票价。如果第 i 天不是旅行日，则第 i 天的费用与第 i-1 天相同，即 dp[i] = dp[i-1]。如果第 i 天是旅行日，则考虑三种购票方式：\n1. 购买为期一天的票，费用为 dp[i-1] + costs[0]；\n2. 购买为期七天的票，费用为 dp[i-7] + costs[1]，如果 i < 7，则费用为 costs[1]；\n3. 购买为期三十天的票，费用为 dp[i-30] + costs[2]，如果 i < 30，则费用为 costs[2]。\n每天的最低票价取上述三种情况的最小值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0] * (days[-1] + 1)  # 创建dp数组，长度为最后一个旅行日加一
        day_index = 0  # 用以跟踪days数组中的日子
        for i in range(1, len(dp)):
            if i != days[day_index]:
                dp[i] = dp[i - 1]  # 如果不是旅行日，费用与前一天相同
            else:
                # 计算买不同票的费用并取最小值
                dp[i] = min(dp[max(0, i - 1)] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2])
                day_index += 1  # 移动至下一个旅行日
        return dp[-1]  # 返回最后一天的最低票价

Explore

在动态规划中，为了处理7天或30天的票价，我们采用了如下方程：对于7天票，dp[i] = min(dp[i], dp[max(0, i-7)] + costs[1])；对于30天票，dp[i] = min(dp[i], dp[max(0, i-30)] + costs[2])。这种方法利用了max函数确保在计算前7天或前30天的最低票价时不会访问到数组的负索引。如果i小于7或30，直接使用costs[1]或costs[2]作为那天的最低费用。这样设计确保了每一天都是基于之前的有效天数来计算，避免了重复计算以及遗漏任何天数的情况。

在代码实现中，通过两种机制确保 `day_index` 不会超出数组 `days` 的界限。首先，在for循环中的条件是 `i <= days[-1]`，这意味着循环不会超过days数组中的最后一个旅行日。其次，在每次循环中，当 `i` 等于 `days[day_index]` 时，先进行计算后再使 `day_index` 加一，但是在加一前会通过条件 `if day_index < len(days)` 来检查是否已经是最后一个元素，从而避免超出界限。

选择从1开始循环直到 `days[-1]` 而不是直接遍历 `days` 数组是因为需要对每一天进行考虑，以确定是否购买更长期的票券更划算。如果仅遍历 `days` 数组，我们将无法考虑到连续多日旅行的情况，例如连续7天或30天的票价优势。通过设置dp数组从1到 `days[-1]` 的每一天，我们能够确保正确地评估所有可能的购票组合，并对非旅行日进行适当的处理（即继承前一天的费用）。

在计算最小票价时使用 `max` 函数是为了处理数组索引可能为负的情况。当 `i` 小于7或30时，直接使用 `i-7` 或 `i-30` 作为索引将会导致访问非法的负索引，这在Python中是不允许的。使用 `max(0, i-7)` 和 `max(0, i-30)` 确保即使在这些情况下，我们仍然访问有效的索引（最小为0），这允许我们处理边界条件，如月票或周票在月初或年初的使用情况。