983 Minimum Cost For Tickets 最低票价

Description:
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.

Train tickets are sold in three different ways:

a 1-day pass is sold for costs[0] dollars,
a 7-day pass is sold for costs[1] dollars, and
a 30-day pass is sold for costs[2] dollars.
The passes allow that many days of consecutive travel.

For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.
Return the minimum number of dollars you need to travel every day in the given list of days.

Example:

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = 7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = 11 and covered all the days of your travel.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = 2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.

Constraints:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

题目描述:
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 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] = 7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = 11，并完成了你计划的每一天旅行。

示例 2：

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

提示:

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

思路:

动态规划
设 dp[i] 表示第 i 天的花费
初始化 dp[0] = 0, 表示第 0 天花费 0 元
将 dp[days[i]] 初始化为 0x3f3f3f3f
if dp[i] == 0, dp[i] = dp[i - 1], 即当天没有出游计划
否则 dp[i] = min(dp[i], dp[i - 1] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2]), 即从前 1/7/30 天中选择一种最便宜的购票方式
时间复杂度为 O(n), 空间复杂度为 O(n)

代码:
C++:

class Solution 
{
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) 
    {
        int n = days.size(), last_day = days.back();
         vector<int> dp(last_day + 1, 0);
         for (int i = 0; i < n; i++) dp[days[i]] = 0x3f3f3f3f;
         for (int i = 1; i <= last_day; i++)
         {
            if (!dp[i]) dp[i] = dp[i - 1];
            else dp[i] = min({dp[i], dp[i - 1] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2]});
         }
         return dp.back();
    }
};

Java:

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length, lastDay = days[n - 1], dp[] = new int[lastDay + 1];
        for (int i = 0; i < n; i++) dp[days[i]] = 0x3f3f3f3f;
        for (int i = 1; i <= lastDay; i++) {
            if (dp[i] == 0) dp[i] = dp[i - 1];
            else dp[i] = Math.min(dp[i], Math.min(dp[i - 1] + costs[0], Math.min(dp[Math.max(0, i - 7)] + costs[1], dp[Math.max(0, i - 30)] + costs[2])));
        }
        return dp[lastDay];
    }
}

Python:

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