动态规划入门：从打家劫舍问题解析状态定义与转移方程

1. 从“打家劫舍”到动态规划：一个算法竞赛的经典入口

如果你正在备战蓝桥杯这类算法竞赛，看到“打家劫舍”这个题目，第一反应可能是觉得有趣甚至有点“不正经”。但恰恰是这道题，它几乎是所有动态规划入门者无法绕开的一座里程碑。我第一次在LeetCode上刷到它时，也觉得名字起得挺有意思，但真正理解其背后的思想后，才发现它是一把打开动态规划大门的绝佳钥匙。动态规划（Dynamic Programming, DP）是算法竞赛中的核心考点，尤其在蓝桥杯国赛级别的比赛中，对DP的考察往往决定了你能走多远。而“打家劫舍”及其一系列变种，完美地诠释了DP最核心的“状态定义”和“状态转移”思想。今天，我们就以这道题为每日一练的起点，彻底拆解其原理，并延伸到竞赛中常见的变形，目标是让你不仅会解这一道题，更能掌握解决一类题的方法论，为冲刺国赛打下坚实基础。

2. “打家劫舍”原题精析：状态与选择的艺术

我们先来看最经典的“打家劫舍I”问题描述：你是一个专业的小偷，计划偷窃一条街上的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

2.1 为什么暴力搜索会“爆炸”？

面对这个问题，新手最容易想到的方法是“穷举”：尝试所有可能的偷窃组合，然后找出最大值。对于一个长度为n的数组，每个房子有两种状态（偷或不偷），但受限于“不能偷相邻房子”的约束，实际可能的组合数仍然是指数级别的（近似于斐波那契数列增长）。当n=30时，计算量已经非常庞大；n=100时，任何计算机都无法在短时间内穷举完毕。这就是算法中典型的“组合爆炸”问题，也引出了我们为什么需要动态规划——避免重复计算子问题。

2.2 定义状态：抓住问题的本质

动态规划的第一步，也是最关键的一步，就是定义“状态”。状态就是我们试图解的子问题的一种描述。对于“打家劫舍”，我们到底关心什么？我们关心的是“从某个位置开始，能获得的最大金额”。但这样定义有点模糊。一个更精准、更高效的定义是：设 dp[i] 表示考虑前 i 个房屋（下标从0开始或从1开始需明确）时，能偷窃到的最高金额。

这里有一个至关重要的细节：“考虑前i个房屋”并不意味着一定要偷第i个房屋。dp[i]是一个结果，它已经包含了在第i个房屋上“偷”与“不偷”这两种决策中的最优解。这个定义是理解整个问题的基石。

2.3 推导状态转移方程：决策的逻辑

定义了状态，接下来就要找出状态之间的关系，即状态转移方程。我们如何从已知的小问题答案，推导出更大问题的答案？

当我们计算dp[i]时，面对第 i 个房屋（假设是第 i 个，索引从1开始），我们只有两种选择：

1. 偷第 i 个房屋：那么第 i-1 个房屋绝对不能偷。因此，此时能获得的最大金额是“前 i-2 个房屋的最大金额”加上“第 i 个房屋的金额”。即dp[i-2] + nums[i]。
2. 不偷第 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数组的长度为n+1（如果房屋编号从1开始思考），并将dp[0]和dp[1]按上述规则初始化，然后从i=2开始循环计算到i=n。

注意：这是最容易出错的地方之一。一定要明确你的dp数组下标含义与nums数组下标含义的对应关系。另一种常见且更简洁的写法是：dp[i]表示考虑下标为[0, i]的房屋，此时dp[0] = nums[0],dp[1] = max(nums[0], nums[1])，然后从i=2开始转移。两种思路都可以，但必须自洽。

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 prev1

3. 竞赛进阶：掌握“打家劫舍”的三大经典变种

在蓝桥杯等竞赛中，直接考原题的情况较少，更多的是考察变种和应用能力。熟练掌握以下三个变种，能让你在面对复杂DP问题时游刃有余。

