先交代一下背景：今天是我hot100打卡的第12天，前11天按专题推进，链表、哈希表、双指针、滑动窗口、二叉树这些常规板块基本都过了一遍，从第10天开始进入动态规划专题。hot100动态规划这部分题量不小，而且属于那种“一看题解全懂，一关题解就懵”的类型，卡壳太正常了。这篇就把我day12刷的三道题完整复盘一下，题目分别是打家劫舍、最长递增子序列、零钱兑换。三题刚好覆盖了一维DP的三种经典范式：简单递推、以i结尾的LIS型、完全背包型。如果你也正在刷hot100，或者准备系统过一遍动态规划，这篇文章应该能帮你省不少弯路。

1. 三道DP题的整体落位与选题逻辑

先说为什么day12选这三道。hot100里的动态规划题目大概有十几道，真正适合作为入门序列的，必须是状态定义清晰、转移方程不绕、而且能延伸到后续难题的题目。打家劫舍是“相邻限制”的经典模型，最长递增子序列是“以i结尾”这个高频套路的代表，零钱兑换则引入了“遍历顺序”这个隐藏考点，做完这三道，再去做最大子数组和、编辑距离、最长公共子序列会顺很多。

从打卡规划的角度，我习惯把hot100按专题拆分，而不是按题号顺序刷。原因很简单：hot100题号打乱之后并没有难度递进关系，今天做一道简单题明天直接上困难题，挫败感特别强。按专题集中突破，一周内同一个套路反复见三次以上，肌肉记忆就建立了。day10到day14我都在动态规划板块，day12正好是节奏中段，难度适当上调，从“会做”过渡到“讲得清为什么”。

三道题里，打家劫舍我是第一遍做，最长递增子序列以前面试的时候见过，但当时用的是贪心加二分，没有真正写过O(n²)的DP版本，零钱兑换则是之前踩过坑、这次重新梳理了一遍遍历顺序。这个组合有一个好处：既有新题，也有旧题重做，旧题重做时重点不是“能不能AC”，而是能不能把转移方程的推导过程讲清楚。建议你也用这个思路安排刷题节奏——不要只刷新题，隔几天把做过的旧题重新用文字复盘一遍，效果比多刷三道新题要好。

三题的难度定位也值得说一下。打家劫舍属于动态规划入门第一梯队，和爬楼梯、斐波那契并列，10分钟能拿下属于正常水平；最长递增子序列的O(n²)解法不难，但很多人会纠结“dp[i]表示前i个还是以i结尾”，这一步想清楚后面都好说；零钱兑换是三道里面最需要小心的一题，因为初始化用无穷大、遍历顺序影响结果，出错往往不是逻辑问题而是细节问题。三题做完，动态规划的“三板斧”——状态定义、转移方程、边界初始化——基本就都见过了。

2. 打家劫舍：相邻限制型DP的入门标尺

2.1 题目回顾与状态定义的核心逻辑

题目不复杂：一排房子，每间有现金nums[i]，不能偷相邻两家，问最多能偷多少。第一次做这道题，最容易掉进去的思路是从大到小贪心，先偷最多的一家然后跳过邻居，但这种情况在[2, 1, 1, 2]这种用例上会直接翻车，因为贪心只看局部最优，看不到“隔一家偷一家”的全局最优组合。

正确姿势是定义dp[i]表示“从前i间房子中能偷到的最大金额”，这里的关键是搞清楚“前i间”到底从哪里算起。我习惯用“前i间，下标0到i-1”这套约定，好处是dp[0]可以表示空房子，dp[1]表示只考虑第一间，代码里不用做下标的二次偏移。

转移方程是dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。解释起来也不绕：到了第i间房子，你只有两个选择，不偷这一间，那就延续前i-1间的结果dp[i-1]；偷这一间，那就必须跳过第i-1间，收益是前i-2间的最优结果加上当前房子的金额。两个方向取最大值，就是当前状态的最优解。

有一个细节容易忽略：为什么不偷当前房子时，直接沿用dp[i-1]就够，不需要再比较dp[i-2]？因为dp[i-1]本身已经包含了“第i-1间偷还是不偷”的最优决策，它是一个已经归约好的最优子结构，不需要在这个层面继续展开。这就是动态规划“用子问题答案拼父问题答案”的精髓，理解了这一点，后面做打家劫舍III的树形DP才不会懵。

