【LeetCode】动态规划—983. 最低票价（附完整Python/C++代码）

用户9613193

发布于 2026-06-16 19:00:45

630

动态规划—983. 最低票价

题目描述
前言
基本思路
- 1. 定义
- 2. 理解问题和递推关系
- 3. 解决方法
- 4. 进一步优化
- 5. 小总结
代码实现
- Python代码
- - 代码解释总结
- C++代码
- - 代码解释总结
总结

题目描述

前言

在旅行中，选择最优的票务购买方案是一个常见的问题。给定多个出行日期以及不同票种的费用，我们需要计算出为旅行者提供的最小票务费用。本篇文章将通过动态规划的方法，探讨如何有效解决这个问题。

基本思路

1. 定义

我们需要确定一个动态规划数组 dp，其中 dp[i] 表示在第 i 天的最小票务费用。

2. 理解问题和递推关系

输入：
- days: 旅行的日期数组，包含所有出行日期。
- costs: 不同类型的票的费用，分别为 1 天、7 天和 30 天的票价。
目标：
- 计算出覆盖所有旅行日期的最小费用。

3. 解决方法

状态转移：
- 如果在第 i 天没有出行，则 dp[i] = dp[i-1]。
- 如果在第 i 天出行，则可以选择三种票：
  - 购买 1 天票，费用为 dp[i-1] + costs[0]
  - 购买 7 天票，费用为 dp[max(0, i-7)] + costs[1]
  - 购买 30 天票，费用为 dp[max(0, i-30)] + costs[2]
- 综上，状态转移方程为：
dp[i] = \min(dp[i-1] + costs[0], dp[max(0, i-7)] + costs[1], dp[max(0, i-30)] + costs[2])
边界条件：
- 初始化 dp[0] 为 0，因为在第 0 天没有费用。
最终答案：
- 返回 dp[max_day]，即最后一天的最小费用。

4. 进一步优化

在构建 dp 数组时，实际只需维护最近 30 天的状态，因此可以优化空间复杂度为 O(1)，通过循环更新三个变量来跟踪最新的费用。

5. 小总结

通过动态规划，我们能够有效地计算出覆盖所有旅行日期的最小票务费用。这种方法在时间和空间上的表现都较为优越。

以上就是最低票价问题的基本思路。

代码实现

Python代码

class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        max_day = days[-1]
        dp = [0] * (max_day + 1)
        day_set = set(days)
        
        for i in range(1, max_day + 1):
            if i not in day_set:
                dp[i] = dp[i - 1]
            else:
                dp[i] = min(dp[i - 1] + costs[0],  # 1-day ticket
                             dp[max(0, i - 7)] + costs[1],  # 7-day ticket
                             dp[max(0, i - 30)] + costs[2])  # 30-day ticket
        
        return dp[max_day]  # 返回最后一天的最小费用

代码解释总结

在 Python 代码中，我们维护一个 dp 数组来存储每一天的最小票务费用。通过判断每一天是否出行，我们能决定最小费用并更新状态。最终返回最后一天的费用即可。

C++代码

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int max_day = days.back();
        vector<int> dp(max_day + 1, 0);
        unordered_set<int> day_set(days.begin(), days.end());
        
        for (int i = 1; i <= max_day; ++i) {
            if (day_set.find(i) == day_set.end()) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = std::min(dp[i - 1] + costs[0],  // 1-day ticket
                                 std::min(dp[max(0, i - 7)] + costs[1],  // 7-day ticket
                                          dp[max(0, i - 30)] + costs[2]));  // 30-day ticket
            }
        }
        
        return dp[max_day];  // 返回最后一天的最小费用
    }
};