最低票价 图解题解

最低票价这道题到底要我们决定什么

给升序的出行日 days 和三种票价 costs（1 天、7 天、30 天通票），每张票从买入当天起连续覆盖若干天，求盖住所有出行日的最低总花费。示例 days=[1,4,6,7,8,20]、costs=[2,7,15]，答案 11：一张 7 天票罩住 1 到 7 号，8 号、20 号再各买一张 1 天票。难点是每个出行日都能挑三种票、长票还跨盖多个出行日。

为什么把每天买什么票都试一遍会算不过来

每个出行日都能挑 1、7、30 天三种票，n 个出行日就有 3ⁿ 种买法，几十个已是天文数字。何况长票跨盖多个出行日，硬枚举里「前面怎么办」被反复重算。既然「办妥前若干个出行日的最低花费」问一次就定死，算一次存起来复用，指数枚举就压成一条线。

状态为什么定成『办妥前 i 个出行日』、还按出行日而不是日历天推

动态规划（DP，办妥前 i 个出行日的最低花费只算一次存 dp[i]、直接复用）在这里把状态定成 dp[i]（i 是出行日个数，不是日历第几天），dp[0]=0 是没出行日、不花钱的地基。盯出行日是因为没出行的日子不用买票，排进表全是白算的空格；答案就是最后一格 dp[n]。

三种票各往回望 1、7、30 天，怎么接上更早那段的 dp

填 dp[i] 只盯第 i 个出行日，记它日期为 today。d 天票含当天共 d 天，覆盖起点是 today-d+1：1 天票只盖当天，7 天票往回盖到 today-7+1，30 天票盖到 today-30+1。这张票罩住 today 往前一截出行日，剩下更早、它够不着的又是一个子问题：管不到的是前 j+1 个出行日（j 是往回退时停在的那个出行日的下标），那段花费就是 dp[j+1]，接上再加票价 c。三种票取最小：dp[i]=min(三种票的 dp[j+1]+c)。往回退 j，就是往前跳过被这张票盖住的出行日、落到第一个没盖住的。

拿 days=[1,4,6,7,8,20] 把这张表一格格填出来

dp[0]=0 打底。1 号：1 天票 dp[0]+2=2 最省，dp[1]=2。4 号：dp[1]+2=4，dp[2]=4。6 号：dp[2]+2=6，dp[3]=6。到 7 号才有看头：1 天票 dp[3]+2=8，可 7 天票从 7 号往回盖到 1 号、把 1、4、6、7 号全罩住，接 dp[0]+7=7 更便宜，dp[4]=7。8 号：dp[4]+2=9，dp[5]=9。20 号离得远，7 天票只盖到 14 号、30 天票加 15 都不划算，1 天票 dp[5]+2=11，dp[6]=11 就是答案。

覆盖起点写成 today-d 少个 +1，整张表为什么会悄悄接错

覆盖起点是 today-d+1；漏掉 +1 写成 today-d 就把覆盖多算一天，往回退 j 时跳掉本该保留的出行日，dp 接错子问题、答案偏小；退 j 的条件 days[j] >= today-d+1 里那个 +1 正是防它。复杂度每个出行日只对 3 种票各退一小段 j，票数是常数，时间 O(n)（大 O 记号，描述规模变大时操作数怎么涨）、空间 O(n)。两处边界也别弄错：只有一个出行日也得把三种票比一遍取最小；密集连续多日要让一张长票和多张短票正面比价。

Python

from typing import List
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        durations = [1, 7, 30]
        n = len(days)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = 10**9
            for d, c in zip(durations, costs):
                j = i - 1
                while j >= 0 and days[j] >= days[i-1] - d + 1:
                    j -= 1
                dp[i] = min(dp[i], dp[j + 1] + c)
        return dp[n]

C++

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dur = {1,7,30};
        int n = days.size();
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; ++i) {
            dp[i] = 1000000000;
            for (int t = 0; t < 3; ++t) {
                int j = i - 1;
                while (j >= 0 && days[j] >= days[i-1] - dur[t] + 1) j--;
                dp[i] = min(dp[i], dp[j + 1] + costs[t]);
            }
        }
        return dp[n];
    }
};

Java

import java.util.*;
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int[] dur = {1, 7, 30};
        int n = days.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = 1_000_000_000;
            for (int t = 0; t < 3; t++) {
                int j = i - 1;
                while (j >= 0 && days[j] >= days[i - 1] - dur[t] + 1) j--;
                dp[i] = Math.min(dp[i], dp[j + 1] + costs[t]);
            }
        }
        return dp[n];
    }
}