2.2 两种实现方案与一维滚动优化

打家劫舍最直观的写法是开一个长度为n+1的dp数组：

def rob(nums): n = len(nums) if n == 0: return 0 dp = [0] * (n + 1) dp[1] = nums[0] for i in range(2, n + 1): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) return dp[n]

这个版本好理解，但空间上是O(n)。仔细观察转移方程发现，dp[i]只依赖dp[i-1]和dp[i-2]，之前的状态数组完全可以丢掉，只用两个变量滚动记录就行：

def rob(nums): prev2, prev1 = 0, 0 for num in nums: cur = max(prev1, prev2 + num) prev2, prev1 = prev1, cur return prev1

这里我把prev2定义为“前i-2间的最优值”，prev1是“前i-1间的最优值”，每轮读到一个新房子，就通过这个公式推进。滚动优化不是这道题的专属技巧，hot100后面很多DP题都能用，比如最大子数组和、买卖股票系列，所以值得从这道题就开始养成习惯。面试时如果先写了数组版，再主动优化成滚动版，是加分项。

这道题还有一个变体版本值得提一下——打家劫舍II，变成了环形房子。解法思路是把环拆成两个线性问题：偷第一间则最后一间不能偷，不偷第一间则可以碰最后一间。hot100没有收录这一题，但建议有兴趣的可以自己做一遍，它考察的就是“如何把特殊约束转化为标准DP”的能力，对后续理解状态压缩和约束建模有帮助。

2.3 为什么“隔一家偷一家”不是最优策略

再展开说一下贪心失效的原因。拿[2, 1, 1, 2]举例，贪心选最大的2（第一间），然后跳过第二间，第三间只有1，偷了，第四间因为相邻又跳过，总收益3。但最优解其实是偷第一间和第四间，总收益4。贪心的问题在于每一步只看到“当前能偷的最大值”，没有考虑到偷了当前房子之后，后面连续两间都不能碰的连锁后果。

但DP不会漏掉这个组合，因为dp[i-2] + nums[i-1]这条路径明确考虑了“跳过紧邻的上一间，从更早的最优解直接跳过来”。这就是动态规划相对贪心算法的本质区别：贪心做一次决策就锁死，DP在每个状态都保留所有可能的决策结果，最后统一取最优。

理解了这一层，你会发现很多所谓的“DP难题”，本质上都是“贪心锁死了一条路，而DP保留了所有路”。

3. 最长递增子序列：以i结尾套路的典型训练

3.1 状态定义里最容易踩的坑

最长递增子序列这道题，描述一句话就够：给一个数组，找出最长的严格递增子序列长度。注意是“子序列”，不是“子数组”，意味着元素可以不连续。很多新手在这里栽跟头，以为和最大子数组和一样用“前i个元素”的状态就能搞定，结果转移方程怎么都写不顺。

先说结论：LIS要定义成dp[i]表示“以nums[i]结尾的最长递增子序列长度”。这个“以i结尾”和“前i个”的区别就是整道题的题眼。如果你定义成“前i个元素中能形成的最长递增子序列长度”，确实也成立，但你无法知道这个最长序列的最后一个元素是什么，也就没法判断下一个元素能不能接上去。而“以i结尾”强制锁定了序列末端，新元素nums[j]能不能接，只需要判断nums[j] > nums[i]即可。

转移方程也顺理成章：dp[i] = max(dp[j] + 1)，其中j的取值范围是0到i-1，并且要满足nums[j] < nums[i]。如果前面没有任何元素小于nums[i]，那dp[i]至少是1，也就是自己单独成一个序列。

初始化也比较简单，dp数组全部初始化为1。这里有一个常见错误：有人会把dp[0]初始化为0，导致整个推导全部错位。记住，每个元素自身就是长度1的递增子序列，所以1是下限。

3.2 标准O(n²)写法与复杂度推导

def length_of_lis(nums): n = len(nums) if n == 0: return 0 dp = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

