1. 从“打家劫舍”到动态规划一个算法竞赛的经典入口如果你正在备战蓝桥杯这类算法竞赛看到“打家劫舍”这个题目第一反应可能是觉得有趣甚至有点“不正经”。但恰恰是这道题它几乎是所有动态规划入门者无法绕开的一座里程碑。我第一次在LeetCode上刷到它时也觉得名字起得挺有意思但真正理解其背后的思想后才发现它是一把打开动态规划大门的绝佳钥匙。动态规划Dynamic Programming, DP是算法竞赛中的核心考点尤其在蓝桥杯国赛级别的比赛中对DP的考察往往决定了你能走多远。而“打家劫舍”及其一系列变种完美地诠释了DP最核心的“状态定义”和“状态转移”思想。今天我们就以这道题为每日一练的起点彻底拆解其原理并延伸到竞赛中常见的变形目标是让你不仅会解这一道题更能掌握解决一类题的方法论为冲刺国赛打下坚实基础。2. “打家劫舍”原题精析状态与选择的艺术我们先来看最经典的“打家劫舍I”问题描述你是一个专业的小偷计划偷窃一条街上的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。2.1 为什么暴力搜索会“爆炸”面对这个问题新手最容易想到的方法是“穷举”尝试所有可能的偷窃组合然后找出最大值。对于一个长度为n的数组每个房子有两种状态偷或不偷但受限于“不能偷相邻房子”的约束实际可能的组合数仍然是指数级别的近似于斐波那契数列增长。当n30时计算量已经非常庞大n100时任何计算机都无法在短时间内穷举完毕。这就是算法中典型的“组合爆炸”问题也引出了我们为什么需要动态规划——避免重复计算子问题。2.2 定义状态抓住问题的本质动态规划的第一步也是最关键的一步就是定义“状态”。状态就是我们试图解的子问题的一种描述。对于“打家劫舍”我们到底关心什么我们关心的是“从某个位置开始能获得的最大金额”。但这样定义有点模糊。一个更精准、更高效的定义是设 dp[i] 表示考虑前 i 个房屋下标从0开始或从1开始需明确时能偷窃到的最高金额。这里有一个至关重要的细节“考虑前i个房屋”并不意味着一定要偷第i个房屋。dp[i]是一个结果它已经包含了在第i个房屋上“偷”与“不偷”这两种决策中的最优解。这个定义是理解整个问题的基石。2.3 推导状态转移方程决策的逻辑定义了状态接下来就要找出状态之间的关系即状态转移方程。我们如何从已知的小问题答案推导出更大问题的答案当我们计算dp[i]时面对第 i 个房屋假设是第 i 个索引从1开始我们只有两种选择偷第 i 个房屋那么第 i-1 个房屋绝对不能偷。因此此时能获得的最大金额是“前 i-2 个房屋的最大金额”加上“第 i 个房屋的金额”。即dp[i-2] nums[i]。不偷第 i 个房屋那么问题就退化成了“考虑前 i-1 个房屋”的情况。此时能获得的最大金额就是dp[i-1]。我们的目标是最大化总金额所以dp[i]应该取这两种选择中的较大值dp[i] max(dp[i-1], dp[i-2] nums[i])这就是本问题的核心状态转移方程。它清晰地体现了“最优子结构”性质大问题的最优解可以由小问题的最优解推导出来。2.4 初始化与边界处理细节决定成败有了方程我们还需要知道最开始怎么算。也就是初始化dp数组。dp[0]考虑前0个房屋能偷的最大金额显然是0。dp[1]考虑前1个房屋我们只能偷它因为只有一个所以dp[1] nums[0]注意这里nums索引从0开始nums[0]对应第一个房屋。在实际编码中我们通常会让dp数组的长度为n1如果房屋编号从1开始思考并将dp[0]和dp[1]按上述规则初始化然后从i2开始循环计算到in。注意这是最容易出错的地方之一。一定要明确你的dp数组下标含义与nums数组下标含义的对应关系。另一种常见且更简洁的写法是dp[i]表示考虑下标为[0, i]的房屋此时dp[0] nums[0],dp[1] max(nums[0], nums[1])然后从i2开始转移。两种思路都可以但必须自洽。2.5 代码实现与空间优化基于以上分析标准的动态规划实现如下Python语言def rob(nums): if not nums: return 0 n len(nums) if n 1: return nums[0] # 创建dp数组 dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): # 状态转移方程 dp[i] max(dp[i-1], dp[i-2] nums[i]) return dp[-1] # 最后一个元素就是考虑所有房屋的最大值观察状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])你会发现计算dp[i]时只依赖于前两个状态dp[i-1]和dp[i-2]。这意味着我们不需要保存整个dp数组只用两个变量滚动记录即可将空间复杂度从 O(n) 优化到 O(1)。这在竞赛中是一个重要的优化点尤其当数据量巨大时。def rob_optimized(nums): if not nums: return 0 n len(nums) if n 1: return nums[0] # 用两个变量代替整个dp数组 prev2 nums[0] # 相当于 dp[i-2] prev1 max(nums[0], nums[1]) # 相当于 dp[i-1] for i in range(2, n): current max(prev1, prev2 nums[i]) prev2, prev1 prev1, current # 滚动更新 return prev13. 竞赛进阶掌握“打家劫舍”的三大经典变种在蓝桥杯等竞赛中直接考原题的情况较少更多的是考察变种和应用能力。熟练掌握以下三个变种能让你在面对复杂DP问题时游刃有余。3.1 变种一环形街道打家劫舍 II问题描述所有房屋围成一圈即第一个房屋和最后一个房屋相邻。其他条件不变。核心难点环的存在打破了原来的线性序列首尾产生了制约。解题思路既然首尾不能同时被偷那么我们可以将环状问题拆解成两个线性问题考虑偷第一家不偷最后一家。即计算nums[0: n-1]这个线性数组的最大值。考虑不偷第一家可以偷最后一家。即计算nums[1: n]这个线性数组的最大值。最终结果就是这两个线性问题结果的最大值。这样我们就巧妙地将一个环形DP问题转化为了两个我们已经解决了的线性DP问题。def rob_ii(nums): def rob_linear(sub_nums): # 复用上面优化版的线性打家劫舍代码 prev2 prev1 0 for num in sub_nums: prev2, prev1 prev1, max(prev1, prev2 num) return prev1 n len(nums) if n 0: return 0 if n 1: return nums[0] # 拆解成两个子问题 return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))实操心得这是解决环形DP的经典套路——“破环成链”。很多复杂的环形问题都可以通过枚举“断点”或者分类讨论转化为若干个线性问题来处理。在竞赛中看到“环形”、“首尾相连”等字眼要立刻想到这种思路。3.2 变种二树形住宅区打家劫舍 III问题描述房屋之间的相邻关系构成一棵二叉树。小偷不能偷直接相连父子节点的房屋。核心难点数据结构从数组变成了树决策在每个节点上进行且需要从子节点的信息汇总到父节点。解题思路这需要用到树形动态规划树形DP。对于树中的任何一个节点我们定义两个状态dp[0]表示不偷当前节点时以当前节点为根的子树能获得的最大金额。dp[1]表示偷当前节点时以当前节点为根的子树能获得的最大金额。那么状态转移就需要在递归遍历后序遍历的过程中完成如果偷当前节点则左右子节点都不能偷dp[1] node.val left[0] right[0]如果不偷当前节点则左右子节点可以偷也可以不偷我们取最大值dp[0] max(left[0], left[1]) max(right[0], right[1])最终根节点的max(dp[0], dp[1])就是答案。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def rob_iii(root): def dfs(node): if not node: return (0, 0) # (不偷该节点的最大值 偷该节点的最大值) left dfs(node.left) right dfs(node.right) # 不偷当前节点 not_rob max(left[0], left[1]) max(right[0], right[1]) # 偷当前节点 rob node.val left[0] right[0] return (not_rob, rob) result dfs(root) return max(result[0], result[1])避坑指南树形DP的递归函数通常需要返回一个数组或元组携带多种状态信息。务必明确递归函数返回值的定义并在纸上画一个小树模拟一下计算过程否则很容易被绕晕。另外注意递归深度在竞赛中如果树可能退化成链深度很大需要考虑是否会被递归栈溢出有时需要用迭代法拓扑排序来替代递归。3.3 变种三带冷却期的股票买卖另一种视角虽然不叫“打家劫舍”但“最佳买卖股票时机含冷冻期”这个问题其DP内核与“打家劫舍”异曲同工。问题描述卖出股票后有一天的冷冻期期间不能买入。求最大利润。状态定义我们可以定义三个状态dp[i][0]第i天结束时持有股票的最大利润。dp[i][1]第i天结束时不持有股票且处于冷冻期即今天卖出了股票的最大利润。dp[i][2]第i天结束时不持有股票且不处于冷冻期的最大利润。状态转移dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])昨天就持有或者昨天非冷冻期今天买入dp[i][1] dp[i-1][0] prices[i]今天卖出进入冷冻期dp[i][2] max(dp[i-1][2], dp[i-1][1])昨天就不持有且非冷冻或者昨天冷冻期结束你会发现这里的“冷冻期”约束与“打家劫舍”中“不能偷相邻房屋”的约束在状态转移的逻辑上非常相似都是限制了某些连续操作不能发生。理解这一点就能将解决“打家劫舍”的思维迁移到更多具有“间隔限制”的DP问题上。4. 蓝桥杯国赛级DP备战策略与实战技巧掌握了“打家劫舍”及其变种只能说拿到了DP领域的入场券。要想在国赛中应对更复杂的DP问题还需要系统的策略和扎实的技巧。4.1 如何识别一道题是动态规划问题这是解题的第一步。通常一个问题如果同时具备以下两个性质就极有可能用DP解决最优子结构一个问题的最优解包含其子问题的最优解。比如“打家劫舍”中前i个房子的最优解必然由前i-1或前i-2个房子的最优解推导而来。重叠子问题在递归求解过程中会反复计算相同的子问题。比如在暴力穷举“打家劫舍”时计算“从第3个房子开始偷”的方案会被重复计算很多次。在竞赛中常见的DP问题特征还包括求“最大值”、“最小值”、“方案数”、“是否可行”问题可以被分解为多个阶段每个阶段有若干状态当前阶段的状态可以由前面阶段的状态转移而来。4.2 动态规划的解题四步法这是一个通用的思考框架务必内化定义状态明确dp数组或变量以及下标的含义。这是最重要也最难的一步。多问自己我要记录什么信息这个信息足以推导出下一步吗确定状态转移方程找出dp[i]与dp[i-1]、dp[i-2]... 之间的关系。这是DP的核心需要严谨的逻辑推导。初始化找到递推的起点。哪些状态是可以直接得到的比如dp[0],dp[1]初始化错误会导致全盘皆输。确定遍历顺序与计算答案确定循环是正序还是倒序最终答案存储在哪个状态里是dp[n]还是max(dp)4.3 从“打家劫舍”延伸出的DP类型“打家劫舍”属于最简单的“线性DP”。以此为基础你需要进一步拓展知识面背包DP0-1背包、完全背包、多重背包。这是竞赛必考题型核心是“容量”和“价值”的权衡。可以理解为一种特殊的“打家劫舍”——每个物品房子偷或不偷但多了总容量限制。区间DP典型问题是“石子合并”、“最长回文子序列”。状态通常定义为dp[i][j]表示区间[i, j]上的最优解。遍历顺序往往是先枚举区间长度。状态压缩DP当状态可以用二进制位表示时如“旅行商问题TSP”、“铺瓷砖问题”可以用一个整数的二进制位来压缩表示一个状态集合极大提升效率。数位DP统计满足特定条件的数字个数例如“数字1的个数”。需要结合数位分析和记忆化搜索。4.4 竞赛实战中的调试与优化技巧画表法对于线性DP在纸上画出dp数组手动模拟前几步的计算过程。这是验证状态转移方程和初始化是否正确的最直观方法。对于“打家劫舍”你可以列一个表格分别写出nums[i]、dp[i]以及每次计算max(dp[i-1], dp[i-2]nums[i])的过程。打印中间状态在代码中关键步骤后打印dp数组与你的手动推算结果对比。这是线上调试无法替代的本地调试手段。空间优化像“打家劫舍”一样观察状态转移方程是否只依赖于有限的几个前驱状态。如果是就用滚动变量如prev2,prev1,curr替代数组。记忆化搜索对于树形DP或难以确定遍历顺序的DP可以先用“记忆化搜索”递归缓存的方式实现思路更直观然后再尝试转化为递推迭代形式。rob_iii的解法就是典型的记忆化搜索思想。注意数据范围与初始化蓝桥杯的题目经常会设置边界条件陷阱。比如数组为空、长度为1、所有金额为0等情况。你的代码必须能妥善处理这些情况。dp数组的初始化值也要仔细斟酌有时需要初始化为无穷大求最小值时或一个不可能的值。5. 以“打家劫舍”为起点的每日一练计划建议冲刺国赛仅理解一道题是不够的需要系统的、持续的练习。我建议围绕DP主题制定一个为期4-6周的每日一练计划第一周基础夯实周Day1-2彻底吃透“打家劫舍I, II, III”做到能白板编码能讲解状态定义和转移方程。Day3-4练习经典线性DP如“爬楼梯”斐波那契、“最小路径和”、“最长递增子序列(LIS)”。体会状态定义的不同方式。Day5-6入门背包DP。从“0-1背包”和“完全背包”的经典模板题开始理解“容量”和“物品”两层循环的内涵。Day7总结复盘整理本周的DP状态定义和转移方程模板。第二周背包与序列深化周Day8-10深入练习背包变种问题求方案数、求具体方案、二维费用背包、分组背包。Day11-13攻克序列DP如“最长公共子序列(LCS)”、“编辑距离”。这类问题通常是二维dp[i][j]思考难度上了一个台阶。Day14进行一场模拟赛专门做包含背包和序列DP的真题或高质量练习题。第三周区间与状态压缩周Day15-17学习区间DP理解“枚举区间长度-枚举左端点-计算”的三重循环模式。Day18-20接触状态压缩DP。从简单的“旅行商问题”状压解法开始理解用二进制位表示“是否访问过”的状态。Day21复盘整理区间DP和状压DP的常见模型和位运算技巧。第四周及以后综合应用与真题冲刺每天保持1-2道中等难度以上的综合DP题练习优先做蓝桥杯历年国赛真题中的DP题。建立自己的错题本记录每道错题或难题的核心状态定义和转移方程以及自己卡壳的原因。尝试对同一道题进行空间优化或者用不同的状态定义去解决它比较优劣。最后我想分享一个最深的体会动态规划的本质是“聪明地穷举”。它之所以难是因为它要求我们跳出一步步模拟过程的惯性思维转而从“状态”和“决策”的更高维度去思考问题。而“打家劫舍”正是训练这种思维的最佳启蒙题。当你拿到一道新题能下意识地去想“有什么状态状态之间如何转移”你就已经入门了。国赛之路道阻且长但把每个这样的经典模型吃透、练熟一步步积累信心和能力你会发现曾经望而生畏的DP最终会成为你手中最有力的武器之一。 动态规划入门：从打家劫舍问题解析状态定义与转移方程
1. 从“打家劫舍”到动态规划一个算法竞赛的经典入口如果你正在备战蓝桥杯这类算法竞赛看到“打家劫舍”这个题目第一反应可能是觉得有趣甚至有点“不正经”。但恰恰是这道题它几乎是所有动态规划入门者无法绕开的一座里程碑。我第一次在LeetCode上刷到它时也觉得名字起得挺有意思但真正理解其背后的思想后才发现它是一把打开动态规划大门的绝佳钥匙。动态规划Dynamic Programming, DP是算法竞赛中的核心考点尤其在蓝桥杯国赛级别的比赛中对DP的考察往往决定了你能走多远。而“打家劫舍”及其一系列变种完美地诠释了DP最核心的“状态定义”和“状态转移”思想。今天我们就以这道题为每日一练的起点彻底拆解其原理并延伸到竞赛中常见的变形目标是让你不仅会解这一道题更能掌握解决一类题的方法论为冲刺国赛打下坚实基础。2. “打家劫舍”原题精析状态与选择的艺术我们先来看最经典的“打家劫舍I”问题描述你是一个专业的小偷计划偷窃一条街上的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。2.1 为什么暴力搜索会“爆炸”面对这个问题新手最容易想到的方法是“穷举”尝试所有可能的偷窃组合然后找出最大值。对于一个长度为n的数组每个房子有两种状态偷或不偷但受限于“不能偷相邻房子”的约束实际可能的组合数仍然是指数级别的近似于斐波那契数列增长。当n30时计算量已经非常庞大n100时任何计算机都无法在短时间内穷举完毕。这就是算法中典型的“组合爆炸”问题也引出了我们为什么需要动态规划——避免重复计算子问题。2.2 定义状态抓住问题的本质动态规划的第一步也是最关键的一步就是定义“状态”。状态就是我们试图解的子问题的一种描述。对于“打家劫舍”我们到底关心什么我们关心的是“从某个位置开始能获得的最大金额”。但这样定义有点模糊。一个更精准、更高效的定义是设 dp[i] 表示考虑前 i 个房屋下标从0开始或从1开始需明确时能偷窃到的最高金额。这里有一个至关重要的细节“考虑前i个房屋”并不意味着一定要偷第i个房屋。dp[i]是一个结果它已经包含了在第i个房屋上“偷”与“不偷”这两种决策中的最优解。这个定义是理解整个问题的基石。2.3 推导状态转移方程决策的逻辑定义了状态接下来就要找出状态之间的关系即状态转移方程。我们如何从已知的小问题答案推导出更大问题的答案当我们计算dp[i]时面对第 i 个房屋假设是第 i 个索引从1开始我们只有两种选择偷第 i 个房屋那么第 i-1 个房屋绝对不能偷。因此此时能获得的最大金额是“前 i-2 个房屋的最大金额”加上“第 i 个房屋的金额”。即dp[i-2] nums[i]。不偷第 i 个房屋那么问题就退化成了“考虑前 i-1 个房屋”的情况。此时能获得的最大金额就是dp[i-1]。我们的目标是最大化总金额所以dp[i]应该取这两种选择中的较大值dp[i] max(dp[i-1], dp[i-2] nums[i])这就是本问题的核心状态转移方程。它清晰地体现了“最优子结构”性质大问题的最优解可以由小问题的最优解推导出来。2.4 初始化与边界处理细节决定成败有了方程我们还需要知道最开始怎么算。也就是初始化dp数组。dp[0]考虑前0个房屋能偷的最大金额显然是0。dp[1]考虑前1个房屋我们只能偷它因为只有一个所以dp[1] nums[0]注意这里nums索引从0开始nums[0]对应第一个房屋。在实际编码中我们通常会让dp数组的长度为n1如果房屋编号从1开始思考并将dp[0]和dp[1]按上述规则初始化然后从i2开始循环计算到in。注意这是最容易出错的地方之一。一定要明确你的dp数组下标含义与nums数组下标含义的对应关系。另一种常见且更简洁的写法是dp[i]表示考虑下标为[0, i]的房屋此时dp[0] nums[0],dp[1] max(nums[0], nums[1])然后从i2开始转移。两种思路都可以但必须自洽。2.5 代码实现与空间优化基于以上分析标准的动态规划实现如下Python语言def rob(nums): if not nums: return 0 n len(nums) if n 1: return nums[0] # 创建dp数组 dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): # 状态转移方程 dp[i] max(dp[i-1], dp[i-2] nums[i]) return dp[-1] # 最后一个元素就是考虑所有房屋的最大值观察状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])你会发现计算dp[i]时只依赖于前两个状态dp[i-1]和dp[i-2]。这意味着我们不需要保存整个dp数组只用两个变量滚动记录即可将空间复杂度从 O(n) 优化到 O(1)。这在竞赛中是一个重要的优化点尤其当数据量巨大时。def rob_optimized(nums): if not nums: return 0 n len(nums) if n 1: return nums[0] # 用两个变量代替整个dp数组 prev2 nums[0] # 相当于 dp[i-2] prev1 max(nums[0], nums[1]) # 相当于 dp[i-1] for i in range(2, n): current max(prev1, prev2 nums[i]) prev2, prev1 prev1, current # 滚动更新 return prev13. 竞赛进阶掌握“打家劫舍”的三大经典变种在蓝桥杯等竞赛中直接考原题的情况较少更多的是考察变种和应用能力。熟练掌握以下三个变种能让你在面对复杂DP问题时游刃有余。3.1 变种一环形街道打家劫舍 II问题描述所有房屋围成一圈即第一个房屋和最后一个房屋相邻。其他条件不变。核心难点环的存在打破了原来的线性序列首尾产生了制约。解题思路既然首尾不能同时被偷那么我们可以将环状问题拆解成两个线性问题考虑偷第一家不偷最后一家。即计算nums[0: n-1]这个线性数组的最大值。考虑不偷第一家可以偷最后一家。即计算nums[1: n]这个线性数组的最大值。最终结果就是这两个线性问题结果的最大值。这样我们就巧妙地将一个环形DP问题转化为了两个我们已经解决了的线性DP问题。def rob_ii(nums): def rob_linear(sub_nums): # 复用上面优化版的线性打家劫舍代码 prev2 prev1 0 for num in sub_nums: prev2, prev1 prev1, max(prev1, prev2 num) return prev1 n len(nums) if n 0: return 0 if n 1: return nums[0] # 拆解成两个子问题 return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))实操心得这是解决环形DP的经典套路——“破环成链”。很多复杂的环形问题都可以通过枚举“断点”或者分类讨论转化为若干个线性问题来处理。在竞赛中看到“环形”、“首尾相连”等字眼要立刻想到这种思路。3.2 变种二树形住宅区打家劫舍 III问题描述房屋之间的相邻关系构成一棵二叉树。小偷不能偷直接相连父子节点的房屋。核心难点数据结构从数组变成了树决策在每个节点上进行且需要从子节点的信息汇总到父节点。解题思路这需要用到树形动态规划树形DP。对于树中的任何一个节点我们定义两个状态dp[0]表示不偷当前节点时以当前节点为根的子树能获得的最大金额。dp[1]表示偷当前节点时以当前节点为根的子树能获得的最大金额。那么状态转移就需要在递归遍历后序遍历的过程中完成如果偷当前节点则左右子节点都不能偷dp[1] node.val left[0] right[0]如果不偷当前节点则左右子节点可以偷也可以不偷我们取最大值dp[0] max(left[0], left[1]) max(right[0], right[1])最终根节点的max(dp[0], dp[1])就是答案。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def rob_iii(root): def dfs(node): if not node: return (0, 0) # (不偷该节点的最大值 偷该节点的最大值) left dfs(node.left) right dfs(node.right) # 不偷当前节点 not_rob max(left[0], left[1]) max(right[0], right[1]) # 偷当前节点 rob node.val left[0] right[0] return (not_rob, rob) result dfs(root) return max(result[0], result[1])避坑指南树形DP的递归函数通常需要返回一个数组或元组携带多种状态信息。务必明确递归函数返回值的定义并在纸上画一个小树模拟一下计算过程否则很容易被绕晕。另外注意递归深度在竞赛中如果树可能退化成链深度很大需要考虑是否会被递归栈溢出有时需要用迭代法拓扑排序来替代递归。3.3 变种三带冷却期的股票买卖另一种视角虽然不叫“打家劫舍”但“最佳买卖股票时机含冷冻期”这个问题其DP内核与“打家劫舍”异曲同工。问题描述卖出股票后有一天的冷冻期期间不能买入。求最大利润。状态定义我们可以定义三个状态dp[i][0]第i天结束时持有股票的最大利润。dp[i][1]第i天结束时不持有股票且处于冷冻期即今天卖出了股票的最大利润。dp[i][2]第i天结束时不持有股票且不处于冷冻期的最大利润。状态转移dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])昨天就持有或者昨天非冷冻期今天买入dp[i][1] dp[i-1][0] prices[i]今天卖出进入冷冻期dp[i][2] max(dp[i-1][2], dp[i-1][1])昨天就不持有且非冷冻或者昨天冷冻期结束你会发现这里的“冷冻期”约束与“打家劫舍”中“不能偷相邻房屋”的约束在状态转移的逻辑上非常相似都是限制了某些连续操作不能发生。理解这一点就能将解决“打家劫舍”的思维迁移到更多具有“间隔限制”的DP问题上。4. 蓝桥杯国赛级DP备战策略与实战技巧掌握了“打家劫舍”及其变种只能说拿到了DP领域的入场券。要想在国赛中应对更复杂的DP问题还需要系统的策略和扎实的技巧。4.1 如何识别一道题是动态规划问题这是解题的第一步。通常一个问题如果同时具备以下两个性质就极有可能用DP解决最优子结构一个问题的最优解包含其子问题的最优解。比如“打家劫舍”中前i个房子的最优解必然由前i-1或前i-2个房子的最优解推导而来。重叠子问题在递归求解过程中会反复计算相同的子问题。比如在暴力穷举“打家劫舍”时计算“从第3个房子开始偷”的方案会被重复计算很多次。在竞赛中常见的DP问题特征还包括求“最大值”、“最小值”、“方案数”、“是否可行”问题可以被分解为多个阶段每个阶段有若干状态当前阶段的状态可以由前面阶段的状态转移而来。4.2 动态规划的解题四步法这是一个通用的思考框架务必内化定义状态明确dp数组或变量以及下标的含义。这是最重要也最难的一步。多问自己我要记录什么信息这个信息足以推导出下一步吗确定状态转移方程找出dp[i]与dp[i-1]、dp[i-2]... 之间的关系。这是DP的核心需要严谨的逻辑推导。初始化找到递推的起点。哪些状态是可以直接得到的比如dp[0],dp[1]初始化错误会导致全盘皆输。确定遍历顺序与计算答案确定循环是正序还是倒序最终答案存储在哪个状态里是dp[n]还是max(dp)4.3 从“打家劫舍”延伸出的DP类型“打家劫舍”属于最简单的“线性DP”。以此为基础你需要进一步拓展知识面背包DP0-1背包、完全背包、多重背包。这是竞赛必考题型核心是“容量”和“价值”的权衡。可以理解为一种特殊的“打家劫舍”——每个物品房子偷或不偷但多了总容量限制。区间DP典型问题是“石子合并”、“最长回文子序列”。状态通常定义为dp[i][j]表示区间[i, j]上的最优解。遍历顺序往往是先枚举区间长度。状态压缩DP当状态可以用二进制位表示时如“旅行商问题TSP”、“铺瓷砖问题”可以用一个整数的二进制位来压缩表示一个状态集合极大提升效率。数位DP统计满足特定条件的数字个数例如“数字1的个数”。需要结合数位分析和记忆化搜索。4.4 竞赛实战中的调试与优化技巧画表法对于线性DP在纸上画出dp数组手动模拟前几步的计算过程。这是验证状态转移方程和初始化是否正确的最直观方法。对于“打家劫舍”你可以列一个表格分别写出nums[i]、dp[i]以及每次计算max(dp[i-1], dp[i-2]nums[i])的过程。打印中间状态在代码中关键步骤后打印dp数组与你的手动推算结果对比。这是线上调试无法替代的本地调试手段。空间优化像“打家劫舍”一样观察状态转移方程是否只依赖于有限的几个前驱状态。如果是就用滚动变量如prev2,prev1,curr替代数组。记忆化搜索对于树形DP或难以确定遍历顺序的DP可以先用“记忆化搜索”递归缓存的方式实现思路更直观然后再尝试转化为递推迭代形式。rob_iii的解法就是典型的记忆化搜索思想。注意数据范围与初始化蓝桥杯的题目经常会设置边界条件陷阱。比如数组为空、长度为1、所有金额为0等情况。你的代码必须能妥善处理这些情况。dp数组的初始化值也要仔细斟酌有时需要初始化为无穷大求最小值时或一个不可能的值。5. 以“打家劫舍”为起点的每日一练计划建议冲刺国赛仅理解一道题是不够的需要系统的、持续的练习。我建议围绕DP主题制定一个为期4-6周的每日一练计划第一周基础夯实周Day1-2彻底吃透“打家劫舍I, II, III”做到能白板编码能讲解状态定义和转移方程。Day3-4练习经典线性DP如“爬楼梯”斐波那契、“最小路径和”、“最长递增子序列(LIS)”。体会状态定义的不同方式。Day5-6入门背包DP。从“0-1背包”和“完全背包”的经典模板题开始理解“容量”和“物品”两层循环的内涵。Day7总结复盘整理本周的DP状态定义和转移方程模板。第二周背包与序列深化周Day8-10深入练习背包变种问题求方案数、求具体方案、二维费用背包、分组背包。Day11-13攻克序列DP如“最长公共子序列(LCS)”、“编辑距离”。这类问题通常是二维dp[i][j]思考难度上了一个台阶。Day14进行一场模拟赛专门做包含背包和序列DP的真题或高质量练习题。第三周区间与状态压缩周Day15-17学习区间DP理解“枚举区间长度-枚举左端点-计算”的三重循环模式。Day18-20接触状态压缩DP。从简单的“旅行商问题”状压解法开始理解用二进制位表示“是否访问过”的状态。Day21复盘整理区间DP和状压DP的常见模型和位运算技巧。第四周及以后综合应用与真题冲刺每天保持1-2道中等难度以上的综合DP题练习优先做蓝桥杯历年国赛真题中的DP题。建立自己的错题本记录每道错题或难题的核心状态定义和转移方程以及自己卡壳的原因。尝试对同一道题进行空间优化或者用不同的状态定义去解决它比较优劣。最后我想分享一个最深的体会动态规划的本质是“聪明地穷举”。它之所以难是因为它要求我们跳出一步步模拟过程的惯性思维转而从“状态”和“决策”的更高维度去思考问题。而“打家劫舍”正是训练这种思维的最佳启蒙题。当你拿到一道新题能下意识地去想“有什么状态状态之间如何转移”你就已经入门了。国赛之路道阻且长但把每个这样的经典模型吃透、练熟一步步积累信心和能力你会发现曾经望而生畏的DP最终会成为你手中最有力的武器之一。