先交代一下背景今天是我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 两种实现方案与一维滚动优化打家劫舍最直观的写法是开一个长度为n1的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²)。我第一次写这个解法时犯过一个错误外层从i1开始循环理由是“第一个元素不用比”但后来发现dp数组没初始化对导致答案少1。后来统一改为从0开始通过max(dp)取最终结果不再纠结起点问题。还有一个看起来不对但实际合理的点对于完全递减的数组比如[5, 4, 3, 2, 1]最终答案是1不是0因为每个元素自身可以成为一个长度为1的子序列这是最长递增子序列定义里隐含的边界条件。3.3 进阶方向贪心二分的优化版本O(n²)在hot100大多数题目里都能过因为数据范围通常在几千以下。但既然LIS太经典面试官经常会追问一句“能不能优化到O(n log n)”这里简单说一下。优化思路是维护一个数组tailstails[k]表示长度为k1的递增子序列中结尾元素的最小值。遍历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 为什么amount1可以代替无穷大用float(inf)做初始化当然可以但有些面试官会追问“为什么代码里用amount1”。原因是凑出amount最多不可能超过amount枚硬币因为最极端的情况是全部用面值为1的硬币那也只需要amount枚。所以amount 1是一个比任何合法答案都大的数它能安全地充当“不可能”的标记同时避免了浮点数比较带来的性能损耗和心理不适。这个“用边界值代替无穷大”的小技巧在很多DP题里都通用。比如最小路径和里用大数标记不可达格点编辑距离里直接给首行首列按规律填充都属于同一类问题——初始化值的选取要保证不影响后续min/max运算并且能区分非法状态。我在实际做题时通常会先写float(inf)版本确保逻辑正确再改成amount1版本。不是为了性能而是为了防止自己写出“inf参与运算”时不小心出bug。比如dp[i - coin] 1如果dp[i - coin]是inf那结果还是infPython里不会有问题但换到某些语言里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, n1)起步需要先保证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], amount11口算几轮就能发现遍历顺序的影响。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], amount11。这三组用例在多个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天你会发现自己已经能秒杀当初觉得很难的链表题和二叉树题了这种“回头看变简单”的感觉是打卡最核心的奖励。动态规划的突破也是同理今天觉得零钱兑换的遍历顺序很绕一周后你可能会惊讶于自己居然能给别人讲明白。坚持住后面的编辑距离、正则表达式匹配这些真正的硬骨头都需要这几天的积累打底。