在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年时间里，你要旅行的日子将以名为 days 的数组给出。每一项是一个 1 到 365 的整数。
火车票有三种不同的销售方式：
一张为期一天的通行证售价为cost[0]美元
一张为期七天的通行证售价为cost[1]美元
一张为期三十天的通行证售价为cost[2]美元
通行证运行数天无限制的旅行。例如，我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定列表 days 中列出的每一天的旅行所需的最低消费。
CPP代码：
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
// 获取旅行的最后一天
int lastDay = days.back();
// 将旅行的天数存储在集合中，以便快速查找
unordered_set<int> daysSet(days.begin(), days.end());
// 创建一个大小为lastDay + 1的dp数组
//用于存储从第0天到第lastDay天的最小花费
vector<int> dp(lastDay + 1);
// 遍历每一天
for (int i = 1; i <= lastDay; i ++) {
// 如果这一天不是旅行的日期，则前一天的最小花费就是本天的最小花费
if(!daysSet.contains(i)) {
dp[i] = dp[i - 1];
} else {
dp[i] = min({dp[i - 1] + costs[0],
dp[max(0, i - 7)] + costs[1],
dp[max(0, i - 30)] + costs[2]});
}
}
return dp[lastDay];
}
};
GO代码：
func mincostTickets(days []int, costs []int) int {
lastDay := days[len(days) - 1]
isTravel := make([]bool, lastDay + 1)
for _, day := range days {
isTravel[day] = true
}
dp := make([]int, lastDay + 1)
for i := 1; i <= lastDay; i ++ {
if !isTravel[i] {
dp[i] = dp[i - 1]
} else {
dp[i] = min(dp[i - 1] + costs[0],
dp[max(0, i - 7)] + costs[1],
dp[max(0, i - 30)] + costs[2])
}
}
return dp[lastDay]
}