Medium

题目描述

你已经提前一年规划了火车旅行。你将要旅行的日期用整数数组 days 表示。每一天都是从 1 到 365 的整数。

火车票有三种不同的销售方式：

  • 1 天通行证售价为 costs[0] 美元
  • 7 天通行证售价为 costs[1] 美元
  • 30 天通行证售价为 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 个旅行日 days[i-1]，我们有三种选择：

    • 买1天通行证：dp[i] = dp[i-1] + costs[0]
    • 买7天通行证：找到7天前最早的未覆盖日期
    • 买30天通行证：找到30天前最早的未覆盖日期

  3. 优化思路：对于7天和30天通行证，我们需要找到能覆盖当前日期的最早购买时机。具体来说，如果在第 j 天购买k天通行证，那么它可以覆盖 [j, j+k-1] 这些天。

  4. 实现方法：

    • 方法一：对每个日期，向前查找7天和30天通行证的最优购买点
    • 方法二：使用哈希集合优化日期查找，减少时间复杂度

推荐解法：使用动态规划 + 二分查找的方法，时间复杂度最优。

代码实现

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> dp(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            // 买1天通行证
            dp[i] = dp[i - 1] + costs[0];
            
            // 买7天通行证
            int j = i - 1;
            while (j >= 0 && days[i - 1] - days[j] < 7) {
                j--;
            }
            dp[i] = min(dp[i], dp[j + 1] + costs[1]);
            
            // 买30天通行证
            j = i - 1;
            while (j >= 0 && days[i - 1] - days[j] < 30) {
                j--;
            }
            dp[i] = min(dp[i], dp[j + 1] + costs[2]);
        }
        
        return dp[n];
    }
};

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)
        dp = [0] * (n + 1)
        
        for i in range(1, n + 1):
            # 买1天通行证
            dp[i] = dp[i - 1] + costs[0]
            
            # 买7天通行证
            j = i - 1
            while j >= 0 and days[i - 1] - days[j] < 7:
                j -= 1
            dp[i] = min(dp[i], dp[j + 1] + costs[1])
            
            # 买30天通行证
            j = i - 1
            while j >= 0 and days[i - 1] - days[j] < 30:
                j -= 1
            dp[i] = min(dp[i], dp[j + 1] + costs[2])
        
        return dp[n]

public class Solution {
    public int MincostTickets(int[] days, int[] costs) {
        int n = days.Length;
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            // 买1天通行证
            dp[i] = dp[i - 1] + costs[0];
            
            // 买7天通行证
            int j = i - 1;
            while (j >= 0 && days[i - 1] - days[j] < 7) {
                j--;
            }
            dp[i] = Math.Min(dp[i], dp[j + 1] + costs[1]);
            
            // 买30天通行证
            j = i - 1;
            while (j >= 0 && days[i - 1] - days[j] < 30) {
                j--;
            }
            dp[i] = Math.Min(dp[i], dp[j + 1] + costs[2]);
        }
        
        return dp[n];
    }
}

var mincostTickets = function(days, costs) {
    const n = days.length;
    const dp = new Array(n + 1).fill(0);
    
    for (let i = 1; i <= n; i++) {
        // 买1天通行证
        dp[i] = dp[i - 1] + costs[0];
        
        // 买7天通行证
        let j = i - 1;
        while (j >= 0 && days[i - 1] - days[j] < 7) {
            j--;
        }
        dp[i] = Math.min(dp[i], dp[j + 1] + costs[1]);
        
        // 买30天通行证
        j = i - 1;
        while (j >= 0 && days[i - 1] - days[j] < 30) {
            j--;
        }
        dp[i] = Math.min(dp[i], dp[j + 1] + costs[2]);
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度：对于每个旅行日，最坏情况下需要向前扫描所有之前的日期来找到7天和30天通行证的购买点，因此是 O(n²)
  • 空间复杂度：使用了长度为 n+1 的 dp 数组，因此是 O(n)

相关题目