动态规划这四个字很多初学算法的朋友一看就头大。要是只挑一道题来打破这种恐惧我会选“大盗阿福”。这道题几乎出现在所有入门教材的动态规划章节里讲的是有个叫阿福的角色面前有一排房子每间屋子放着不同数量的现金但他不能同时偷相邻的两家否则会触发警报问他最多能拿走多少钱。题面很有故事感剥掉外壳后却是一个特别纯正的动态规划模型在一维序列上做互不冲突的选择让收益最大化。它适合刚接触DP的大学生、准备竞赛的选手也适合所有觉得“状态转移方程是玄学”的自学者。把这一道题嚼透后面再看背包问题、区间DP、树形DP会发现核心套路都是同一套东西。这个题我会从题意开始讲然后拆开状态定义、转移方程、边界条件、空间优化、常见坑点和若干变形全程配上能直接复制运行的代码还有手把手的手算表。你先别急着看代码我们先把模型搞清楚。1. 先把题读明白大盗阿福到底在要你算什么1.1 题目背景与约束条件原题的设定大致是这样阿福来到一排房子前总共有 n 间屋子第 i 间屋子里放着 a[i] 块钱。他计划潜入其中的若干间但有个硬性限制——不能同时偷相邻的两家因为相邻的两家一旦同时失窃报警系统就会被触发。现在要你计算一个最优方案让阿福偷到的总金额最大。这里要提醒一句真实世界里入室盗窃当然违法我们聊的只是算法题抽象出来的那个“阿福”。他的任务本质上是替我们练熟一种建模能力在给定候选集合里做出一些互相冲突的选择并求出最优收益。把“偷钱”替换成“选物品”“排工位”“抢会议室”逻辑完全不变。常见的输入格式是第一行一个整数 T 表示测试组数每组先给 n再给 n 个数表示 a[1] 到 a[n]。n 一般能到 10^5 的量级所以暴力枚举 2^n 种方案肯定不行必须用多项式时间算法。1.2 为什么这道题是DP入门首选我见过很多同学第一次接触DP是从背包问题入手的结果被二维表格劝退了也有人从区间DP入手直接被状态转移绕晕。相比之下“大盗阿福”有四个很适合当第一课的特征首先是结构足够简单。所有房子排成一条线只有一个位置维度不需要建图不需要排序不需要处理复杂的依赖关系。其次是决策只有两个——偷或者不偷这样转移方程非常容易写适合用来理解“决策分类”这个核心动作。第三是重叠子问题异常明显每一步的最优解都建立在前几步的结果上天然能看出DP消除重复计算的威力。最后是它有一个很强的直觉陷阱看起来能用贪心解决但实际上不能所以它能帮你区分“贪心”和“动态规划”的边界这个价值非常大。很多教材把这道题当作线性DP的“hello world”不是没道理的。你如果能独立把这道题的完整思考过程走一遍就相当于拿到了学习一切DP问题的通用方法定义状态写出转移确定边界然后递推。2. 从“最后一家”倒着想状态定义与转移方程2.1 状态定义dp[i] 到底在记什么动笔写代码之前必须先回答一个问题我们要用一个数组记录什么信息很多新手卡在这一步不是不会写代码而是不知道 dp 数组每个格子应该代表什么含义。在“大盗阿福”这个题里一个很自然的选择是dp[i] 表示考虑前 i 户人家时能偷到的最大金额。注意措辞是“前 i 户”不是“偷到第 i 户”。这个区别很重要。“前 i 户”意味着你拥有完整的选择权可以偷第 i 户也可以不偷第 i 户dp[i] 记的是这 i 户范围内的最优解。如果用“偷到第 i 户”来定义那你就必须强制偷第 i 户反而不符合问题的原始要求。我习惯用“从第一户一直处理到第 i 户最终的最佳结果”来形容 dp[i]。当你把 i 从 1 推到 n最后的 dp[n] 自然就是全局答案。这个定义的巧妙之处在于它把一个大规模问题压缩成一串结构相同的小问题每个小问题都可以从前面的小问题推导出来。2.2 转移方程两个决策取一个max有了状态定义下一步就是思考dp[i] 怎么由比它更小的状态算出来这里有一个非常关键的思维方式——从最后一家倒着想。假设我已经处理完前 i-1 户现在站在第 i 户门口面前只有两个选择。第一个选择是不偷第 i 户。那第 i-1 户偷不偷都无所谓反正第 i 户不参与问题直接退化成“前 i-1 户的最优解”也就是 dp[i-1]。第二个选择是偷第 i 户。那么第 i-1 户就必须放弃否则相邻报警。于是收益由两部分组成第 i 户自己的钱 a[i]再加上“前 i-2 户的最优解” dp[i-2]。这里为什么用 dp[i-2] 而不是 dp[i-1]因为第 i-1 户已经被强制牺牲掉了我们只能从前 i-2 户里继续做选择。两个选择都算出来后取较大的那个作为 dp[i]dp[i] max(dp[i-1], dp[i-2] a[i])这个方程就是整道题的核心。你仔细品一下它其实在做一件很聪明的事把所有可能的“当前状态”收敛成两种路线然后把两种路线的收益进行比较把赢家记录下来。之后无论问题规模怎么扩大每增加一户都只是在重复这个比较过程。可能有人会问如果前 i-2 户的最优解里已经偷了第 i-2 户那我再偷第 i 户中间还隔着第 i-1 户算不算相邻不算因为 i-2 户和 i 户之间隔着 i-1 户物理上并不相邻所以不会触发报警。这也是为什么转移方程里可以放心地把 dp[i-2] 加上 a[i]。2.3 边界先行没有地基的递推会塌动态规划最忌讳的事情就是遞推关系想清楚了却忘记给递推一个起点。你可以把转移方程想象成盖楼房方程是每一层楼的结构但一楼下面是地基没有地基整个楼都是悬空的。在这道题里边界条件有两项dp[0] 0前 0 户人家当然一分钱也偷不到。dp[1] a[1]只有一户人家时最优方案就是偷这一户。有了这两个边界i 2 时就能正常套用转移方程因为 dp[2] 需要 dp[1] 和 dp[0]再往后每步都有基础。如果你用下标从 0 开始的写法也就是把房子的编号定义为 0 到 n-1那么 dp[1] 对应的意义要小心。我个人的习惯是读入数据时直接把 a 的下标从 1 开始也就是开一个长度为 n1 的数组a[1] 存第一户的钱。这样 dp[1] a[1]dp[0] 0代码和思路一一对应不容易乱。2.4 手算一遍比看十遍题解都管用纸上得来终觉浅我强烈建议你拿到任何一道DP题都先手动跑一个例子。这里我们用一个具体数据来完整推一遍假设 a [3, 1, 6, 2, 9]。初始时 dp[0] 0dp[1] 3。然后从 i 2 一路算到 i 5ia[i]计算过程dp[i]00边界初始值013只有一户直接偷321max(dp[1]3, dp[0]a[2]1)336max(dp[2]3, dp[1]a[3]9)942max(dp[3]9, dp[2]a[4]5)959max(dp[4]9, dp[3]a[5]18)18最终答案是 18对应的方案是偷第 1 户的 3、第 3 户的 6、第 5 户的 9一共 18。你看中间隔着第 2 户和第 4 户完全不违反相邻限制。手算这一步能帮你建立“信任感”——原来这个递推式子真的能推出正确结果。更重要的是当你代码写错时你可以用同样的数据去调试程序亲眼看到 dp 数组哪一位和手算不符就能很快定位问题。3. 写代码从朴素数组到滚动数组优化3.1 C 基础版按部就班递推如果把上面这些思路翻译成 C最直接的写法是这样#include bits/stdc.h using namespace std; const int N 100005; int a[N], dp[N]; int main() { int T; cin T; while (T--) { int n; cin n; for (int i 1; i n; i) { cin a[i]; } dp[0] 0; if (n 1) dp[1] a[1]; for (int i 2; i n; i) { dp[i] max(dp[i - 1], dp[i - 2] a[i]); } cout dp[n] endl; } return 0; }这段代码的时间复杂度是 O(n)因为从 1 到 n 每个位置只算一次空间复杂度是 O(n)因为开了一个和 a 等长的 dp 数组。对于一个 10^5 的数据量来说绰绰有余。有一点要注意dp[0] 在每组数据里都要被重新赋值为 0。如果写在全局数组里上一组数据可能把它改过所以循环里每次都得重置。3.2 Python 实现与记忆化搜索对照Python 版本写起来更接近咱们刚才的思路def solve(): n int(input()) a [0] list(map(int, input().split())) if n 0: return 0 dp [0] * (n 1) dp[1] a[1] for i in range(2, n 1): dp[i] max(dp[i - 1], dp[i - 2] a[i]) return dp[n]如果你更习惯自顶向下的思考方式也可以改成记忆化搜索。道理是一样的用一个 memo 数组记录已经算过的 dp[i]避免重复计算。def solve(): n int(input()) a [0] list(map(int, input().split())) memo [-1] * (n 1) def dfs(i): if i 0: return 0 if memo[i] ! -1: return memo[i] # 不偷第i户 vs 偷第i户 memo[i] max(dfs(i - 1), dfs(i - 2) a[i]) return memo[i] return dfs(n)两种写法本质相同递推版更接近“从边界往上盖楼”的感觉记忆化搜索更接近“从目标向下拆问题”。我建议都写一遍能帮你理清动态规划的两个方向。3.3 滚动数组把空间压到 O(1)再看一下转移方程dp[i] max(dp[i-1], dp[i-2] a[i])你会发现计算 dp[i] 的时候只用了它前面两个状态 dp[i-1] 和 dp[i-2]。换句话说dp[0] 到 dp[i-3] 这些早就算完的数据之后再也没有机会用到。既然如此为什么要开一整个数组把它们存着完全可以用两个变量滚动前进。想象你手里只拿两张卡片一张写着“前 i-2 户的最优值”一张写着“前 i-1 户的最优值”。每处理一户新房子就用这两张卡片算出新卡片然后把手里的旧卡片丢掉一张把新卡片补上。这就是滚动数组。int solve(vectorint a, int n) { int f0 0; // dp[i-2] int f1 a[1]; // dp[i-1] for (int i 2; i n; i) { int cur max(f1, f0 a[i]); f0 f1; f1 cur; } return f1; }在 Python 里也一样def solve(): n int(input()) a [0] list(map(int, input().split())) if n 0: return 0 f0, f1 0, a[1] for i in range(2, n 1): f0, f1 f1, max(f1, f0 a[i]) return f1这里每一步更新是同步进行的新的 f0 是旧的 f1新的 f1 是本次算出来的最优值。如果你写成f1 max(f1, f0 a[i])然后再去更新 f0顺序就乱了算出来的结果会出错。这是我见过最普遍的滚动数组写错方式。3.4 复杂度分析与选型建议把两种写法放在一起对比写法时间复杂度空间复杂度适用场景朴素递推数组O(n)O(n)调试直观后续可能要输出方案滚动数组O(n)O(1)n 特别大时卡空间记忆化搜索O(n)O(n)理解自顶向下思路递归深度受限制对于普通的竞赛题或面试题开数组和滚动数组都能过所以不必为了炫技一上来就写滚动数组。我个人的学习顺序是先写朴素版保证逻辑正确再优化成滚动数组感受一下空间到底省在哪里。如果哪一天遇到 n 是 10^7 甚至更大内存只给几十 MB 的情况滚动数组就是你最后的救星。4. 常见问题与排查实录4.1 下标配错最容易翻车的三个细节第一类问题是下标从 0 开始还是从 1 开始。很多人读入时用 0-based 习惯写转移时又下意识用dp[i-2]结果 i1 时出现 dp[-1]直接越界。统一使用 1-based 下标可以完全避开这个问题。第二类问题是 dp[1] 忘记初始化导致第一户的钱根本没被考虑最后结果比正确答案少。第三类问题是转移方程里的 a[i] 和下标的对应错位如果你 dp 从 1 开始但 a 数组从 0 开始那么 dp[i-2]a[i] 里的 a[i] 其实取的是下一户的钱全盘皆错。最有效的排查方式是每次写完代码拿题目的样例手动走一遍在代码里打印出每个 dp[i]和手算表对照。如果某位不一致马上就能看出是下标问题还是初始化问题。4.2 边界样例自测清单写DP题最怕的不是正常数据出错而是边界数据出错。我习惯用下面这组自测用例来检查代码输入期望输出检验点n00空序列是否安全n1, a[5]5只有一户时能否正确处理n2, a[5,10]10只取价值较大的那户n3, a[10,5,10]20取两头隔一户的组合n3, a[3,5,3]6贪心会错的两个同值边界如果题目明确保证 n 1n0 的自测可以跳过但自己写通用函数时处理 n0 能避免很多意外。特别注意n3, a[10,5,10]这种情况它检验的是“看起来应该取中间的5但实际两头都是10加起来20更大”——正是这一类的比较让DP区别于简单贪心。4.3 贪心错得多离谱一个经典反例每次讲这个题都会有同学跳出来说这题不是很简单吗我每次都挑当前能偷的最大金额偷完把邻居删掉再重复不就行了这个想法听起来头头是道但一个反例就能击穿它。考虑三户人家的金额是 [3, 5, 3]。按“先偷最大户”的贪心逻辑第一轮钱最多的是中间的 5偷完之后左右两个 3 因为是邻居都不能偷了总收益 5。但正确答案是偷两边的 3 和 3总收益 6。中间那户虽然单看金额最大但偷它会“挤掉”两个邻居两边的户单看都不如它加在一起却更大。贪心是近视眼它只看单独一家的局部利益不会组合比较。DP 不一样每一步都把“不偷”和“偷”两种路线的总收益算出来再比较所以不会被这种陷阱坑到。还有一种错误直觉是按奇偶位置把所有户分成两组哪组金额大就偷哪组。比如 [5, 1, 1, 5, 1]奇数位置和是 5117偶数位置和是 156按这个策略会选奇数位置但最优方案其实是第1户的 5 加上第4户的5一共10。这个反例说明任何形式的局部固定规则都无法覆盖所有情况只有状态之间的逐步比较才是通用解法。4.4 多组数据的坑别忘了重新初始化原题经常带有 T 组测试数据。这时最容易踩的坑是全局 dp 数组在上一组数据算完后残留旧值而新一组的 n 比较小循环没有覆盖到旧数据。尽管你的转移方程只依赖 dp[i-1] 和 dp[i-2]理论上旧数据影响不到这次计算但如果有一户刚好因为某些原因没有被赋值残留值就会悄悄混进去。稳妥的写法是每组数据开始前把 dp[0] 和 dp[1] 重新赋值循环中每个 dp[i] 都会被覆盖到所以不需要清空整个数组。如果你图省事用滚动数组就更不用担心这个问题了因为 f0 和 f1 每轮都会重新初始化。5. 从一条街到一座花园经典变形与进阶方向5.1 环形街道首尾相连怎么破如果把阿福面对的街道改成环形也就是第1户和第 n 户变成了邻居问题就会多一个新约束你不能同时偷第1户和第 n 户。这就是经典的“打家劫舍 II”式变形很多在线测评平台都有收录。解决办法非常优雅——把环形拆成两个线性问题。第一个子问题不偷第1户那么第2户到第 n 户完全不受环形约束可以作为普通的线性街道来求解。第二个子问题不偷第 n 户那么第1户到第 n-1 户同样变成线性街道。最终答案取这两个子问题的较大值。为什么这样是对的因为任何一个合法方案要么没有偷第1户要么没有偷第n户否则两者同时被偷就违法了所以它一定会落在两个子问题中的至少一个里面。可能会有同学问如果有一个方案首尾都不偷它是不是被漏掉了不会因为它同时满足两个子问题的约束在求每个子问题时DP 都有机会不选端点自然包含首尾都不偷的情况。这里要注意特判n1 时两个子问题的区间都会变成空或只有一个点需要单独处理。我自己的实现习惯是封装一个函数 solve_no_cycle(l, r)专门求 a[l..r] 上的线性答案然后ans max(solve(1, n-1), solve(2, n))。5.2 树形版本大盗阿福与树上DP初探如果房子不再排成一条街而是布置成一个树形结构某个节点和它的直接子节点算“相邻”偷了父节点就不能偷它的直接子节点那么问题就从一维递推升级成树形DP。这时需要给每个节点记两个状态dp[u][0]以 u 为根的子树中不偷 u 时的最大收益dp[u][1]以 u 为根的子树中偷 u 时的最大收益。转移也很自然。如果偷 u那么所有直接孩子都不能偷所以 dp[u][1] a[u] sum(dp[v][0])其中 v 遍历 u 的每个孩子。如果不偷 u每个孩子都可以自由选择偷或不偷所以 dp[u][0] sum(max(dp[v][0], dp[v][1]))。最后用一次 DFS 从叶子往上合并根节点的两个状态取最大值就是答案。这个变形很好地展示了动态规划从“位置维度”扩展到“树结构维度”的思路。5.3 进阶方向加维度、输出方案、矩阵加速当你完全掌握了基础版本还可以往几个方向继续扩展。第一个方向是加限制条件。比如阿福最多只能偷 k 户那么状态就要增加一个维度dp[i][j] 表示前 i 户里恰好偷了 j 户的最大收益。转移时要额外判断 j 的取值本质上还是“偷不偷第 i 户”的决策分类。第二个方向是输出具体方案。只求最大金额时我们不用记录决策来源但如果题目要求输出偷了哪几户就需要另一个数组 prev[i] 记录 dp[i] 到底是由 dp[i-1] 推出来的还是由 dp[i-2] a[i] 推出来的。最后从 n 往前回溯一步步还原整个选择路径。需要注意的是当 dp[i-1] 等于 dp[i-2] a[i] 时选择哪条路径会影响输出的方案这时候要看题目是否需要字典序之类的要求。第三个方向是数据规模再扩大。如果 n 大到 10^18而且金额序列具有某种重复模式可以考虑用矩阵快速幂优化转移过程因为同一组转移方程会被循环使用。这个属于竞赛进阶内容现阶段了解一下“DP 还能和矩阵结合”就够了。另外补充一个关于输出方案时的小技巧我习惯在 dp 数组之外另开一个choice数组choice[i] 0表示不偷第 i 户choice[i] 1表示偷。回溯时从 n 开始如果 choice[i] 1就在方案里加入 i然后跳到 i-2否则跳到 i-1。用这个方式能很轻松地把一维线性DP的路径打印出来。最后说点我自己的体会。这个题我前前后后讲过很多遍每次有人卡住都不是卡在“看不懂题”上而是卡在“不敢定义状态”。一想到要从 2^n 种方案里找最优就下意识觉得需要什么高级技巧其实只要你试着把 dp[i] 定义为前 i 户的最优解转移方程十五分钟就能推出来。我强烈建议拿到任何一道线性DP都先自己在草稿纸上写三样东西状态是什么、转移是什么、边界是什么。写不出来就找更小的问题练手比如这道阿福。把它彻底吃透后面不管是背包问题、区间DP还是树形DP你会发现它们归根到底还是那三板斧状态、转移、边界。