1. 项目概述从一道“画廊”题看动态规划的实战拆解最近在刷题社区里看到不少朋友在讨论一道名为“画廊”的题目标签是动态规划。这让我想起了自己初学DP时面对各种状态定义和转移方程的手足无措。动态规划这个听起来高大上的算法思想其实核心就是“聪明的穷举”加上“记忆化”避免重复计算。而“画廊”这道题恰好是一个绝佳的DP入门实战案例它不像背包问题那样模板化也不像最长公共子序列那样经典它需要你根据实际问题自己定义状态设计转移非常锻炼思维。今天我就结合这道题把我自己的解题笔记和踩过的坑梳理一遍希望能帮你打通DP的任督二脉。无论你是正在备战面试还是单纯想提升算法能力这篇笔记都会从最朴素的思路开始一步步带你走到最优解并分享那些只有自己踩过坑才知道的调试技巧和优化心得。2. 问题解析与状态定义画廊里到底在画什么2.1 问题场景还原与抽象首先我们得把题目描述清楚。一个典型的“画廊”问题可能是这样的有一条长长的走廊画廊走廊两侧的墙上各有若干个画框或者需要放置艺术品的位置。每个画框可以选择挂一幅画或者不挂。但是画廊有审美要求不能有连续三个或者K个画框是空的或者连续挂画具体看题目约束。我们的目标是在满足这个审美约束下计算一共有多少种不同的布置方案。这只是一个示例场景实际题目可能会有变体比如两侧的画框数量可能不同约束条件可能更复杂例如左右两侧的空白还有关联。但万变不离其宗核心是我们有一系列的位置画框每个位置有几种状态挂画/不挂画并且状态之间存在某种限制不能连续出现某个模式求满足限制的所有状态序列的数量。这类问题天然就是动态规划的菜。为什么因为当我们考虑第i个位置的方案数时它只依赖于前面有限个位置的状态比如前两个位置是否空置而不是依赖于整个序列。这种“无后效性”和“最优子结构”正是DP发挥威力的地方。2.2 状态定义的“第一性原理”DP最难也最关键的一步就是定义状态。定义不好要么方程复杂无比要么根本推不出来。我的经验是从问题的约束条件入手。以“不能有连续三个画框为空”为例。约束关注的是“连续的空画框”数量。那么要判断在第i个位置做决策时是否合法我必须知道以第i-1个位置结尾时已经连续空了几个画框。因此一个最直接的状态定义呼之欲出dp[i][j]表示考虑前i个画框并且以第i个画框结尾时末尾连续空画框的数量为j的方案总数。这里j的取值范围是0, 1, 2。因为如果连续空了3个j3就已经非法了我们不需要记录这个状态。但是等等第i个画框本身有两种选择挂画记为状态F或者空着记为状态E。如果第i个画框挂画F那么无论前面是什么连续空画框的计数都会被重置为0。因为挂画打断了“空”的连续性。如果第i个画框空着E那么连续空画框的计数就是前一个状态连续空的数量 1当然不能超过2本题约束。所以我们的状态dp[i][j]实际上隐含了第i个位置的状态。更清晰的定义是dp[i][j]表示考虑前i个画框且第i个画框的状态导致了末尾连续空画框数为j的方案数。 但这样还是有点绕。一个更常见、更清晰的定义方式是使用状态机DP。状态机定义 我们可以定义三个状态分别表示以当前位置结尾时末尾连续空画框的数量。状态0 (dp[i][0])第i个位置挂画。此时连续空画框数为0。状态1 (dp[i][1])第i个位置空着且这是连续的第1个空画框即第i-1个位置挂画了。状态2 (dp[i][2])第i个位置空着且这是连续的第2个空画框即第i-1个位置也是空的。为什么没有状态3因为题目不允许连续3个空所以当连续空画框数达到2时下一个位置绝对不能是空必须挂画。因此我们只需要记录到2。注意这里的状态定义是DP的精髓。很多新手会试图用dp[i]直接表示前i个位置的方案总数但这样无法体现“连续空”这个约束信息量不够无法写出转移方程。必须把约束条件“编码”到状态里。2.3 初始状态的思考确定了状态就要考虑起点。对于第一个画框i1它可以挂画对应状态0dp[1][0] 1。它可以空着对应状态1因为前面没有画框空着就是第一个空dp[1][1] 1。它不可能处于状态2连续两个空所以dp[1][2] 0。这样我们的DP数组就可以从i2开始递推了。3. 状态转移方程推导与优化3.1 画出状态转移图根据定义我们可以像设计一个有限状态自动机一样画出状态之间的转移关系。这能极大帮助理清思路。从状态0 (当前挂画) 出发下一个位置可以挂画 - 进入新的状态0。挂画后连续空重置为0下一个位置可以空着 - 进入状态1。空了一个从状态1 (当前空且是第一个空) 出发下一个位置可以挂画 - 进入状态0。挂画打断连续性下一个位置可以空着 - 进入状态2。空了第二个从状态2 (当前空且是连续第二个空) 出发下一个位置必须挂画 - 进入状态0。否则就连续三个空了非法下一个位置不能空着。3.2 写出转移方程用数学语言描述上面的转移图假设我们要求前i个画框的方案现在已知i-1的所有状态dp[i][0]第i位挂画第i位挂画时前一位(i-1)可以是任何状态因为挂画总是合法的。从dp[i-1][0]来前一位挂画这一位也挂画。从dp[i-1][1]来前一位是第一个空这一位挂画。从dp[i-1][2]来前一位是第二个空这一位必须挂画。所以dp[i][0] dp[i-1][0] dp[i-1][1] dp[i-1][2]dp[i][1]第i位空且是第一个空这意味着第i位空着但第i-1位必须挂画否则就是连续空了。只能从dp[i-1][0]来前一位挂画这一位选择空。所以dp[i][1] dp[i-1][0]dp[i][2]第i位空且是连续第二个空这意味着第i位空着且第i-1位也是空的即处于状态1。只能从dp[i-1][1]来前一位是第一个空这一位继续空。所以dp[i][2] dp[i-1][1]3.3 初始化与最终答案根据3.1节的初始状态dp[1][0] 1,dp[1][1] 1,dp[1][2] 0假设画廊有N个画框。那么考虑完所有N个画框后最终合法的方案是第N个画框处于任何合法状态的方案总和。因为我们的状态定义已经保证了过程的合法性。 所以最终答案ans dp[N][0] dp[N][1] dp[N][2]实操心得在推导方程时一定要反复问自己“要达到目标状态前一个状态必须满足什么条件” 比如dp[i][1]要求“第i位空且是第一个空”那么第i-1位必须不空也就是必须挂画对应状态0。这样思考能确保转移的正确性。3.4 空间优化滚动数组观察转移方程dp[i][0]依赖于dp[i-1][0], dp[i-1][1], dp[i-1][2]dp[i][1]依赖于dp[i-1][0]dp[i][2]依赖于dp[i-1][1]我们发现计算第i层状态只需要第i-1层状态。因此我们完全不需要一个N x 3的二维数组只需要两个长度为3的数组或者用几个变量来回倒腾就行。这是DP常见的空间优化技巧——滚动数组。具体实现时我们可以只用三个变量来表示前一层的三个状态pre0, pre1, pre2。 然后计算当前层的cur0, cur1, cur2cur0 pre0 pre1 pre2 cur1 pre0 cur2 pre1计算完后把(cur0, cur1, cur2)赋值给(pre0, pre1, pre2)用于下一轮计算。 初始化时pre0, pre1, pre2 1, 1, 0(对应i1的情况)。这样空间复杂度就从O(N)降到了O(1)。对于N很大的情况比如上亿这个优化至关重要。4. 代码实现与调试实录4.1 基础版本代码Python我们先实现一个最直观的二维DP版本便于理解。def gallery_arrangements(N): 计算长度为N的画廊禁止连续三个画框为空有多少种布置方案。 if N 0: return 0 # dp[i][j], i从1开始计数这里我们开N1行方便对齐 dp [[0] * 3 for _ in range(N 1)] # 初始化 i1 dp[1][0] 1 # 挂画 dp[1][1] 1 # 空第一个空 dp[1][2] 0 # 不可能有两个空 for i in range(2, N 1): # 状态转移 dp[i][0] dp[i-1][0] dp[i-1][1] dp[i-1][2] # 当前挂画 dp[i][1] dp[i-1][0] # 当前空且是第一个空 dp[i][2] dp[i-1][1] # 当前空且是第二个空 # 最终答案第N个位置处于任何合法状态的方案总和 return dp[N][0] dp[N][1] dp[N][2] # 测试 print(gallery_arrangements(1)) # 输出2 (挂 or 空) print(gallery_arrangements(2)) # 输出? 我们可以手算验证 print(gallery_arrangements(5)) # 输出?4.2 空间优化版本代码def gallery_arrangements_opt(N): if N 0: return 0 if N 1: return 2 # 直接返回基础情况 # 初始化代表 i1 时的状态 pre0, pre1, pre2 1, 1, 0 for i in range(2, N 1): cur0 pre0 pre1 pre2 cur1 pre0 cur2 pre1 # 滚动到下一轮 pre0, pre1, pre2 cur0, cur1, cur2 return pre0 pre1 pre24.3 调试与验证从小数据开始DP代码写完后最怕的就是转移方程推错了。最好的调试方法就是从小数据开始手动模拟对比输出。N1方案有 {挂}, {空}。共2种。程序输出2正确。N2我们手动枚举一下所有合法方案记F为挂画E为空FFFEEFEE? 注意EE是连续两个空是允许的因为约束是禁止连续三个空。 所以N2时所有4种方案都合法。程序应该输出4。运行gallery_arrangements(2)得到4正确。N3手动枚举有点麻烦了但我们可以用DP思想手算i1: (0:1, 1:1, 2:0)i2:dp[2][0] 1102(对应FF, EF)dp[2][1] dp[1][0]1(对应FE)dp[2][2] dp[1][1]1(对应EE)i3:dp[3][0] dp[2][0]dp[2][1]dp[2][2] 2114dp[3][1] dp[2][0] 2dp[3][2] dp[2][1] 1总方案 421 7。我们验证一下N3时非法方案只有一种EEE。总共有2^38种可能减去1种非法得到7种。完美匹配。通过这样验证前几个小数据基本可以确定DP方程的正确性。踩坑记录我第一次写的时候在初始化dp[1][2]时顺手写了0但没仔细想。后来测试N2时发现结果不对才回头检查。对于边界情况一定要结合定义反复推敲。dp[1][2]表示“第一个画框空且是连续第二个空”这显然不可能所以是0。这个“显然”的步骤最容易出错。5. 问题变体与扩展思考“画廊”问题只是一个引子DP的魅力在于它能解决一大类具有相似结构的问题。掌握了这个模型你可以轻松应对许多变体。5.1 变体一约束条件变化问题如果约束变成“不能有连续两个画框为空”怎么办分析此时状态“连续两个空”就是非法的了。我们的状态只需要状态0当前挂画。状态1当前空且是第一个空即前一位挂画。 状态2不需要了因为一旦出现连续两个空就非法。转移方程dp[i][0] dp[i-1][0] dp[i-1][1]当前挂画前一位任意dp[i][1] dp[i-1][0]当前空前一位必须挂画 初始化dp[1][0]1, dp[1][1]1。 答案dp[N][0] dp[N][1]。你可以验证N3时非法方案是EE?和?EE具体有EEF, FEE, EEE。总方案8-35。用这个DP算出来也是5。5.2 变体二两侧画廊问题问题画廊两侧都有画框左侧有L个右侧有R个。约束可能是同一侧不能连续K个空或者左右两侧对应位置不能同时空等等。分析状态维度需要增加。例如我们可以定义dp[i][j][a][b]表示处理到第i个位置可能需要一个顺序遍历两侧左侧最后一个状态为a右侧最后一个状态为b且连续空的情况为j这里j可能需要更复杂编码。这变成了一个多维DP本质思路不变但状态设计和转移会更复杂。这常用于竞赛中的“状压DP”结合。5.3 变体三求具体方案而不仅是数量问题如果要求输出所有具体的布置方案而不仅仅是数量。分析DP通常用于计数或求最优值。要求所有具体方案一般需要结合回溯Backtracking。我们可以用DP先计算出每个状态下的方案数然后从最终状态倒推根据转移方程和方案数递归地构造出所有路径。这通常比纯暴力回溯高效因为DP表帮助我们快速判断某条分支下是否真的存在合法方案可以进行剪枝。5.4 与经典DP模型的联系“画廊”问题本质上是一个线性DP并且带有状态机特征。它和以下经典问题神似股票买卖问题带有冷冻期状态表示“持有股票”、“不持有股票且在冷冻期”、“不持有股票且不在冷冻期”。打家劫舍问题状态表示“偷当前家”和“不偷当前家”并且有“不能连续偷”的约束。解码方法问题数字字符串解码成字母当前字符可以单独解码也可以和前一个字符组合解码状态就是“以单独解码结尾”和“以组合解码结尾”。它们的共同点是当前决策受到前面有限步决策的影响并且这种影响可以被几个有限的状态所概括。识别出这个模式你就掌握了解决一大片DP问题的钥匙。6. 常见错误与排查技巧6.1 初始化错误这是最常见的错误之一。一定要把i1或i0看你的下标习惯的所有状态根据定义一个一个手动赋值不要想当然。比如在“画廊”题中dp[1][2]第一个位置就是连续第二个空明显为0但如果你漏了或者写成1后面全错。排查技巧打印出DP表的前几行与手动计算的结果对比。对于线性DP前3-5行的值很容易手算验证。6.2 转移方程遗漏或错误推导方程时容易遗漏某些转移路径或者搞错转移条件。例如在dp[i][0]的转移中是否包含了所有可能的前置状态排查技巧画状态转移图用纸笔画出来箭头标上转移条件一目了然。口语化检查对着方程念出来。“要让我第i个位置挂画状态0那么第i-1个位置可以是什么情况可以是挂画状态0可以是第一个空状态1也可以是第二个空状态2。好这三种情况都加上了吗” 这种自问自答非常有效。小数据测试如前所述用N1,2,3去测试对比暴力枚举的结果。6.3 模运算下的陷阱很多题目要求结果对某个大数如1e97取模。这时要注意加法、乘法运算后及时取模防止溢出。初始化时也要取模虽然初始值很小但养成好习惯。在滚动数组优化时确保用于计算当前值的“前一轮状态”是已经取过模的。6.4 索引越界在循环中如果状态转移用到了dp[i-2]甚至更早的状态要确保i从足够大的值开始循环并对i1等边界情况单独处理。通用调试流程静心读题至少读三遍用笔划出关键约束“连续K个空”。定义状态问自己为了判断下一个决策是否合法最少需要知道前面哪些信息把这些信息组合成状态。写出方程基于状态定义枚举当前状态的所有可能来源。确定初值考虑第一个元素或前几个元素所有可能的状态取值。小数据验证用N1,2,3手动计算DP表并与程序输出对比。如果不符回到步骤2-4检查。大数据测试如果可能写一个暴力搜索函数DFS用于小范围N10或15验证确保DP结果与暴力结果完全一致。这是最可靠的验证方法。DP就像搭积木状态是积木块转移方程是拼接规则。一块没放对整个模型就垮了。耐心和细致的推导是解开所有DP问题的唯一捷径。这道“画廊”题就是一个完美的起点。下次遇到类似的“连续约束”问题不妨先想想我们需要用几个状态来描述这个“连续”的进度。