两层循环，外层遍历“以谁结尾”，内层遍历“从谁转移过来”，所以时间复杂度是O(n²)。我第一次写这个解法时犯过一个错误：外层从i=1开始循环，理由是“第一个元素不用比”，但后来发现dp数组没初始化对，导致答案少1。后来统一改为从0开始，通过max(dp)取最终结果，不再纠结起点问题。

还有一个看起来不对但实际合理的点：对于完全递减的数组，比如[5, 4, 3, 2, 1]，最终答案是1不是0，因为每个元素自身可以成为一个长度为1的子序列，这是最长递增子序列定义里隐含的边界条件。

3.3 进阶方向：贪心+二分的优化版本

O(n²)在hot100大多数题目里都能过，因为数据范围通常在几千以下。但既然LIS太经典，面试官经常会追问一句“能不能优化到O(n log n)”，这里简单说一下。

优化思路是维护一个数组tails，tails[k]表示长度为k+1的递增子序列中，结尾元素的最小值。遍历nums时，用二分查找找到nums[i]在tails中应该插入的位置，如果nums[i]比所有tails元素都大，就扩展tails长度；否则替换掉第一个不小于它的元素。

这个优化不好理解的地方在于“为什么替换不会丢答案”——因为tails里存的并不是真实的子序列，只是“每个长度的最小末尾值”，这个信息足以支撑长度判断。CLRS和很多算法教材都把这一步称为patience sorting，名字唬人，本质就是个二分查找的边界操作。

我的建议是：第一阶段先把O(n²)的DP版本写熟练，能推导转移方程、能讲清楚“以i结尾”，再去啃O(n log n)优化。不要一开始就被“最优解”绑住，刷hot100的目标是建立题型映射，不是每道题都追求最优复杂度。

4. 零钱兑换：完全背包模型的遍历顺序之谜

4.1 状态定义与初始化的无穷大问题

零钱兑换题目本身很简单：给定不同面额的硬币coins和一个总金额amount，问凑出这个金额最少需要几枚硬币，凑不出来返回-1。这道题在hot100动态规划里热度很高，因为它背后是“完全背包求最小值”这个大家族——hot100里的单词拆分、分割等和子集都有它的影子。

状态定义有两种习惯，我建议用dp[i]表示“凑出金额i所需的最少硬币数”。注意和前两题的区别：这里状态的下标是“金额”，不是“数组位置”，状态空间大小由amount决定，而不是由coins长度决定。想清楚这一点很重要，因为后续的遍历逻辑就是围绕这个下标含义展开的。

初始化是关键中的关键：dp[0] = 0，其他dp[i]初始化为一个非常大的数，比如amount + 1，或者用float('inf')。这个“无穷大”不是摆设，它是为了在转移时区分“不可达状态”。如果某个金额凑不出来，那它的值永远保持无穷大，最后判断dp[amount]是否还是无穷大，就能决定返回-1还是返回结果。我见过不少新手把dp初始化成0，结果所有金额都“凑得出来”，最后一团乱麻。这个坑几乎每个刷到这题的人都会踩一次。

4.2 先遍历硬币与先遍历金额的分别

零钱兑换最迷惑的地方在于遍历顺序。很多题解直接给两版代码，一版先遍历硬币、内层遍历金额，另一版反过来，结果都能AC。但如果你不理解两者的差异，换一道变体题就立刻懵。

先遍历硬币、内层遍历金额的写法：

def coin_change(coins, amount): dp = [0] + [amount + 1] * amount for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1

这版代码的逻辑是：逐枚硬币考虑，内层循环从小到大推进金额。因为硬币可以无限使用，内层从小到大就是允许重复使用同一枚硬币——这个理解很关键，如果内层换成从大到小，就退化成“每枚硬币只能用一次”，也就是0/1背包了。零钱兑换是“完全背包”，必须从小到大。

先遍历金额、内层遍历硬币的写法：

def coin_change(coins, amount): dp = [0] + [amount + 1] * amount for i in range(1, amount + 1): for coin in coins: if i >= coin: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1

