最开始碰到这道题，是在一次刷题练习时看到“最低票价”四个字。题目本身讲的是一个买火车票的场景：你计划一年里旅行若干天，可以买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. 从贪心到暴力再到动态规划：为什么正解只能是DP
2.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日票，总成本2+7+2=11。但这其实不是最优解：如果第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换成了30：30日票从第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[i+1]可能依赖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(vector<int>& days, vector<int>& costs) { int lastDay = days.back(); unordered_set<int> travelSet(days.begin(), days.end()); vector<int> 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]; Set<Integer> 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(0+2, 0+7, 0+15) = 2，成立。如果错误地把7日票写成dp[1]+7，那dp[1]不是出行日，继承0，dp[1]+7=7，反而不如dp[0]+7更符合“从第1天开始覆盖”的语义。这个小例子能帮你快速定位写错的索引偏移。
另一个技巧是：把所有票价设成1，即costs = [1, 1, 1]。此时最优方案一定是在有出行的最早期买一张长期票，覆盖全部出行日，最终答案是1。你随便挑几个days测试，如果代码返回1，说明转移和边界基本没问题；如果返回大于1，那一定是某天被重复计费了，大概率是索引偏移写错了。这个“极端参数测试法”我后来也用到其他DP题上，每次都帮我节省了大量调试时间。
最后再说一句个人体会：动态规划不怕看不懂，怕的是看懂了却不肯动手推例子。最低票价这道题是我觉得最适合“手推入门”的题目之一，因为它天数少、票种少、逻辑直白，你完全可以在纸上模拟整个过程。花上一个小时把这道题的每个状态、每个转移都亲手推一遍，收益比看十篇题解都大。
