# \[983]\[中等]\[动态规划]\[背包] 最低票价

## 题目描述

[983. 最低票价](https://leetcode-cn.com/problems/minimum-cost-for-tickets/)

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 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

## 解题思路

这是一个**完全背包**变种的问题.

物品和背包本身都很好定义. 物品就是三种票, 它们的占用的大小为它们的同行天数, 价值为它们的售价, 每种物品都可以使用无数次. 背包容量就是最大天数, 即`days`数组的最后一个元素, 一张票占用一定的天数. 这是一道求最小价值/花费的问题, 需要将`max`代替为`min`.

我们考虑当前的花费如何定义. 如果遍历天的时候, 考虑在当前天购买一张票, 计算到花费中, 那么这些票的有效期限会延伸到后面天中, 在考虑后面天的花费时就需要将前面购买票的剩余有效期, 以及不同票的不同的有效期统统考虑进去, 这种当前选择对产生的后续影响在动态规划/递归中都是不被允许的.

因此遍历到当天时, 将这天的花费定义为**之前某天购买的票在这一天有效期结束**. 这样在做动态规划时, 我们只需要考虑购买这张票前一天的累计花费, 再加上这张票的花费就是当前的累计花费了. 如果寻找当前这张票购买的前一天时越界, 说明这张票的部分天数浪费了, 因此购买前一天的花费为0.

首先题目中的一天有两种角色:

**不去旅行**

我们不需要为这一天专门买票, 因此考虑上一天的花费即可.

**去旅行**

必须买票覆盖. 考虑三种票, 分别找到它们对应的购买票前一天的累计花费, 再加上这张票的花费, 取最小值, 就是这一天的花费了.

传统的背包问题是两层循环, 完成是物品, 内层是背包限制, 即每次考虑一个物品. 但在本问题中, 物品的放入有顺序问题, 不能考虑完一个物品的所有情况, 再考虑下一个. 对于每天, 都需要考察三种票的最优情况, 取最小值.

```python
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0] * (days[-1] + 1)
        w = [1, 7, 30]
        next_travel_index = 0

        for i in range(1, days[-1] + 1):
            if i != days[next_travel_index]:
                dp[i] = dp[i - 1]
            else:
                dp[i] = float('inf')
                for j in range(3):
                    dp[i] = min(dp[i], dp[max(i - w[j], 0)] + costs[j])
                next_travel_index += 1
        return dp[-1]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/983-zui-di-piao-jia.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.