这版代码是“从金额出发，尝试每一种硬币”。两种写法在这道题里结果一样，因为状态转移只依赖更小的金额，而不管这些更小金额是通过哪些硬币凑出来的。但如果你把题目改成“求方案总数”，两个遍历顺序就会产生完全不同的含义——先硬币后金额求的是组合数，先金额后硬币求的是排列数。这个区别在hot100里就有一道题会考到，所以现在把这个点记住，后面能省几个小时。

4.3 为什么amount+1可以代替无穷大

用float('inf')做初始化当然可以，但有些面试官会追问“为什么代码里用amount+1”。原因是：凑出amount最多不可能超过amount枚硬币，因为最极端的情况是全部用面值为1的硬币，那也只需要amount枚。所以amount + 1是一个比任何合法答案都大的数，它能安全地充当“不可能”的标记，同时避免了浮点数比较带来的性能损耗和心理不适。

这个“用边界值代替无穷大”的小技巧在很多DP题里都通用。比如最小路径和里用大数标记不可达格点，编辑距离里直接给首行首列按规律填充，都属于同一类问题——初始化值的选取要保证不影响后续min/max运算，并且能区分非法状态。

我在实际做题时，通常会先写float('inf')版本确保逻辑正确，再改成amount+1版本。不是为了性能，而是为了防止自己写出“inf参与运算”时不小心出bug。比如dp[i - coin] + 1，如果dp[i - coin]是inf，那结果还是inf，Python里不会有问题，但换到某些语言里inf加1可能会产生NaN，很容易埋雷。能不用inf就不用的习惯，值得尽早养成。

5. 动态规划三件套：状态、转移、边界的通用方法论

5.1 从三道题中提炼状态设计的判断标准

刷完打家劫舍、最长递增子序列、零钱兑换，可以把状态设计的方法论抽出来。大多数一维DP的状态定义，要么是“前i个元素的某种最优结果”，要么是“以第i个元素结尾的某种属性”，要么是“目标值i的最优方案”。选择标准只有一个：转移方程能不能写得出来。

具体来说，你定义完状态后，立刻尝试写dp[i]和前面状态的关系。如果发现写不出来，大概率是状态定义漏掉了关键信息。比如LIS如果定义成“前i个元素的最长递增子序列长度”，你写转移的时候就会卡在“不知道上一个元素是什么”，这就是状态定义缺失的信号。反过来，打家劫舍定义成“前i间房子的最大收益”就能写出来，因为“最后一个房子偷不偷”这个信息不需要记——转移时只看上一步的最优值就可以了。

有一个粗略的判断技巧：如果转移时需要一个“位置指针”或者“上一个选择”的信息，那状态里多半要加一个维度，或者改用“以i结尾”而不是“前i个”。这个技巧在二维DP里更实用，比如编辑距离dp[i][j]表示“s前i个字符变到t前j个字符的最少操作数”，就是因为两个字符串的子问题必须要双下标才能描述清楚。

5.2 转移方程的三种基本形态

从这三道题里可以归纳出三种最常见的转移方程形态。

第一种是“取前值或隔项加值”，典型代表是打家劫舍和爬楼梯。dp[i] = max(dp[i-1], dp[i-k] + value[i])。特征是决策只有“选或不选前一项”，约束体现在k的大小上。后续买卖股票系列大量使用这类方程。

第二种是“枚举所有可能的转移来源”，典型代表是最长递增子序列。dp[i] = max(dp[j] + 1) for j < i。特征是当前状态可能从任意更早的状态转移过来，但需要满足一个条件（比如nums[j] < nums[i]）。这类题的时间复杂度通常高于O(n)，在hot100里属于中坚难度，最长有效括号、接雨水也都涉及类似思想。

第三种是“从目标值反推子目标”，典型代表是零钱兑换。dp[i] = min(dp[i - cost[k]] + 1) for k in choices。特征是问题被建模成“凑目标值”，每个子目标之间有加减关系，适用于背包类、凑数类题目。

你不需要刻意背这三种形态，但在复盘时试着把每道题归类，会逐渐形成“看到题目特征→匹配方程形态”的条件反射。

5.3 边界初始化的三个原则

初始化是DP里最烦人的环节，也是最容易丢分的环节。总结三个原则供你自检：

第一，dp[0]或空状态必须显式定义。打家劫舍里dp[0]代表没有房子可偷因此是0；零钱兑换里dp[0]代表凑0元需要0枚硬币。空状态通常是推导的起点，写错了整个数组全错。

