983. 最低票价

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

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 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] = $2, which covered day 1.

On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.

On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.

In total, you spent $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] = $15 which covered days 1, 2, ..., 30.

On day 31, you bought a 1-day pass for costs[0] = $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] = $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

解题思路

1. 状态定义： 定义 dp[i] 表示第 i 天为止的最低花费。

2. 状态转移方程：

   • 如果第 i 天不是旅行日，则继承前一天的花费： dp[i] = dp[i - 1]
   • 如果第 i 天是旅行日，有三种购买车票方案：
     1. 若购买一日票，价格为 costs[0]，花费为 oneDay = costs[0] + dp[i - 1]。
     2. 若购买七日票，价格为 costs[1]，花费为 sevenDays = costs[1] + dp[max(0, i - 7)]。
     3. 若购买三十日票，价格为 costs[2]，花费为 thirtyDays = costs[2] + dp[max(0, i - 30)]。
   • 选择三种车票方案中的最小值： dp[i] = min(oneDay, sevenDays, thirtyDays)

3. 边界条件：

   • 第 0 天的花费为 0：dp[0] = 0。

4. 最终结果：

   • 返回 dp[lastDay]，即最后一天的最低花费。

复杂度分析

• 时间复杂度：O(lastDay)，因为每一天都需要根据状态转移方程计算。
• 空间复杂度：O(lastDay)，存储动态规划数组 dp。

代码

/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function (days, costs) {
	const travelDay = new Set(days); // 旅行日期集合
	const lastDay = days[days.length - 1]; // 最后一天
	let dp = new Array(lastDay + 1).fill(0); // dp[i] 初始化为 0

	for (let i = 1; i <= lastDay; i++) {
		if (!travelDay.has(i)) {
			dp[i] = dp[i - 1]; // 非旅行日，花费不变
			continue;
		}
		// 计算三种方案的花费
		const oneDay = costs[0] + dp[i - 1];
		const sevenDays = costs[1] + dp[Math.max(0, i - 7)];
		const thirtyDays = costs[2] + dp[Math.max(0, i - 30)];
		dp[i] = Math.min(oneDay, sevenDays, thirtyDays);
	}
	return dp[lastDay];
};

相关题目

题号	标题	题解	标签	难度	力扣
322	零钱兑换	[✓]	广度优先搜索 数组 动态规划	🟠	🀄️ 🔗
2979	最贵的无法购买的商品 🔒		数学 动态规划 数论	🟠	🀄️ 🔗