动态规划核心思想与国赛四大模型：从暴力枚举到状态转移

1. 从“暴力枚举”到“状态转移”动态规划的核心思想如果你正在备战蓝桥杯国赛并且已经刷到“动态规划专题”这个阶段那说明你已经跨过了基础语法和简单算法的门槛开始接触算法竞赛中真正的“硬骨头”了。动态规划Dynamic Programming, DP是国赛乃至所有算法竞赛中区分度最高的知识点之一它不像排序、查找那样有固定的模板更像是一种解决问题的“思想”或“方法论”。很多同学在初次接触时会觉得它既神秘又困难状态、转移方程、初始化这些概念让人头大。但我想告诉你动态规划的本质其实是一种“聪明的暴力”——它通过记录并复用子问题的解避免了大量重复计算从而将原本指数级的时间复杂度优化到多项式级别。我们从一个最经典的例子开始斐波那契数列。如果让你写一个函数fib(n)来计算第n项最直观的想法是递归fib(n) fib(n-1) fib(n-2)。这个思路完全正确但效率极其低下。因为计算fib(5)需要计算fib(4)和fib(3)而计算fib(4)又要计算fib(3)和fib(2)……你会发现fib(3)被计算了无数次。这种重复计算就是暴力递归的致命伤。动态规划的做法是我们开一个数组dpdp[i]表示fib(i)的值。我们先手动算出dp[0]0,dp[1]1然后就可以用循环递推dp[i] dp[i-1] dp[i-2]。这样每个fib(i)只计算一次时间复杂度从指数级的 O(2^n) 降到了线性的 O(n)。这个数组dp就是我们所说的“状态”而dp[i] dp[i-1] dp[i-2]就是“状态转移方程”。所以动态规划的核心思想可以概括为将原问题分解为相对简单的子问题通过解决并保存子问题的解记忆化来高效地解决原问题。备战国赛你需要训练的正是这种“定义状态”和“寻找转移”的思维能力。接下来我将结合蓝桥杯国赛的考察特点从基础模型到高级技巧为你梳理出一条清晰的动态规划进阶路径。2. 国赛动态规划四大基础模型与解题框架在深入复杂问题前必须牢牢掌握几个基础模型。它们是构成所有复杂DP问题的“积木”。国赛题目往往不会直接考裸题但一定会考察你对这些模型本质的理解和灵活运用。2.1 线性DP最长上升子序列LIS的两种视角线性DP是指状态沿着一个维度通常是序列下标线性推进的DP问题。最长上升子序列Longest Increasing Subsequence, LIS是其代表。1. 经典O(n²)解法定义状态与转移最直接的想法是定义dp[i]为以第i个数字结尾的最长上升子序列的长度。那么要计算dp[i]我们需要看前面所有比nums[i]小的数字nums[j] (j i)dp[i]就等于所有满足条件的dp[j] 1中的最大值。如果前面没有比它小的dp[i]就是1只包含自己。状态转移方程为dp[i] max(dp[j] 1) for all j i and nums[j] nums[i]初始化dp[0...n-1] 1。最终答案是所有dp[i]中的最大值。这个方法思路直观但时间复杂度是 O(n²)在数据规模较大如 n 10^4的国赛题中可能不够用。2. 贪心二分的O(n log n)优化重新理解“状态”这是国赛必须掌握的优化技巧。我们换一种状态定义设tails[k]表示长度为k1的所有上升子序列中结尾元素最小的那个值。这个数组是单调递增的为什么思考一下。我们遍历原数组对于每个数x如果x比tails中所有数都大就把它追加到后面子序列长度1。否则在tails中找到第一个大于等于x的数用x替换它。因为对于同样长度的上升子序列结尾元素越小未来“潜力”越大。 这个“查找”过程可以用二分查找完成因此总复杂度为 O(n log n)。这种方法的核心在于我们不再关心子序列具体是什么而是关注“某个长度下的最小结尾”这是一种更精炼的状态表示。在国赛中遇到“最长上升/不降子序列”且数据范围大的题目应首先想到此法。注意这个优化算法得到的是长度如果需要还原具体的子序列则需要额外的记录数组会稍微复杂一些。国赛有时会要求输出方案这点要留意。2.2 背包DP从01背包到多重背包的演变背包问题是动态规划的另一个基石核心是“选择”与“限制”。1. 01背包选与不选的哲学问题描述有N件物品和一个容量为V的背包。第i件物品的体积是v[i]价值是w[i]。每件物品只能选一次。求解将哪些物品装入背包可使价值总和最大。状态定义dp[i][j]表示考虑前i件物品在背包容量为j时能获得的最大价值。状态转移对于第i件物品我们有两种选择不选dp[i][j] dp[i-1][j]价值不变选前提是j v[i]dp[i][j] dp[i-1][j - v[i]] w[i]我们取两者的最大值dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])空间优化滚动数组观察转移方程dp[i]只依赖于dp[i-1]因此我们可以将二维数组压缩成一维数组dp[j]。但需要注意的是为了保证在计算dp[j]时用到的dp[j-v[i]]是上一轮i-1的状态我们必须逆序枚举容量j从V到v[i]。这是01背包空间优化的关键点必须理解透彻。2. 完全背包与多重背包完全背包每件物品可以选无限次。它与01背包的唯一区别在于状态转移时选择当前物品后仍然可以继续考虑当前物品。在一维优化下这体现为正序枚举容量j从v[i]到V。因为正序枚举允许我们在本轮中多次添加同一物品。多重背包第i件物品最多可以选s[i]次。最朴素的解法是将其视为01背包把每件物品拆分成s[i]个独立的物品但这样复杂度高。优化方法有二进制拆分和单调队列优化。二进制拆分是国赛常考点将数量s拆分成 1, 2, 4, ..., 2^k, c其中 c s - (2^{k1}-1)这样几个“物品包”每个包视为一个独立的01背包物品。因为任何不超过s的数都可以由这些包组合而成。这能将复杂度从 O(V * Σs) 降至 O(V * Σlog s)。2.3 区间DP枚举分割点的艺术区间DP用于解决涉及区间性质的问题例如合并石子、回文子序列等。状态通常定义为dp[i][j]表示区间[i, j]上的最优解。经典例题石子合并有N堆石子排成一排每次只能合并相邻的两堆合并的代价是两堆石子的重量之和。求将所有石子合并成一堆的最小总代价。状态定义dp[i][j]表示合并区间[i, j]内的所有石子所需的最小代价。状态转移我们考虑最后一次合并它一定是将[i, j]分成的左右两堆[i, k]和[k1, j]合并起来。因此我们需要枚举这个分割点k。dp[i][j] min(dp[i][k] dp[k1][j] sum[i][j]) for all k in [i, j-1]其中sum[i][j]是区间[i, j]的石子总重量可以用前缀和快速计算。遍历顺序由于计算大区间[i, j]需要用到所有比它短的区间所以我们通常按区间长度从小到大进行遍历。先算所有长度为1的区间dp[i][i] 0再算长度为2的依次类推。区间DP的代码通常呈现一个三层循环的结构外层循环区间长度len中层循环区间起点i内层循环分割点k。掌握这个模板是解决此类问题的第一步。2.4 树形DP后序遍历的思维当问题结构是一棵树如公司职级、城市道路时就需要树形DP。其核心是递归DFS和在回溯时进行状态转移。经典例题没有上司的舞会公司有一棵上下级关系树每个人有一个快乐值。直接上下级不能同时参加舞会求最大的快乐值之和。状态定义对于以节点u为根的子树我们定义两个状态dp[u][0]: u不参加时其子树能获得的最大快乐值。dp[u][1]: u参加时其子树能获得的最大快乐值。状态转移如果u不参加那么它的子节点v可以参加也可以不参加我们取最大值dp[u][0] Σ max(dp[v][0], dp[v][1])如果u参加那么它的所有子节点v都不能参加dp[u][1] happy[u] Σ dp[v][0]求解过程从根节点开始进行一次DFS后序遍历在从子节点回溯到父节点时根据上述方程更新父节点的dp值。最终答案就是max(dp[root][0], dp[root][1])。树形DP的关键在于把树“拍平”成线性序列的思维。通过DFS我们保证了在计算父节点状态时所有子节点的状态都已经计算完毕这正符合动态规划“无后效性”的要求。3. 进阶技巧状态机与状态压缩DP掌握了基础模型国赛的题目往往会在这些模型上增加“维度”其中“状态机”和“状态压缩”是两种最常用的增加维度、描述复杂决策过程的方法。3.1 状态机DP描述具有多个状态的决策过程状态机模型用于描述一个对象拥有多个状态并且在这些状态之间根据条件进行转移的过程。它让DP的状态定义更加清晰。经典例题股票买卖系列含冷冻期这是状态机DP的绝佳例子。以“含一天冷冻期”为例你不能在卖出股票后的第二天买入。 我们可以为每一天定义三个状态dp[i][0]: 第i天结束时持有股票的最大收益。dp[i][1]: 第i天结束时不持有股票且处于冷冻期即今天卖出了股票的最大收益。dp[i][2]: 第i天结束时不持有股票且不处于冷冻期的最大收益。状态转移图如下dp[i][0](今天持有) 可能来自昨天就持有dp[i-1][0]或者今天买入。今天买入的前提是昨天不持有且不在冷冻期即dp[i-1][2] - prices[i]。所以dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])。dp[i][1](今天卖出进入冷冻期) 只能来自昨天持有今天卖出。dp[i][1] dp[i-1][0] prices[i]。dp[i][2](今天空闲) 可能来自昨天就空闲dp[i-1][2]或者昨天是冷冻期今天解冻dp[i-1][1]。所以dp[i][2] max(dp[i-1][2], dp[i-1][1])。初始化dp[0][0] -prices[0](第一天买入)dp[0][1] 0(第一天不可能处于卖出后的冷冻期)dp[0][2] 0。 最终答案max(dp[n-1][1], dp[n-1][2])因为最后一天持有股票肯定不是最优的。通过状态机我们将复杂的买卖规则清晰地刻画成了状态之间的转移。在国赛中遇到涉及多种状态、且有特定转移规则的问题如“打家劫舍”中相邻不能偷、蓝桥杯真题中的“高僧斗法”等博弈问题都可以尝试构建状态机模型。3.2 状态压缩DP用二进制表示集合当问题的状态是一个“集合”时比如哪些点被访问过、哪些任务已完成如果集合元素不多通常 n 20我们可以用一个整数的二进制位来表示这个集合这就是状态压缩DP。经典例题旅行商问题TSP有n个城市从城市0出发要访问所有城市恰好一次后回到0求最短路径。状态定义dp[S][i]表示已经访问过的城市集合为S一个二进制数第k位为1表示城市k已访问当前位于城市i的最小花费。状态转移考虑当前状态(S, i)下一步可以去往任何一个未访问的城市j即S的第j位为0。转移方程为dp[S | (1j)][j] min(dp[S | (1j)][j], dp[S][i] dist[i][j])其中|是按位或运算S | (1j)表示将城市j加入集合S。初始化dp[1][0] 0表示从城市0出发只访问了城市0集合为1当前在0号点花费为0。答案最终答案是访问所有城市后回到0即dp[(1n)-1][i] dist[i][0]的最小值其中(1n)-1表示所有n位都是1即所有城市都访问过了。状态压缩DP的难点在于位运算的熟练使用以及如何将实际问题抽象成集合的表示与转移。在蓝桥杯国赛中状态压缩常与图论、棋盘摆放如铺瓷砖问题结合考察。4. 蓝桥杯国赛真题精讲与实战拆解理论学习必须结合实战。我们选取一道经典的、融合了多种DP思想的蓝桥杯国赛真题进行深度拆解看看如何将上述知识融会贯通。题目高僧斗法蓝桥杯2013年第四届国赛真题题目描述可以抽象为在一个一维棋盘上有N个棋子代表小和尚两人轮流移动任一棋子向右移动任意正整数格但不能越过其他棋子无法移动者输即经典的“Nim博弈”变种——阶梯博弈。1. 问题转化与模型识别这不是一道直接的动态规划求最优值题而是一道博弈论题但解决博弈论问题的核心方法——SG函数Sprague-Grundy其计算过程本质上就是一种动态规划。我们需要判断当前局面是“先手必胜”还是“先手必败”。 将相邻两个小和尚配对第1和第2第3和第4...计算每一对之间的空位数。如果棋子数是奇数则最后一个单独考虑。结论是将所有“配对间隔”的SG值进行异或XOR若结果为0则先手必败否则先手必胜。而一个间隔的SG值就等于这个间隔的距离。2. 动态规划记忆化搜索求解SG函数虽然对于这个具体模型有结论但我们可以用更通用的DP思路来理解。定义sg(x)为间隔为x时的SG函数值。sg(x)的计算方式是考虑从x能转移到哪些状态即移动一个棋子后形成的新的间隔距离。sg(x)的值是这些后继状态的SG值集合的mex最小非负整数。 我们可以用记忆化搜索一种递归缓存的DP来计算from functools import lru_cache lru_cache(maxsizeNone) def sg(x): # 从间隔x可以移动1, 2, ..., x步到达状态 x-i (i从1到x) next_states {sg(x - i) for i in range(1, x 1)} # 求mex mex 0 while mex in next_states: mex 1 return mex对于本题实际上sg(x) x。但记忆化搜索的DP框架是解决更复杂博弈问题的通用武器。3. 解题步骤与代码实现读入棋子位置数组a。将棋子两两分组计算每组两个棋子之间的间隔a[i1] - a[i] - 1。将所有间隔进行异或操作得到nim_sum。如果nim_sum 0输出先手必败信息。否则先手必胜。我们需要找到第一步的走法遍历所有棋子尝试移动它计算移动后的新局面的异或值是否为0。找到一个能使异或值变为0的走法即可输出。# 核心判断与搜索走法部分伪代码 a [0] list_of_positions # 假设位置已排序开头加一个0方便处理 n len(a) - 1 nim_sum 0 for i in range(1, n, 2): # 两两配对 nim_sum ^ (a[i1] - a[i] - 1) if nim_sum 0: print(先手必败) else: for i in range(1, n1): # 尝试移动第i个棋子 for step in range(1, a[i1]-a[i]): # 可以移动的步数 # 计算移动后受影响的间隔变化 old_gap1 a[i] - a[i-1] - 1 if i%20 else ... # 需要分奇偶讨论配对 new_gap1 ... # 重新计算异或和 new_nim_sum nim_sum ^ old_gap1 ^ new_gap1 if new_nim_sum 0: print(f移动第{i}个棋子 {step} 步) return这道题完美地将博弈论、数学结论和动态规划记忆化搜索思想结合在一起。在国赛备战中遇到新题时要训练自己这种“识别模型 - 转化问题 - 应用算法”的能力。5. 动态规划的调试技巧与考场策略即使思路正确DP也极易因细节出错而得不到分。分享几个我实战中总结的调试技巧和考场策略。1. 状态定义与转移的验证画表格对于二维DP在纸上画一个dp[i][j]的表格手动推导前几行几列的值。这是最直观的检查方法能立刻发现转移方程或初始化的错误。打印DP表在代码中将关键的DP数组尤其是前几轮完整打印出来与你的手动推导进行对比。小数据暴力对拍写一个绝对正确但低效的暴力算法如DFS搜索用随机生成的小规模数据n10与你的DP程序对比结果。这是确保算法逻辑正确的“金标准”。2. 初始化与边界条件的陷阱数组大小DP数组大小通常需要n1或V1别忘了。负无穷/正无穷的初始化在求最大值时通常将DP数组初始化为一个很小的数或负无穷但要注意如果状态可能由无效状态转移而来要确保它不会被误用。例如在背包问题中dp[0]0表示容量为0时价值为0其他dp[j]初始化为负无穷表示无法恰好装满容量j。下标从0还是1开始这是一个个人习惯问题但必须保持一致。我推荐从1开始这样dp[i]对应原数据的第i个元素思维负担小不易出错。相应地输入数据也最好从下标1开始存储。3. 考场上的时间分配与策略5分钟审题建模仔细读题明确问题的目标最大/最小/方案数识别约束条件数据范围 n, V 等。数据范围是重要的提示n20 可能状压n100 可能是 O(n³) 的区间DPn1000 可能是 O(n²) 的线性DPn10^5 可能需要 O(n log n) 的优化。10分钟设计状态用一句话完整定义dp[x][y]...的含义。这是最关键的一步。如果10分钟还想不出清晰的状态定义考虑是不是模型识别错了或者需要换角度。先写暴力再优化如果直接想优化DP没思路先写一个记忆化搜索DFS缓存。记忆化搜索的思维更符合直觉写出来后再尝试将其改写成递推形式的DP。很多时候递推的转移方程就藏在记忆化搜索的递归公式里。预留时间测试边界用题目给的样例、最小情况n0,1、最大情况如果可能测试。特别检查初始化是否正确。动态规划的学习没有捷径唯有多思考、多总结、多刷题。每做一道题不仅要会写代码更要问自己这道题的状态为什么这样定义转移方程是如何推导出来的有没有更优的状态表示方法把经典的模型LIS、背包、区间、树形和进阶技巧状态机、状压内化成自己的思维工具在国赛的考场上你才能从容地拆解那些看似新颖复杂的题目。记住所有复杂的DP都是由简单的状态和转移组合而成的。祝你备赛顺利国赛夺魁