最开始碰到这道题是在一次刷题练习时看到“最低票价”四个字。题目本身讲的是一个买火车票的场景你计划一年里旅行若干天可以买1日票、7日票、30日票问怎么组合最省钱。看完题面我第一反应是“这不就是个贪心吗”结果试了几组数据才发现完全不是那么回事。这道题我后来反复做了几遍每次都有新体会。它把动态规划里最常见的几个关键点全部串起来了状态怎么定义、转移怎么推导、边界怎么处理、代码怎么写才不会越界。今天就把我从头到尾的完整思路写出来希望能帮到正在啃DP的各位。1. 一道被包装成“买火车票”的动态规划题题目在问什么1.1 题面拆解与三个票种的特殊性先把这个题目的细节说清楚。你有一个days数组里面是一年里的出行日期比如[1, 4, 6, 7, 8, 20]数字范围是1到365表示第几天出门。另外给你三个票价costs[0]是1日票价格costs[1]是7日票价格costs[2]是30日票价格。关键点在于这三个票的“有效期”不是自然周或自然月而是从购买当天开始连续算。1日票只管当天7日票管连续7天包括买票那天30日票管连续30天。也就是说如果你在第5天买了7日票它覆盖的是第5、6、7、8、9、10、11天而不是“这一周的周一至周日”。这个看似简单的设定恰恰是整个题目的灵魂。因为它意味着你无法通过“固定周几”或“固定月初”来做区间划分每一天买票的覆盖范围都和你买票的日期强相关所以必须找到一个能够表达“任意起点”的建模方式。还有个容易忽略的细节你不需要在不出行的日子里买票但买了票的日子即使不出行也算在有效期内“被覆盖了”。也就是说一张7日票可能只覆盖了其中一两个出行日只要综合下来划算你依然可以买。这本质上是一个区间覆盖成本最小化问题只是区间长度只有三种1、7、30。1.2 为什么它天然适合动态规划我先说结论这道题能动态规划是因为它满足两个条件——无后效性和最优子结构。这两个词看起来抽象放到这个场景里其实非常直白。“无后效性”说的是当你决定“第i天之后怎么买票”的时候不需要关心第i天之前你到底买了哪几张票、为什么这么买你只需要知道“到第i天为止最少花了多少钱”这一个数字就够了。之前的选择只会通过这个最小花费影响未来而不会影响未来选择的可行性。“最优子结构”说的是如果“到第365天为止总花费最少”的计划存在那么在这个计划里其中任何一天之前的部分也一定是“到那一天为止”的最优计划。想反证也很简单如果第100天之前有更省钱的买法你把它替换进去后面照旧总花费会更低这就矛盾了。这两个性质一成立动态规划就有了根基。一群天数、三个固定长度的票种、一个明确的成本函数这种“在线决策、成本累积”的结构基本就是为状态机递推量身定做的。1.3 适合什么人读这道题如果你是刚开始学动态规划的读者这道题可以作为“区间覆盖类DP”的入门范本它比“背包问题”更容易找到直观感觉因为“天数”这个状态非常自然。如果你是有一定刷题量的选手这道题值得用来复盘状态定义和边界处理特别是dp[i-7]和dp[i-30]这类索引偏移很多人会在这里绕晕。2. 从贪心到暴力再到动态规划为什么正解只能是DP2.1 贪心策略为什么总差一口气我在开头痛快地说一开始觉得这是贪心后来被打脸了。这里把打脸过程详细说一下因为这也是很多人走过的弯路。一种很自然的贪心是把所有出行日期按顺序排列然后每次发现“前方7天内出行次数多”就买7日票“前方1天内出行”就买单日票。听上去合理但你只要构造一个反例就崩了。假设days [1, 7, 8, 9, 10, 11, 12, 20]票价分别为costs [2, 7, 15]。按“连续出行多就买7日票”的贪心你会发现第7到第13天有6个出行日于是买一张7日票成本7覆盖第7到第13天。第1天和第20天比较远各自买1日票总成本27211。但这其实不是最优解如果第1天买一张7日票覆盖第1到第7天成本7再给第7到第13天的行程买一张7日票成本7总成本就是14反而更贵。所以这个例子里贪心好像赢了。再换一个反例days [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]costs [3, 10, 12]。如果盯着“单个出行日”不买票一旦发现连续7天出行日多就买7日票你会在第1天买7日票覆盖第1~7天成本10第8天买1日票3第9天买1日票3第10天买1日票3总成本19。但更优的方案是直接在第1天买30日票成本12覆盖全部10天。这种“一票到底比拆开买更便宜”的情况贪心极难预料因为你需要在很早的时候就做出一个跨度30天的决策而贪心通常只看眼前几天的密度。贪心的本质问题是它只做局部最优判断却无法回答“要不要为了未来30天提前买一张跨越当前区间的长期票”。这个决策必须全局比较而全局比较恰恰是动态规划的强项。2.2 穷举的复杂度会膨胀到什么程度有人会说那我不贪了我暴力搜索把所有买票方案都枚举一遍总能找到最优吧理论上可以但实际会爆炸。你的出行日期最多有365个每个日子你都有三种选择买1日票、买7日票、买30日票如果完全枚举就是3^365个组合这个数字比宇宙中的原子数量还大得多。当然你可以剪枝比如“已经超过当前最优成本的分支直接砍掉”但在最坏情况下剪枝后的搜索空间依然是指数级的无法在常规时间内运行。那稍微优化一点按“出行日编号”递归呢对于每一个需要处理的出行日你依然面临三种买票选择最多递归300多层最坏复杂度仍是O(3^n)其中n是出行日数量。这个复杂度在数据量小时还能碰碰运气遇到100个出行日就彻底凉了。所以这道题不可能用搜索硬爆必须在决策之间找到共享子结构。所谓“共享子结构”翻译成人话就是你不需要重复计算“第1天到第50天最少花多少钱”这个子问题100次你算一次存下来后面直接查表。这就是动态规划的核心思路。2.3 “无后效性”是这道题的题眼为什么看起来那么像贪心结果却必须上DP就是因为决策之间有后效性。你在第1天买了30日票这个决策不仅影响了第1天的花费还“抹平”了第2到第30天所有日子的购票需求。这种“一个决策影响未来很长一段时间的状态”的特性正是贪心最容易判断失误的地方。无后效性在这里的体现是我们不需要记录“当前还剩多少天票有效”而是把票的有效期直接“折算”进状态中。你怎么才能做到这一点答案是在计算第i天的最优花费时只从那些“已经处理完上一段覆盖区间”的状态转移过来。具体来说如果第i天你选择用一张7日票覆盖那么这张票一定是从某个较早日期的“状态终点”之后开始生效的。我们只需要关心“生效前一天”的状态而不用关心中间这几天你是否买了别的票。中间的出行日全都由这张7日票覆盖不需要单独决策。这样一来一个跨度7天的决策就压缩成了“从dp[i-7]直接跳转过来”后效性被完全消除了。3. 状态定义与前天数的转移逻辑dp[i]到底表示什么3.1 用“前i天的最低花费”作为状态动态规划里状态定义是第一步也是最关键的一步。这道题最自然、最常用的定义是dp[i] 从第1天到第i天包含第i天为止覆盖这些出行日所需的最低总花费这里有个约定俗成的小细节dp[0] 0表示“还没有开始旅行”这是所有递推的起点。dp[365]就是最终答案。为什么要定义成“前i天”而不是“第i天之后”因为票的购买时机是任意的7日票可能在第1天买、也可能在第300天买。如果只盯着单个日子你没法判断“今天买长期票是不是划算”必须把“到这一天为止已经完成的覆盖”累积起来才能做跨区间的比较。“前i天”这个前缀式定义天然支持跨区间跳转。3.2 转移方程的三种来源与索引偏移核心转移方程是这道题的重中之重也是最容易写错的地方。我们先给出最终形态dp[i] min( dp[i-1] costs[0], // 第i天买1日票 dp[max(0, i-7)] costs[1], // 覆盖到第i天的一组7日票 dp[max(0, i-30)] costs[2] // 覆盖到第i天的一组30日票 )注意这里我特意用了dp[max(0, i-7)]而不是dp[i-7]就是为了处理i小于7时的数组越界问题。这个细节很多人会在第一遍写代码时漏掉后面我会专门说。现在解释这三个式子的含义。第一个既然第i天要出行我直接买一张1日票那么之前第1到第i-1天的覆盖成本是dp[i-1]加上今天的票价costs[0]即可。这个最好理解。第二个稍微绕一点。如果我决定“用一张7日票覆盖到第i天”为了不浪费这张票我会让它在第i-6天开始生效因为第i-6天到第i天刚好覆盖7天最后一天恰好是i。这张票生效之前的那一天是第i-7天所以第1到第i-7天的最优覆盖成本是dp[i-7]。再加上这张7日票的价格costs[1]就得到了总成本。这里有一个常见的疑惑为什么不是dp[i-6] costs[1]那是因为dp[i-6]已经包含了第1到第i-6天的覆盖成本如果再加上一张从第i-6天开始的7日票第i-6天就被覆盖了两次等于重复计费了。我们必须从“上一个覆盖区间结束后的下一天”开始计算新票的覆盖范围所以索引要往前再推一天用i-7。第三个式子的逻辑完全相同只是把7换成了3030日票从第i-29天开始生效覆盖到第i天所以它生效前一天的索引是i-30状态从dp[i-30]转移过来。为了更直观我画个简单的数字例子。假设i 20你考虑使用7日票覆盖到第20天那么这张票的生效日应该是第14天覆盖第14~20天。第14天之前的状态是dp[13]也就是dp[i-7] dp[13]。你问第20天的票不是从第14天开始买吗那不应该从dp[13]开始吗对就是从dp[13]也就是dp[i-7]因为i-7 13刚好是生效日前一天。这里的逻辑是一致且自洽的。3.3 不出行日的继承规则还有一个容易忽略的点如果第i天本来就不在days数组里那你完全不需要在第i天做任何买票决策直接令dp[i] dp[i-1]就行。这个“继承”规则看似简单实际上非常重要。因为dp[i]说的是“覆盖到第i天”哪怕第i天不出行前面某张7日票的有效期也可能恰好覆盖到今天。比如你第1天买了一张7日票第8天不出行但第1天那张票并不能覆盖第8天所以第8天的状态应该延续第7天的状态也就是“不新增任何花费也不改变覆盖状态”。这保证了在遇到下一个出行日时你依然能基于“之前所有日子都已得到最优覆盖”这个前提做决策。有些题解会把dp[i]写成“从第1天到第i天中所有出行日的最低花费”不加“覆盖”这个词。这容易让人误以为不出行日不需要处理。实际上即使不出行你也需要把dp[i]推下去因为后续的dp[i1]可能依赖dp[i]。如果你偷懒只更新出行日的状态那遇到连续不出行日时你手头拥有的“前缀成本”就断档了。4. 完整代码实现与边界处理从方程到可运行的解法4.1 Python版本直接用布尔数组标记出行日先用Python写一个最直接、最容易理解的版本。我建议初学者先掌握这个版本然后再去考虑各种优化。def mincostTickets(days, costs): # 题目保证 days 是递增的且值在 1~365 last_day days[-1] # 用一个集合记录所有出行日方便快速判断某天是否需要出行 travel_set set(days) # dp[i] 表示第 1 天到第 i 天的最低覆盖成本 # dp[0] 0表示还没开始 dp [0] * (last_day 1) for i in range(1, last_day 1): if i not in travel_set: # 不出行直接继承前一天状态 dp[i] dp[i - 1] continue # 出行日考虑三种票 # 买 1 日票 cost_1 dp[i - 1] costs[0] # 买 7 日票覆盖到 i 天需要从 i-7 之前的结束状态转移 cost_7 dp[max(0, i - 7)] costs[1] # 买 30 日票同理从 i-30 之前的结束状态转移 cost_30 dp[max(0, i - 30)] costs[2] dp[i] min(cost_1, cost_7, cost_30) return dp[last_day]这个版本的代码有两点值得强调。第一last_day我直接取days[-1]而不是写死365。因为题目给的是“一年”但实际处理到最后一个出行日就够了后面的日子完全不影响结果。这样不仅省事而且让代码更通用——哪怕某天days改成[1]这种极端情况也能正确处理。第二travel_set是set判断i not in travel_set是O(1)操作比每次都在days列表里做线性查找快得多。很多初学者会问为什么dp长度不直接写365如果写365最后返回dp[365]也可以但题目年份固定万一以后改成长度为n的天数写死365的代码就废了。用last_day是更健壮的做法。4.2 C/Java版本与性能对比如果你刷题用的是C或Java思路完全一样只是语法细节不同。C版本如下int mincostTickets(vectorint days, vectorint costs) { int lastDay days.back(); unordered_setint travelSet(days.begin(), days.end()); vectorint dp(lastDay 1, 0); for (int i 1; i lastDay; i) { if (travelSet.find(i) travelSet.end()) { dp[i] dp[i - 1]; continue; } dp[i] min({ dp[i - 1] costs[0], dp[max(0, i - 7)] costs[1], dp[max(0, i - 30)] costs[2] }); } return dp[lastDay]; }Java版本也顺手放一下方便不同语言习惯的读者对照class Solution { public int mincostTickets(int[] days, int[] costs) { int lastDay days[days.length - 1]; SetInteger travelSet new HashSet(); for (int d : days) travelSet.add(d); int[] dp new int[lastDay 1]; for (int i 1; i lastDay; i) { if (!travelSet.contains(i)) { dp[i] dp[i - 1]; } else { int cost1 dp[i - 1] costs[0]; int cost7 dp[Math.max(0, i - 7)] costs[1]; int cost30 dp[Math.max(0, i - 30)] costs[2]; dp[i] Math.min(cost1, Math.min(cost7, cost30)); } } return dp[lastDay]; } }这三种语言的时间复杂度都是O(N)N是你处理的最后一天到第一天的跨度这个跨度最坏是365所以其实是O(365)非常快。空间复杂度也是O(N)主要花在dp数组上。这里有一个很有意思的点因为天数上限是固定的365理论上空间复杂度可以看作是O(1)但大家一般还是按输入规模描述所以写O(N)或O(365)都可以面试时你说明白就行。4.3 常见错误数组越界、初始化和极端用例代码写出来之后我在调试过程中遇到过几个典型的错误这里逐个列出来希望你别再踩。第一个错误没处理i - 7或i - 30小于0的情况。比如i 3时i - 7 -4如果你直接用dp[-4]Python会从数组末尾取数C则是未定义行为轻则答案错乱重则直接段错误。所以务必用max(0, i - 7)和max(0, i - 30)。这里的含义是如果i本身还不到7天那买一张7日票完全可以从第1天开始生效它之前没有需要覆盖的日子对应的前缀状态就是dp[0]。第二个错误dp数组长度写错。如果你把dp长度写成days.length而不是lastDay 1那么在遍历i从1到lastDay时就会越界。这里关键是要理解dp的索引是“绝对天数”不是“出行日序号”。第300天就是数组下标300哪怕days里只有3个元素。这个混淆一开始很容易犯因为大家都习惯数组下标从0开始、长度等于元素个数但DP的dp[i]常常是“状态编号”它不只是原数组的索引。第三个错误忘记初始化dp[0] 0。dp[0]的默认值就是0所以很多语言里不写它也能跑对。但如果你把dp数组初始化为一个很大的数比如INT_MAX然后忘了给dp[0]赋值那所有转移都会失败。建议显式写上dp[0] 0明确表达“还没旅行的状态没有成本”。第四个错误认为“不出行日也必须买票”。有些初学者会先在循环里计算三种票再判断是否出行结果不出行日也被迫取一个min导致花费虚高。记住不出行日只需要继承不需要决策。5. 两种思考方向都会遇到的坑与进阶优化5.1 记忆化搜索 vs 自底向上怎么选除了自底向上填表这道题也可以用记忆化搜索自顶向下来做。核心是一个递归函数dfs(i)表示“从第1天到第i天的最低成本”。from functools import lru_cache def mincostTickets(days, costs): travel_set set(days) last_day days[-1] lru_cache(None) def dfs(day): if day 0: return 0 if day not in travel_set: return dfs(day - 1) return min( dfs(day - 1) costs[0], dfs(day - 7) costs[1], dfs(day - 30) costs[2] ) return dfs(last_day)这里lru_cache会让递归自动记录已经算过的day所以每个day只计算一次时间复杂度同样是O(N)。它的好处是代码更贴近“状态转移方程”的直觉你不用手动创建dp数组也不用担心遍历顺序坏处是递归深度在最坏情况下是365层Python默认递归深度限制是1000所以没问题。但如果你把同样的思路用在“最长公共子序列”那种二维DP上递归深度可能成为瓶颈那时就要小心。我个人建议对于这道题自底向上的迭代版本更稳因为它没有递归栈开销也不依赖语言递归深度限制。但记忆化搜索作为理解工具非常好用尤其是你刚看完转移方程、还没想清楚循环顺序的时候直接用递归先验证逻辑是否正确是一个高效的调试手段。等逻辑验证通了再改成迭代版本也不迟。5.2 当365天里有大量空闲日压缩日期数组的技巧上面的写法已经足够通过绝大多数在线评测因为365天太小了。但我还是想提一种进阶写法因为在一些变体题里天数跨度可能非常大比如days里的值范围能到10的9次方这时就不可能按天数开数组了必须压缩状态。思路是这样的因为出行日的数量最多也只有365个我们其实只关心“出行日”和“紧邻出行日的那几个关键日子”。可以重新定义dp[i]表示“处理完前i个出行日所需的最低成本”然后转移时看“这个7日票或30日票到底覆盖到了未来的哪个出行日”。写出来大致是def mincostTickets_compressed(days, costs): 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]这个压缩版本的时间复杂度是O(n * ?)取决于你如何找j。上面的写法里每个i最多往前扫描n次所以最坏是O(n^2)。但n最大365跑起来也毫无压力。关键是理解dp[i]语义的变化从“按绝对天数”变成“按出行日序列”。这个技巧在你未来处理“天数跨度极大但离散点很少”的同类问题时非常有用。比如有一个变种题把天数改成“一年有10的9次方天”但出行日依然只有不到几百个这时按绝对天数开数组直接内存爆炸而压缩版本却能轻松解决。5.3 和“最长xx子序列”这类DP的显著区别不少读者会把这道题和最长递增子序列LIS之类的DP混在一起因为它们都要遍历数组、都要求一个“最优值”。但在状态定义上有个本质区别LIS的dp[i]通常表示“以第i个元素结尾的最长长度”它关注的是当前元素作为“结尾”的性质而最低票价的dp[i]表示“覆盖到第i天的最低成本”它关注的是“前缀覆盖的完整性”。这个区别带来一个编码上的直接影响LIS在转移时需要从j i的所有位置找一个最大值复杂度是O(n^2)而最低票价因为票种只有固定三种转移时最多只看三个“起点”所以复杂度是O(n)。这也是为什么这道题虽然带着“区间覆盖”的壳却简单很多的原因——决策空间被固定长度的票约束住了不需要枚举所有历史位置。理解这个区别之后你会更容易判断一个题能不能用DP以及大概什么复杂度如果决策能压缩成少数几个“固定跳转”的来源那基本是线性DP如果每个状态需要和前面所有状态比较那很可能是O(n^2)级别需要考虑优化比如单调栈、线段树。6. 从最低票价到同类题动态规划题目的通用破题路径6.1 一道题总结出的DP五步法刷了大量动态规划题之后我逐渐总结出一个固定的解题流程。拿这道题当例子刚好可以完整走一遍。第一步理解题意确认阶段和决策。阶段就是“日子”决策就是“买哪种票/不买票”。第二步设计状态。想你关心的最优解是什么形式用一个变量能不能描述清楚不行就加维度。这里我们用dp[i]表示“第1天到第i天的最低成本”。第三步写转移方程。从“当前决策覆盖了哪些日子”反推“该从哪个更早的状态跳过来”。第四步定边界。dp[0] 0初始化注意越界。第五步定遍历顺序。这里很明显是按天数从小到大正向遍历。这套流程对八成以上的DP题都适用。尤其是第三步很多人卡住是因为“只会顺着想不会反着想”。顺着想很合理我今天买了票明天怎么怎么样。反着想才是DP的精髓我今天的最优解依赖于“哪个更早的状态加一次决策”。一旦你习惯“从状态转移来源倒推”很多看似复杂的DP都能快速拆解。6.2 与股票买卖、打家劫舍的相似之处最低票价、股票买卖、打家劫舍这三类题看起来完全不搭边但它们的状态机结构高度相似。股票买卖里你每天的决策是“买、卖、持有、不操作”于是需要维护“是否持有股票”两个状态打家劫舍里你每家每户的决策是“偷还是不偷”于是需要维护“偷了上一家”和“没偷上一家”两个状态最低票价里你每天的决策是“用哪种票覆盖到这一天”于是用一个“前缀成本”状态贯穿所有天。它们的共同点是当前状态只由有限几个相邻状态推导而来且与更早的历史无关。股票只关心昨天手里有没有股票打家劫舍只关心上家有没有被偷最低票价只关心“7天前/30天前”的成本。这种“局部依赖”性质决定了它们都能用一维或二维DP高效求解。如果你能把这三道题放在一起做对比你会明显感觉到DP的“手感”先画出状态转移的来源和去向代码反而变成了一个体力活。6.3 经验心得先写转移方程再写代码我见过不少人一上来就打开编辑器写代码边写边想逻辑。遇到简单题还行遇到DP基本都会写出一堆if-else最后自己都看不懂。我现在的习惯是先在纸上写清楚转移方程把一个具体例子手工推一遍确认每一步的值都对得上再敲代码。具体到这道题我会拿days [1, 4, 6, 7, 8, 20]、costs [2, 7, 15]手动推一遍dp[1]到dp[20]的值。手推不仅能验证方程对不对还能让你对“7日票是从第几天覆盖到第几天”产生肌肉记忆。推完以后写代码基本就是照着方程翻译几乎不会卡壳。从这道题延伸出去再分享两个我自己反复用的验证技巧如果让你现在立刻手写这道题的题解你可能会发现方程和代码都能默写出来但为什么i-7不是i-6这种细节还是会犹豫。我的做法是拿一个极端例子来验证假设days [7]costs [2, 7, 15]。只出行第7天。最优方案显然是买1日票花2块。用方程验证dp[7] min(dp[6]2, dp[0]7, dp[0]15) min(02, 07, 015) 2成立。如果错误地把7日票写成dp[1]7那dp[1]不是出行日继承0dp[1]77反而不如dp[0]7更符合“从第1天开始覆盖”的语义。这个小例子能帮你快速定位写错的索引偏移。另一个技巧是把所有票价设成1即costs [1, 1, 1]。此时最优方案一定是在有出行的最早期买一张长期票覆盖全部出行日最终答案是1。你随便挑几个days测试如果代码返回1说明转移和边界基本没问题如果返回大于1那一定是某天被重复计费了大概率是索引偏移写错了。这个“极端参数测试法”我后来也用到其他DP题上每次都帮我节省了大量调试时间。最后再说一句个人体会动态规划不怕看不懂怕的是看懂了却不肯动手推例子。最低票价这道题是我觉得最适合“手推入门”的题目之一因为它天数少、票种少、逻辑直白你完全可以在纸上模拟整个过程。花上一个小时把这道题的每个状态、每个转移都亲手推一遍收益比看十篇题解都大。