第二，非法状态要有明确标记。零钱兑换里其他金额初始化为“大数”，LIS里所有位置初始化为1，打家劫舍里无需标记非法状态因为每间房都可以被跳过。到底用0还是大数还是1，取决于当前题目状态是否“恒合法”。恒合法的用0或1，可能非法的用大数或None。

第三，最终答案可能不在最后一位。打家劫舍返回dp[n]，LIS必须返回max(dp)，因为最长递增子序列不一定以最后一个元素结尾，也许中间某个元素才是最长序列的终点。很多人在这里惯性思维，以为DP答案都在dp数组末尾，结果栽了跟头。记住：只有“覆盖全局”的状态才取末尾，凡是“以某个位置结尾”的状态，都要遍历一遍取最大值。

6. 刷题打卡过程中的典型问题与排查实录

6.1 状态数组越界与下标偏移问题

这三道题里，最容易出bug的是打家劫舍的数组版本。我实际调试时遇到过一个问题：nums为空数组时，直接从dp[1]赋值会报错；nums只有一个元素时，循环从range(2, n+1)起步，需要先保证dp[1]被正确初始化。这类边界问题用几个小用例测试就能暴露，但很多人刷题时不习惯写测试用例，全靠提交后看报错。

我现在刷hot100有一个习惯：每道题写完先在本地跑三组用例——空输入、单元素输入、常规输入。空输入和单元素输入是边界，常规输入确认核心逻辑。这三个用例最多花30秒，但能过滤掉九成的低级错误。

另外注意下标偏移问题。数组版打家劫舍里，dp[i]对应的是nums[i-1]，因为dp数组下标比nums下标多1。这种偏移并不难，但在LIS这类“以i结尾”的题里，dp和nums下标完全对齐，两种模式混着写容易漏掉加减1。建议一道题内始终保持统一的“下标含义约定”，别一会儿dp[i]对应nums[i]，一会儿又对应nums[i-1]。

6.2 答案错误但逻辑“看起来对”的几种情况

刷DP最常见的挫败感来自“逻辑看起来没问题，答案就是不对”。我遇到的几种典型情况如下：

初始化不正确。LIS里初始化成0，整个dp每个位置都少1，最后结果差一点点；零钱兑换里初始化成0，导致所有金额都被认为用0枚硬币就能凑出来，转移完全失效。这类问题靠肉眼很难发现，建议在纸上手动推一遍小规模用例。

转移条件写反或漏写。LIS里的nums[j] < nums[i]写成了<=，严格递增就变成非严格递增；零钱兑换里漏掉i >= coin的判断，就会访问dp负数下标。Python下标为负不会报错，而是从数组末尾取值，这种“不报错的错误”最坑人。我排查时有个笨办法：手动在关键位置print(dp)看中间状态，比如打印LIS每次更新后的dp数组，看到底是哪一步开始数值不对。

遍历顺序颠倒。零钱兑换里先金额后硬币和先硬币后金额在这题结果一致，但如果你把内层循环写成从大到小，就变成0/1背包，答案会偏大。排查这类问题的方法是构造一个简单用例，比如coins=[1,2,5], amount=11，口算几轮就能发现遍历顺序的影响。

6.3 本地复现与调试技巧分享

刷题社区里常说“debug靠print”，我自己的体验是print大法在DP题里意外地好用。因为状态转移是逐层推进的，每一层的dp值应该是有规律的递增或变化，打印出来肉眼扫一遍，定位问题往往比人肉推演更快。以下是三种我在实际调试中高频使用的输出方式，供参考：

轻量输出法：在转移循环里加一行print(i, dp[i])，观察单个状态是否随i变化合理。适合打家劫舍、零钱兑换这类一维DP。

切片输出法：打印dp数组中某个区间的值，重点观察初始化阶段和转移密集区。比如LIS里打印前10位的dp值，确认没有发生整列偏移。

对比验证法：同时实现暴力递归版和DP版，随机生成多组小数据做对比。比如写一个暴力枚举所有子集的LIS解法，和DP版的答案逐组比对。这个方法看似多写了代码，但排查效率极高，尤其在状态定义不确定时能快速告诉我“答案差在哪”。

