LeetCode 983.最低票价

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