3.1 变种一：环形街道（打家劫舍 II）

问题描述：所有房屋围成一圈，即第一个房屋和最后一个房屋相邻。其他条件不变。

核心难点：环的存在打破了原来的线性序列，首尾产生了制约。

解题思路：既然首尾不能同时被偷，那么我们可以将环状问题拆解成两个线性问题：

1. 考虑偷第一家，不偷最后一家。即计算nums[0: n-1]这个线性数组的最大值。
2. 考虑不偷第一家，可以偷最后一家。即计算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, val=0, left=None, right=None): 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解决：

1. 最优子结构：一个问题的最优解包含其子问题的最优解。比如“打家劫舍”中，前i个房子的最优解，必然由前i-1或前i-2个房子的最优解推导而来。
2. 重叠子问题：在递归求解过程中，会反复计算相同的子问题。比如在暴力穷举“打家劫舍”时，计算“从第3个房子开始偷”的方案会被重复计算很多次。

在竞赛中，常见的DP问题特征还包括：求“最大值”、“最小值”、“方案数”、“是否可行”；问题可以被分解为多个阶段；每个阶段有若干状态；当前阶段的状态可以由前面阶段的状态转移而来。

4.2 动态规划的解题四步法

这是一个通用的思考框架，务必内化：

1. 定义状态：明确dp数组（或变量）以及下标的含义。这是最重要也最难的一步。多问自己：我要记录什么信息？这个信息足以推导出下一步吗？
2. 确定状态转移方程：找出dp[i]与dp[i-1]、dp[i-2]... 之间的关系。这是DP的核心，需要严谨的逻辑推导。
3. 初始化：找到递推的起点。哪些状态是可以直接得到的（比如dp[0],dp[1]）？初始化错误会导致全盘皆输。
4. 确定遍历顺序与计算答案：确定循环是正序还是倒序？最终答案存储在哪个状态里？（是dp[n]还是max(dp)？）

4.3 从“打家劫舍”延伸出的DP类型

“打家劫舍”属于最简单的“线性DP”。以此为基础，你需要进一步拓展知识面：

• 背包DP：0-1背包、完全背包、多重背包。这是竞赛必考题型，核心是“容量”和“价值”的权衡。可以理解为一种特殊的“打家劫舍”——每个物品（房子）偷或不偷，但多了总容量限制。
• 区间DP：典型问题是“石子合并”、“最长回文子序列”。状态通常定义为dp[i][j]，表示区间[i, j]上的最优解。遍历顺序往往是先枚举区间长度。
• 状态压缩DP：当状态可以用二进制位表示时（如“旅行商问题TSP”、“铺瓷砖问题”），可以用一个整数的二进制位来压缩表示一个状态集合，极大提升效率。
• 数位DP：统计满足特定条件的数字个数，例如“数字1的个数”。需要结合数位分析和记忆化搜索。

4.4 竞赛实战中的调试与优化技巧

1. 画表法：对于线性DP，在纸上画出dp数组，手动模拟前几步的计算过程。这是验证状态转移方程和初始化是否正确的最直观方法。对于“打家劫舍”，你可以列一个表格，分别写出nums[i]、dp[i]以及每次计算max(dp[i-1], dp[i-2]+nums[i])的过程。
2. 打印中间状态：在代码中关键步骤后打印dp数组，与你的手动推算结果对比。这是线上调试无法替代的本地调试手段。
3. 空间优化：像“打家劫舍”一样，观察状态转移方程是否只依赖于有限的几个前驱状态。如果是，就用滚动变量（如prev2,prev1,curr）替代数组。
4. 记忆化搜索：对于树形DP或难以确定遍历顺序的DP，可以先用“记忆化搜索”（递归+缓存）的方式实现，思路更直观，然后再尝试转化为递推（迭代）形式。rob_iii的解法就是典型的记忆化搜索思想。
5. 注意数据范围与初始化：蓝桥杯的题目经常会设置边界条件陷阱。比如数组为空、长度为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，最终会成为你手中最有力的武器之一。