测试用例上，我常用来验证打家劫舍的是[2,1,1,2]，LIS用[10,9,2,5,3,7,101,18]，零钱兑换用coins=[1,2,5], amount=11。这三组用例在多个DP题里都出现过，建议你也记下来，定期拿出来做回归测试。

7. 打卡节奏管理与动态规划复习策略

7.1 每日打卡如何安排题量与难度

hot100总共100题，网上很多人说30天刷完，但我实测下来，如果每一题都真正搞懂而不是背题解，30天是肯定不够的。我的节奏是每天2到3道新题加1到2道旧题复盘，新题按专题走，旧题用随机抽选或按标签抽选。day12处在整个计划的第12天，前面几天强度适中，后几天开始加入更多的困难题，所以这个阶段的任务重心是“把DP专题的骨架搭完”。

实际操下来的经验是：每天优先保证2新题，如果有余力再加第三道。第五天开始，每天必须留出至少30分钟复盘前几天的题目，不是重写一遍，而是口头讲一遍思路。我之前写过一篇文章提到“费曼学习法用在算法题上效果奇佳”，具体做法是给自己讲：这道题的状态是什么、转移怎么写、边界怎么处理、哪一步最容易错。这个过程控制在5分钟一道题，每天复盘4到5道旧题，坚持一周，你会发现遗忘速度大幅下降。

难度分配上，建议每天最多一道难题，其余都是中低难度。原因很简单：难题的挫败感会消耗打卡动力，而连续多天高难度会导致第二天不想打开刷题软件。hot100的优秀之处在于它同时包含简单、中等、困难三档，你可以根据自己的状态灵活调节当天的难度比例，不必死板地坚持“每天必须刷三道”。

7.2 动态规划专题的复习优先级

DP专题在hot100里数量多、关联性强，复习时按以下优先级比较高效：

第一优先级是“一维基础DP”：爬楼梯、打家劫舍、最大子数组和、最长递增子序列。这些是核心套路，面试被问到的概率高，而且状态设计简单，适合用来建立信心。

第二优先级是“背包与路径DP”：零钱兑换、分割等和子集、不同路径、最小路径和。这些题引入了“二维状态”和“遍历顺序”两个新概念，是DP从入门到进阶的跳板。

第三优先级是“字符串DP与博弈DP”：编辑距离、最长回文子串、单词拆分等。这些题状态设计复杂，适合在基础题全部过完一遍后集中攻克。

day12到day14之间，我会用“重复刷旧题”的方式过掉第一优先级和第二优先级。具体做法是：今天刷完新题，隔一天重写昨天的题，隔三天再重写一遍，隔一周做一次汇总复盘。三次重写之间如果哪次卡住了，就回头重新看题解并把卡住的点记入笔记。这个方法比“每天刷五道新题”慢很多，但一个月后的记忆留存率完全不在一个量级。

7.3 保持打卡动力的心得

打卡到了第12天，新鲜感早就过去了，这时候靠的不是意志力，而是“最小启动成本”。我给自己定了一个规矩：每天打开刷题页面前先不做任何承诺，只做一道最简单、最熟的旧题热身，然后自然过渡到新题。热身题通常3到5分钟就能完成，它能迅速把脑子切换到算法思维模式，而一旦进入状态，新题带来的焦虑感会大幅降低。

另一个心得是“允许自己卡壳，但不允许自己空白”。遇到一道题二十分钟没思路，我不会继续硬刚，而是看题解的前半部分，理清状态定义和转移思路，然后关掉题解自己写完剩下的部分。这种方式介于“纯靠自己”和“直接抄题解”之间，既能学到新套路，又不至于让卡壳破坏整天的动力。

最后想说的是，hot100打卡到第12天，你会发现自己已经能秒杀当初觉得很难的链表题和二叉树题了，这种“回头看变简单”的感觉是打卡最核心的奖励。动态规划的突破也是同理，今天觉得零钱兑换的遍历顺序很绕，一周后你可能会惊讶于自己居然能给别人讲明白。坚持住，后面的编辑距离、正则表达式匹配这些真正的硬骨头，都需要这几天的积累打底。