这道题我是在刷力扣热题100的时候碰到的。题号983难度中等名字叫《最低票价》看起来是个买票算价钱的题目实际上一眼能看出来是动态规划但真正动手写的时候很多人会卡在状态定义上。这篇文章我准备把这道题从暴力递归到记忆化搜索再到两种不同风格的动态规划全部拆开讲一遍顺带把我在提交过程中踩过的边界条件坑也列出来。适合刚学完DP想找综合题目练手的读者也适合已经能AC但想彻底搞懂转移方程为什么这样写的朋友。1. 题面拆解一张票覆盖的不是次数是连续的天数先别急着写代码把题意吃透比什么都重要。题目说你有一次旅行计划days数组里存了你一整年当中要出门坐车的日期costs数组给出三种票的售价1天票、7天票、30天票。票一旦买了就是从买的那天开始连续生效7天票不是让你挑7天坐着玩而是买完当天起连着7天都能坐。1.1 三天票价与一趟旅程的诉求题目给的典型输入长这样days [1, 4, 6, 7, 8, 20] costs [2, 7, 15]三种票单看均价是这样的票种价格有效期平均每天价格1天票21天27天票77天130天票1530天0.5如果只看均价30天票简直便宜到离谱15块钱能用30天平均一天才五毛。但问题在于你并不是每天都出门。days [1, 8]这种情况两张1天票只要4块一张7天票要7块买7天票反而是冤大头。所以均价便宜没有意义能不能把空白的日子跳过去才是关键。1.2 为什么不能直接贪心买最划算的周票我最初做这道题的时候脑子里冒出来的第一个思路是贪心既然7天票均价低那我每次遇到一个出行日就往前看看后面7天里有多少个出行日如果出行日够多就买7天票把这一段全包了否则买1天票。听起来很合理对不对结果一提交直接WA。举一个反例days [1, 4, 6, 7, 8, 20]costs [2, 7, 15]。如果按尽量用7天票覆盖的局部贪心第1天到第8天中间有5个出行日买一张7天票覆盖第1到第7天再给第8天买1天票第20天买1天票总花费是72211。看起来没问题但假如days [1, 2, 3, 4, 5, 30]costs [2, 7, 15]贪心会在第1天买7天票覆盖前5天再给第30天买1天票总花费9。可是最优解是买一张30天票直接15块覆盖全部看起来更贵但如果天数拉长到30天内有很多零散出行日30天票就赢了。贪心只盯着眼前一段无法看到全局这道题天然是动态规划而不是贪心。2. 从DFS暴力到记忆化先写出人话版本动态规划的本质是有记忆的暴力搜索。所以不要一上来就背状态转移公式先想一想如果你自己手动安排买票你会怎么决策。2.1 暴力枚举每一天的三种买法定义一个递归函数dfs(day)含义是从day这一天开始一直到第365天把后面所有要出行的日子都覆盖掉最少还要花多少钱。递归的出口是day 365这时候后面没日子了返回0。如果day这天不需要出行那不用买票直接看下一天dfs(day) dfs(day 1)。如果day这天需要出行你有三个选择买1天票覆盖当天然后从day 1继续规划花费dfs(day 1) costs[0]买7天票覆盖今天到第day 6天然后从day 7继续规划花费dfs(day 7) costs[1]买30天票覆盖今天到第day 29天然后从day 30继续规划花费dfs(day 30) costs[2]然后三者取最小值。这个递归是自顶向下的特别符合人类的直觉今天出门了就决定今天买哪种票剩下的事儿交给明天。2.2 记忆化把已经算过的日子缓存下来直接递归行不行不行因为会有大量重复计算。比如dfs(10)可能被dfs(9)、dfs(8)、dfs(1)多次调用而且每次都会重新展开整棵递归树复杂度指数爆炸。解决办法很简单开一个长度为366的数组memomemo[day]存已经算出来的dfs(day)下次再遇到直接返回。class Solution { public: int mincostTickets(vectorint days, vectorint costs) { bool travel[366] {false}; for (int d : days) travel[d] true; vectorint memo(366, -1); functionint(int) dfs [](int day) - int { if (day 365) return 0; if (memo[day] ! -1) return memo[day]; if (!travel[day]) { memo[day] dfs(day 1); } else { int a dfs(day 1) costs[0]; int b dfs(day 7) costs[1]; int c dfs(day 30) costs[2]; memo[day] min(a, min(b, c)); } return memo[day]; }; return dfs(1); } };这里我强烈建议把memo初始化成-1而不是0。因为某些合法状态的结果理论上也可能是0比如从第366天开始的后半段就是0用-1做未计算标记是最稳妥的。记忆化之后每一天最多计算一次每次只做三次选择和一次取最小值复杂度变成O(365)因为一年只有365天。自顶向下的写法优点是容易理解缺点是递归有栈开销。在力扣上能过但面试官大概率会让你改成自底向上的迭代DP也就是下一章的主角。3. 顺推动态规划365天逐天铺过去自底向上的DP是另一种思维角度我不从某一天往后看而是从前往后把每一天都算出来用前面的结果推后面的结果。3.1 dp[i]的状态定义与转移方程定义dp[i]表示第1天到第i天这个区间内所有需要出行的日子全部被覆盖所需的最低花费。现在站在第i天的位置思考如果第i天不需要出行那今天的成本和昨天一模一样dp[i] dp[i - 1]因为不用为今天额外花一分钱。如果第i天必须出行那么最后一次买票的行为有三种可能最后一张票是1天票这张票只覆盖今天那第i - 1天之前的日子已经被覆盖好了总花费是dp[i - 1] costs[0]最后一张票是7天票这张票从i - 6覆盖到i那在i - 7之前的日子必须在买这张票之前就已经覆盖好总花费是dp[i - 7] costs[1]最后一张票是30天票这张票从i - 29覆盖到i那在i - 30之前的日子必须在买这张票之前就已经覆盖好总花费是dp[i - 30] costs[2]这里经常有人绕不明白为什么用7天票的时候是dp[i - 7]而不是dp[i - 6]因为7天票覆盖的是连续的7天如果今天第i天是这7天的最后一天那么这7天的起点是i - 6也就是说从第1天到第i - 7天和第i - 6到第i天之间是没有重叠的买这张7天票之前前i - 7天必须已经全部覆盖完成。对应dp[i - 7]含义正好是前i - 7天全部覆盖好的最小花费。同理30天票就是dp[i - 30]。当i - 7或者i - 30小于0的时候就说明这张票覆盖的范围超出了第1天前面没有日子需要处理了对应的dp值取0。所以写代码的时候会用max(0, i - 7)。转移方程写成这样dp[i] dp[i - 1] if 第i天不旅行 dp[i] min( dp[max(0, i - 1)] costs[0], dp[max(0, i - 7)] costs[1], dp[max(0, i - 30)] costs[2] ) if 第i天必须旅行实际上第i天旅行时也可以用dp[i - 1]因为i - 1 0。3.2 完整可运行代码C/Python我平时刷题一般用C但出租屋里带的学生也有用Python的所以两个版本的代码都放出来。C版本class Solution { public: int mincostTickets(vectorint days, vectorint costs) { bool travel[366] {false}; for (int d : days) travel[d] true; vectorint dp(366, 0); for (int i 1; i 365; i) { if (!travel[i]) { dp[i] dp[i - 1]; } else { int a dp[i - 1] costs[0]; int b dp[max(0, i - 7)] costs[1]; int c dp[max(0, i - 30)] costs[2]; dp[i] min(a, min(b, c)); } } return dp[365]; } };Python版本class Solution: def mincostTickets(self, days: List[int], costs: List[int]) - int: travel set(days) dp [0] * 366 for i in range(1, 366): if i not in travel: dp[i] dp[i - 1] else: dp[i] min( dp[i - 1] costs[0], dp[max(0, i - 7)] costs[1], dp[max(0, i - 30)] costs[2] ) return dp[365]这版代码在力扣上可以直接通过时间和空间复杂度都是O(365)也就是O(1)级别的常数。这也是这道题最主流、最稳的写法。注意最后返回的是dp[365]不是dp[days.back()]因为dp[365]已经把整年所有旅行日都考虑进去了中间空白的日子不会增加额外费用。4. 踩坑盘点边界条件与性能细节这道题AC的代码看起来很短但我实际做的时候在三个地方栽过跟头写出来给各位提个醒。4.1 i-7和i-30越界时的处理最容易崩的地方就是dp[i - 7]和dp[i - 30]的下标问题。当i小于7或者小于30的时候i - 7、i - 30是负数直接访问数组肯定越界。我见过好几个人在这里用if (i 7) ... else ...单独处理其实完全没必要一行max(0, i - 7)就解决了。有个细节是max(0, i - 7)和dp[0]的语义要能对应上。i 7时i - 7 0dp[0]表示第1天之前没有任何日子需要覆盖这是合法的。所以一定要保证dp[0]初始化为0它就是个哨兵代表空区间。4.2 用bool数组判定出行日比哈希集合更稳我看到不少题解喜欢把days转成unordered_setint然后每次判断travel.count(i)。C里unordered_set虽然理论上是O(1)查询但哈希函数是有开销的而且力扣的测试数据里days最长也就365个元素。在这种数据规模下直接用bool travel[366]数组才是最优解内存连续、访问极快代码也更简洁。bool travel[366] {false}; for (int d : days) travel[d] true;有同学可能会问那Python为什么用set因为Python里没有天然的bool数组访问习惯而且list判断i in travel是O(n)肯定不行所以用set是Python里的正确姿势。语言特性不同选型自然不同。4.3 三个costs大小反直觉时的转移顺序题目没说costs[0] costs[1] costs[2]也就是说可能出现30天票比1天票还便宜的情况。比如costs [10, 1, 1]这时候7天票和30天票都只要1块钱傻子都知道买30天票。我在第一次做的时候写过一个优化既然7天票均价低我就只在i 7时才考虑7天票分支i 30时才考虑30天票分支其余时候只买1天票。这个优化本身没错但是在i 7时万一7天票更便宜比如costs[1] 1costs[0] 100只买1天票就亏大了。所以在写转移时三个分支必须无条件都算一遍不能因为现在没到7天就跳过7天票分支因为dp[max(0, i - 7)] costs[1]在i 7时自带覆盖从第1天到现在所有日子的语义是一种合法的提前囤票行为。4.4 记忆化DFS中的memo初始值前面提到过memo数组建议初始化为-1不要初始化为0。虽然这道题的最优花费不可能是0但为了养成好习惯还是用-1做未访问标记。这不算什么大坑但真有人因为初始化为0在别的DP题里死活调不出来最后发现是某些合法状态返回了0导致缓存命中错误。5. 进阶优化把O(365)压到O(N)的离散化DP很多DP题的进阶方向就是压缩状态。这道题虽然一年只有365天开固定数组没问题但如果面试官把题目改一改比如days里的日期范围可以到10^9days数组长度是10^5那开一个长度为10^9的数组就完全不可行了这时候需要用到离散化DP。5.1 为什么有的场景不能开365数组原题限定了一年只有365天所以dp[366]能兜住。但实际工程或者面试扩展题里一年这个概念完全可以换成一条时间轴天数的上限可能是任意一个很大的整数。这时候如果还按天数开数组空间直接爆炸。正确的思路是只处理真正需要出行的日子中间的空白天根本不需要铺开。5.2 离散化DP的转移思路与代码换个状态定义dp[i]表示前i个旅行日也就是days[0]到days[i-1]全部被覆盖的最低花费。dp[0] 0表示一个旅行日都没有的时候花费为0。对于第i个旅行日days[i-1]三种买法分别对应买1天票只覆盖当天那需要前i-1个旅行日已经覆盖好dp[i-1] costs[0]买7天票覆盖days[i-1] - 6到days[i-1]那么往前找到第一个不在区间内的旅行日。假设下标j对应的days[j]已经小于days[i-1] - 6说明days[j]在7天窗口之外前j1个旅行日下标0到j需要在买票前覆盖好花费是dp[j1] costs[1]买30天票同理找days[j] days[i-1] - 29的位置dp[j1] costs[2]核心代码class Solution { public: int mincostTickets(vectorint days, vectorint costs) { int n days.size(); vectorint dp(n 1, INT_MAX / 2); dp[0] 0; for (int i 1; i n; i) { // 1天票 dp[i] min(dp[i], dp[i - 1] costs[0]); // 7天票找到第一个不在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天票找到第一个不在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]; } };这个写法在最坏情况下比如30天票一直覆盖不到前面的旅行日while循环每趟可能都要扫很多复杂度最坏O(n^2)。但因为days数组是严格递增的可以用两个指针分别维护7天窗口和30天窗口的左边界让整体降到O(n)。我用双指针优化后的写法class Solution { public: int mincostTickets(vectorint days, vectorint costs) { int n days.size(); vectorint dp(n 1, INT_MAX / 2); dp[0] 0; int j7 0, j30 0; for (int i 1; i n; i) { while (days[i - 1] - days[j7] 7) j7; while (days[i - 1] - days[j30] 30) j30; dp[i] min({dp[i - 1] costs[0], dp[j7] costs[1], dp[j30] costs[2]}); } return dp[n]; } };注意这里j7的含义有点微妙它指向第一个仍然在7天窗口内的旅行日下标。也就是说days[j7] days[i-1] - 6所以dp[j7]表示前j7个旅行日都已经覆盖好第j7个旅行日下标j7-1恰好是7天窗口外的最后一个。购买7天票后从j7到i-1这些旅行日全部被覆盖。复杂度O(n)空间O(n)比固定365的写法更通用。6. 从这题延伸出去动态规划的通用套路一道题的价值不在于AC而在于它让你掌握了哪一类问题的解法。《最低票价》属于非常典型的序列覆盖型DP和力扣上的跳跃游戏、视频拼接、粉刷房子本质上是同一套思维。6.1 序列覆盖问题的三步法我总结了一套三步走的思路遇到类似题直接套第一步定义前i个元素处理完的状态也就是想清楚dp[i]到底代表什么。在本题里是前i天全部覆盖花费在跳跃游戏里可能是跳到第i个位置的最少步数。第二步枚举最后一次操作。7天票覆盖7天、30天票覆盖30天本质上是跳7格和跳30格。枚举最后一张票买的是什么就能从之前某个确定的已处理状态转移过来。第三步取min或max。这道题取最小花费所以是min(dp[i-1] costs[0], dp[i-7] costs[1], dp[i-30] costs[2])。这套路对区间覆盖跳跃次数股票买卖打家劫舍都适用区别只在于状态的维度和转移的跨度。6.2 面试时如何讲清这道题如果面试官让你现场做这道题不建议一上来就闷头写递推。我的建议是分三步表达先把暴力递归版本讲出来让面试官知道你的思维是清晰的今天是出行日我就试三种票然后递归处理后面的天。接着指出重复计算问题自然而然地引入记忆化搜索。最后再说我可以把自顶向下的记忆化改成自底向上的DP然后噼里啪啦写出三行转移方程。如果时间够再补一句这题还能离散化处理更大的天数范围这一下就能体现你对DP的理解不只是背模板。面试官真正想看的是你能不能把一个复杂问题拆成状态定义 状态转移 边界条件这三件套而不是记住某个题的代码。力扣上的热门题经常在面试里被翻来覆去地问最低票价就是一道非常适合用来展示从暴力到DP思维过程的题目。我把这道题刷完之后最大的体会是不要怕一开始写出时间复杂度很高的暴力版本重要的是你能意识到哪里重复了、哪里可以缓存、怎么从人话翻译成状态转移方程。这种能力一旦建立起来再遇到没见过的新题也不会慌。 
长河君 · 2026/9/9 9:30:19 · 阅读 1.2k 最低票价动态规划详解：从记忆化搜索到状态转移的完整拆解
这道题我是在刷力扣热题100的时候碰到的。题号983难度中等名字叫《最低票价》看起来是个买票算价钱的题目实际上一眼能看出来是动态规划但真正动手写的时候很多人会卡在状态定义上。这篇文章我准备把这道题从暴力递归到记忆化搜索再到两种不同风格的动态规划全部拆开讲一遍顺带把我在提交过程中踩过的边界条件坑也列出来。适合刚学完DP想找综合题目练手的读者也适合已经能AC但想彻底搞懂转移方程为什么这样写的朋友。1. 题面拆解一张票覆盖的不是次数是连续的天数先别急着写代码把题意吃透比什么都重要。题目说你有一次旅行计划days数组里存了你一整年当中要出门坐车的日期costs数组给出三种票的售价1天票、7天票、30天票。票一旦买了就是从买的那天开始连续生效7天票不是让你挑7天坐着玩而是买完当天起连着7天都能坐。1.1 三天票价与一趟旅程的诉求题目给的典型输入长这样days [1, 4, 6, 7, 8, 20] costs [2, 7, 15]三种票单看均价是这样的票种价格有效期平均每天价格1天票21天27天票77天130天票1530天0.5如果只看均价30天票简直便宜到离谱15块钱能用30天平均一天才五毛。但问题在于你并不是每天都出门。days [1, 8]这种情况两张1天票只要4块一张7天票要7块买7天票反而是冤大头。所以均价便宜没有意义能不能把空白的日子跳过去才是关键。1.2 为什么不能直接贪心买最划算的周票我最初做这道题的时候脑子里冒出来的第一个思路是贪心既然7天票均价低那我每次遇到一个出行日就往前看看后面7天里有多少个出行日如果出行日够多就买7天票把这一段全包了否则买1天票。听起来很合理对不对结果一提交直接WA。举一个反例days [1, 4, 6, 7, 8, 20]costs [2, 7, 15]。如果按尽量用7天票覆盖的局部贪心第1天到第8天中间有5个出行日买一张7天票覆盖第1到第7天再给第8天买1天票第20天买1天票总花费是72211。看起来没问题但假如days [1, 2, 3, 4, 5, 30]costs [2, 7, 15]贪心会在第1天买7天票覆盖前5天再给第30天买1天票总花费9。可是最优解是买一张30天票直接15块覆盖全部看起来更贵但如果天数拉长到30天内有很多零散出行日30天票就赢了。贪心只盯着眼前一段无法看到全局这道题天然是动态规划而不是贪心。2. 从DFS暴力到记忆化先写出人话版本动态规划的本质是有记忆的暴力搜索。所以不要一上来就背状态转移公式先想一想如果你自己手动安排买票你会怎么决策。2.1 暴力枚举每一天的三种买法定义一个递归函数dfs(day)含义是从day这一天开始一直到第365天把后面所有要出行的日子都覆盖掉最少还要花多少钱。递归的出口是day 365这时候后面没日子了返回0。如果day这天不需要出行那不用买票直接看下一天dfs(day) dfs(day 1)。如果day这天需要出行你有三个选择买1天票覆盖当天然后从day 1继续规划花费dfs(day 1) costs[0]买7天票覆盖今天到第day 6天然后从day 7继续规划花费dfs(day 7) costs[1]买30天票覆盖今天到第day 29天然后从day 30继续规划花费dfs(day 30) costs[2]然后三者取最小值。这个递归是自顶向下的特别符合人类的直觉今天出门了就决定今天买哪种票剩下的事儿交给明天。2.2 记忆化把已经算过的日子缓存下来直接递归行不行不行因为会有大量重复计算。比如dfs(10)可能被dfs(9)、dfs(8)、dfs(1)多次调用而且每次都会重新展开整棵递归树复杂度指数爆炸。解决办法很简单开一个长度为366的数组memomemo[day]存已经算出来的dfs(day)下次再遇到直接返回。class Solution { public: int mincostTickets(vectorint days, vectorint costs) { bool travel[366] {false}; for (int d : days) travel[d] true; vectorint memo(366, -1); functionint(int) dfs [](int day) - int { if (day 365) return 0; if (memo[day] ! -1) return memo[day]; if (!travel[day]) { memo[day] dfs(day 1); } else { int a dfs(day 1) costs[0]; int b dfs(day 7) costs[1]; int c dfs(day 30) costs[2]; memo[day] min(a, min(b, c)); } return memo[day]; }; return dfs(1); } };这里我强烈建议把memo初始化成-1而不是0。因为某些合法状态的结果理论上也可能是0比如从第366天开始的后半段就是0用-1做未计算标记是最稳妥的。记忆化之后每一天最多计算一次每次只做三次选择和一次取最小值复杂度变成O(365)因为一年只有365天。自顶向下的写法优点是容易理解缺点是递归有栈开销。在力扣上能过但面试官大概率会让你改成自底向上的迭代DP也就是下一章的主角。3. 顺推动态规划365天逐天铺过去自底向上的DP是另一种思维角度我不从某一天往后看而是从前往后把每一天都算出来用前面的结果推后面的结果。3.1 dp[i]的状态定义与转移方程定义dp[i]表示第1天到第i天这个区间内所有需要出行的日子全部被覆盖所需的最低花费。现在站在第i天的位置思考如果第i天不需要出行那今天的成本和昨天一模一样dp[i] dp[i - 1]因为不用为今天额外花一分钱。如果第i天必须出行那么最后一次买票的行为有三种可能最后一张票是1天票这张票只覆盖今天那第i - 1天之前的日子已经被覆盖好了总花费是dp[i - 1] costs[0]最后一张票是7天票这张票从i - 6覆盖到i那在i - 7之前的日子必须在买这张票之前就已经覆盖好总花费是dp[i - 7] costs[1]最后一张票是30天票这张票从i - 29覆盖到i那在i - 30之前的日子必须在买这张票之前就已经覆盖好总花费是dp[i - 30] costs[2]这里经常有人绕不明白为什么用7天票的时候是dp[i - 7]而不是dp[i - 6]因为7天票覆盖的是连续的7天如果今天第i天是这7天的最后一天那么这7天的起点是i - 6也就是说从第1天到第i - 7天和第i - 6到第i天之间是没有重叠的买这张7天票之前前i - 7天必须已经全部覆盖完成。对应dp[i - 7]含义正好是前i - 7天全部覆盖好的最小花费。同理30天票就是dp[i - 30]。当i - 7或者i - 30小于0的时候就说明这张票覆盖的范围超出了第1天前面没有日子需要处理了对应的dp值取0。所以写代码的时候会用max(0, i - 7)。转移方程写成这样dp[i] dp[i - 1] if 第i天不旅行 dp[i] min( dp[max(0, i - 1)] costs[0], dp[max(0, i - 7)] costs[1], dp[max(0, i - 30)] costs[2] ) if 第i天必须旅行实际上第i天旅行时也可以用dp[i - 1]因为i - 1 0。3.2 完整可运行代码C/Python我平时刷题一般用C但出租屋里带的学生也有用Python的所以两个版本的代码都放出来。C版本class Solution { public: int mincostTickets(vectorint days, vectorint costs) { bool travel[366] {false}; for (int d : days) travel[d] true; vectorint dp(366, 0); for (int i 1; i 365; i) { if (!travel[i]) { dp[i] dp[i - 1]; } else { int a dp[i - 1] costs[0]; int b dp[max(0, i - 7)] costs[1]; int c dp[max(0, i - 30)] costs[2]; dp[i] min(a, min(b, c)); } } return dp[365]; } };Python版本class Solution: def mincostTickets(self, days: List[int], costs: List[int]) - int: travel set(days) dp [0] * 366 for i in range(1, 366): if i not in travel: dp[i] dp[i - 1] else: dp[i] min( dp[i - 1] costs[0], dp[max(0, i - 7)] costs[1], dp[max(0, i - 30)] costs[2] ) return dp[365]这版代码在力扣上可以直接通过时间和空间复杂度都是O(365)也就是O(1)级别的常数。这也是这道题最主流、最稳的写法。注意最后返回的是dp[365]不是dp[days.back()]因为dp[365]已经把整年所有旅行日都考虑进去了中间空白的日子不会增加额外费用。4. 踩坑盘点边界条件与性能细节这道题AC的代码看起来很短但我实际做的时候在三个地方栽过跟头写出来给各位提个醒。4.1 i-7和i-30越界时的处理最容易崩的地方就是dp[i - 7]和dp[i - 30]的下标问题。当i小于7或者小于30的时候i - 7、i - 30是负数直接访问数组肯定越界。我见过好几个人在这里用if (i 7) ... else ...单独处理其实完全没必要一行max(0, i - 7)就解决了。有个细节是max(0, i - 7)和dp[0]的语义要能对应上。i 7时i - 7 0dp[0]表示第1天之前没有任何日子需要覆盖这是合法的。所以一定要保证dp[0]初始化为0它就是个哨兵代表空区间。4.2 用bool数组判定出行日比哈希集合更稳我看到不少题解喜欢把days转成unordered_setint然后每次判断travel.count(i)。C里unordered_set虽然理论上是O(1)查询但哈希函数是有开销的而且力扣的测试数据里days最长也就365个元素。在这种数据规模下直接用bool travel[366]数组才是最优解内存连续、访问极快代码也更简洁。bool travel[366] {false}; for (int d : days) travel[d] true;有同学可能会问那Python为什么用set因为Python里没有天然的bool数组访问习惯而且list判断i in travel是O(n)肯定不行所以用set是Python里的正确姿势。语言特性不同选型自然不同。4.3 三个costs大小反直觉时的转移顺序题目没说costs[0] costs[1] costs[2]也就是说可能出现30天票比1天票还便宜的情况。比如costs [10, 1, 1]这时候7天票和30天票都只要1块钱傻子都知道买30天票。我在第一次做的时候写过一个优化既然7天票均价低我就只在i 7时才考虑7天票分支i 30时才考虑30天票分支其余时候只买1天票。这个优化本身没错但是在i 7时万一7天票更便宜比如costs[1] 1costs[0] 100只买1天票就亏大了。所以在写转移时三个分支必须无条件都算一遍不能因为现在没到7天就跳过7天票分支因为dp[max(0, i - 7)] costs[1]在i 7时自带覆盖从第1天到现在所有日子的语义是一种合法的提前囤票行为。4.4 记忆化DFS中的memo初始值前面提到过memo数组建议初始化为-1不要初始化为0。虽然这道题的最优花费不可能是0但为了养成好习惯还是用-1做未访问标记。这不算什么大坑但真有人因为初始化为0在别的DP题里死活调不出来最后发现是某些合法状态返回了0导致缓存命中错误。5. 进阶优化把O(365)压到O(N)的离散化DP很多DP题的进阶方向就是压缩状态。这道题虽然一年只有365天开固定数组没问题但如果面试官把题目改一改比如days里的日期范围可以到10^9days数组长度是10^5那开一个长度为10^9的数组就完全不可行了这时候需要用到离散化DP。5.1 为什么有的场景不能开365数组原题限定了一年只有365天所以dp[366]能兜住。但实际工程或者面试扩展题里一年这个概念完全可以换成一条时间轴天数的上限可能是任意一个很大的整数。这时候如果还按天数开数组空间直接爆炸。正确的思路是只处理真正需要出行的日子中间的空白天根本不需要铺开。5.2 离散化DP的转移思路与代码换个状态定义dp[i]表示前i个旅行日也就是days[0]到days[i-1]全部被覆盖的最低花费。dp[0] 0表示一个旅行日都没有的时候花费为0。对于第i个旅行日days[i-1]三种买法分别对应买1天票只覆盖当天那需要前i-1个旅行日已经覆盖好dp[i-1] costs[0]买7天票覆盖days[i-1] - 6到days[i-1]那么往前找到第一个不在区间内的旅行日。假设下标j对应的days[j]已经小于days[i-1] - 6说明days[j]在7天窗口之外前j1个旅行日下标0到j需要在买票前覆盖好花费是dp[j1] costs[1]买30天票同理找days[j] days[i-1] - 29的位置dp[j1] costs[2]核心代码class Solution { public: int mincostTickets(vectorint days, vectorint costs) { int n days.size(); vectorint dp(n 1, INT_MAX / 2); dp[0] 0; for (int i 1; i n; i) { // 1天票 dp[i] min(dp[i], dp[i - 1] costs[0]); // 7天票找到第一个不在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天票找到第一个不在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]; } };这个写法在最坏情况下比如30天票一直覆盖不到前面的旅行日while循环每趟可能都要扫很多复杂度最坏O(n^2)。但因为days数组是严格递增的可以用两个指针分别维护7天窗口和30天窗口的左边界让整体降到O(n)。我用双指针优化后的写法class Solution { public: int mincostTickets(vectorint days, vectorint costs) { int n days.size(); vectorint dp(n 1, INT_MAX / 2); dp[0] 0; int j7 0, j30 0; for (int i 1; i n; i) { while (days[i - 1] - days[j7] 7) j7; while (days[i - 1] - days[j30] 30) j30; dp[i] min({dp[i - 1] costs[0], dp[j7] costs[1], dp[j30] costs[2]}); } return dp[n]; } };注意这里j7的含义有点微妙它指向第一个仍然在7天窗口内的旅行日下标。也就是说days[j7] days[i-1] - 6所以dp[j7]表示前j7个旅行日都已经覆盖好第j7个旅行日下标j7-1恰好是7天窗口外的最后一个。购买7天票后从j7到i-1这些旅行日全部被覆盖。复杂度O(n)空间O(n)比固定365的写法更通用。6. 从这题延伸出去动态规划的通用套路一道题的价值不在于AC而在于它让你掌握了哪一类问题的解法。《最低票价》属于非常典型的序列覆盖型DP和力扣上的跳跃游戏、视频拼接、粉刷房子本质上是同一套思维。6.1 序列覆盖问题的三步法我总结了一套三步走的思路遇到类似题直接套第一步定义前i个元素处理完的状态也就是想清楚dp[i]到底代表什么。在本题里是前i天全部覆盖花费在跳跃游戏里可能是跳到第i个位置的最少步数。第二步枚举最后一次操作。7天票覆盖7天、30天票覆盖30天本质上是跳7格和跳30格。枚举最后一张票买的是什么就能从之前某个确定的已处理状态转移过来。第三步取min或max。这道题取最小花费所以是min(dp[i-1] costs[0], dp[i-7] costs[1], dp[i-30] costs[2])。这套路对区间覆盖跳跃次数股票买卖打家劫舍都适用区别只在于状态的维度和转移的跨度。6.2 面试时如何讲清这道题如果面试官让你现场做这道题不建议一上来就闷头写递推。我的建议是分三步表达先把暴力递归版本讲出来让面试官知道你的思维是清晰的今天是出行日我就试三种票然后递归处理后面的天。接着指出重复计算问题自然而然地引入记忆化搜索。最后再说我可以把自顶向下的记忆化改成自底向上的DP然后噼里啪啦写出三行转移方程。如果时间够再补一句这题还能离散化处理更大的天数范围这一下就能体现你对DP的理解不只是背模板。面试官真正想看的是你能不能把一个复杂问题拆成状态定义 状态转移 边界条件这三件套而不是记住某个题的代码。力扣上的热门题经常在面试里被翻来覆去地问最低票价就是一道非常适合用来展示从暴力到DP思维过程的题目。我把这道题刷完之后最大的体会是不要怕一开始写出时间复杂度很高的暴力版本重要的是你能意识到哪里重复了、哪里可以缓存、怎么从人话翻译成状态转移方程。这种能力一旦建立起来再遇到没见过的新题也不会慌。