1. 从一道经典赛题说起为什么动态规划是组合优化的“定海神针”如果你参加过数学建模竞赛或者研究过运筹学问题大概率遇到过这样的场景面对一个看似简单但穷举起来计算量却大到离谱的组合选择问题。比如给你一个容量有限的背包和一堆价值、重量各不相同的物品如何选择物品才能在不超过背包容量的前提下让总价值最大这就是经典的0-1背包问题。再比如给你一个数字序列如何找出其中最长的严格递增子序列这些问题的共同特点是你需要从大量可能的组合中找出一个最优解。最直接的想法是“暴力枚举”把所有可能的组合都列出来比较。但稍微计算一下就知道当物品数量或序列长度达到几十、上百时可能的组合数是指数级增长的用最快的超级计算机也算不完。这时候动态规划Dynamic Programming, DP就登场了。它不是什么高深莫测的魔法而是一种极其聪明、高效的“记账”思想。我最早在准备国赛时啃了不少算法书对DP也是从懵懂到逐渐开窍。真正让我豁然开朗的是2019年国赛C题“机场的出租车问题”中对出租车调度和乘客等待时间的优化分析。虽然那题解法多样但其中涉及的多阶段决策过程其核心优化思想与动态规划不谋而合——不是一次性解决所有问题而是把大问题分解成一系列小问题并且记住已经解决过的小问题的答案避免重复计算。动态规划在组合优化中的应用就像是给一个庞大的迷宫画了一张“已探索区域地图”。每走一步你不仅知道当前的位置还知道从起点到当前位置的最优路径是什么。当你要决定下一步怎么走时你不需要重新从起点开始探索只需要基于已有的“地图”做决策。这种“以空间换时间”、“记录历史、服务未来”的思想让它成为了解决一类具有“最优子结构”和“重叠子问题”特性的组合优化问题的“定海神针”。无论是亚太杯、深圳杯还是国赛从路径规划、资源分配到生产调度DP的身影无处不在。接下来我就结合几个核心模型和实战案例拆解一下DP是如何在数学建模中具体应用的以及有哪些容易踩的坑和必须掌握的技巧。2. 动态规划的核心思想拆解最优子结构与状态转移要用好动态规划绝不能停留在套公式的层面必须深刻理解它的两个核心基石最优子结构和重叠子问题。这是判断一个问题能否用DP解决的“金标准”。2.1 最优子结构大问题的最优解包含小问题的最优解这是动态规划可行的根本逻辑。举个例子在经典的“最短路径”问题中如果我们要求从A点到D点的最短路径假设最优路径是A-B-C-D。那么这条路径上从A到C的子路径A-B-C必然也是从A到C的所有可能路径中的最短路径。如果存在一条从A到C的更短路径那么用它替换掉原路径中的A-C部分就能得到一条从A到D的更短路径这就与原路径是最优解矛盾了。在组合优化中这个特性意味着我们可以通过组合其子问题的最优解来构造原问题的最优解。0-1背包问题就是典型考虑前i件物品、背包容量为j时的最大价值dp[i][j]。对于第i件物品我们只有两种选择放或不放。不放那么问题就等价于“只考虑前i-1件物品容量为j”这个子问题最优值就是dp[i-1][j]。放那么需要先给第i件物品腾出空间问题转化为“只考虑前i-1件物品容量为j - weight[i]”这个子问题得到最优值dp[i-1][j-weight[i]]然后加上第i件物品的价值value[i]。最终dp[i][j]就是在“不放”和“放”这两个决策对应的子问题最优解中取最大值。这就是状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])。你看大问题前i个物品容量j的最优解完全由两个更小的子问题前i-1个物品容量j 或 j-weight[i]的最优解决定。注意不是所有问题都有最优子结构。比如求图中最长简单路径路径不重复访问节点就没有最优子结构。从A到C的最长路径可能是A-B-C但从A到B的最长路径可能不是A-B比如是A-D-B这就无法通过子问题最优解简单组合。建模时首先要验证这一点。2.2 重叠子问题避免重复计算的记忆化核心这是动态规划提升效率的关键。在递归地求解这些子问题时很多子问题会被反复计算多次。比如在计算斐波那契数列F(5)时递归过程会重复计算F(3)、F(2)很多次。如果直接递归时间复杂度是指数级的。动态规划通过“记忆化”Memoization或“制表法”Tabulation来解决这个问题。记忆化是自顶向下的在递归求解过程中用一个数组或哈希表把第一次计算出的子问题结果存起来下次再遇到直接查表返回。制表法是自底向上的我们先计算最小的、最基本的子问题比如dp[0][*]然后根据状态转移方程一步步递推出更大问题的解通常用循环实现。在数学建模中尤其是用Python或MATLAB编程实现时我强烈推荐优先使用自底向上的制表法。原因有三第一它通常具有更好的空间局部性执行效率更高第二它避免了递归深度过大可能导致的栈溢出问题第三它的思维过程更贴近于我们手动填表推导的过程易于调试和验证。例如背包问题的DP表就是一个二维矩阵逐个单元格填充的过程非常直观。2.3 状态设计与状态转移方程DP的灵魂这是动态规划最难也最核心的部分直接决定了算法的成败和效率。状态设计就是定义dp数组的含义。它必须能够完整描述一个子问题并且包含做出后续决策所需的全部信息。对于组合优化常见的状态设计维度包括序列问题通常以“前i个元素”作为一维状态如最长上升子序列dp[i]表示以第i个元素结尾的最长上升子序列长度。背包问题通常用二维状态dp[i][j]表示考虑前i件物品在限制条件j如容量、费用下的最优值。路径/网格问题通常用二维状态dp[i][j]表示到达坐标(i, j)时的最优值。带额外约束的问题可能需要增加状态维度。例如在背包问题中如果物品间有依赖关系状态可能需要记录“选择情况”在股票买卖问题中状态需要记录“持有/未持有”以及“交易次数”。状态转移方程则是描述状态之间如何递推的数学公式。它基于“最优子结构”枚举在最后一个阶段做出的决策并将该决策的影响反映到状态值上。写出正确的状态转移方程需要精准地理解问题中“决策”的含义。我个人的经验是先尝试用自然语言描述“要达到当前状态dp[x]上一步可能来自哪些状态dp[y]通过什么操作决策过来的这个操作对目标值的贡献是多少” 把自然语言翻译成数学表达式就是状态转移方程。3. 经典模型实战从背包到序列掌握核心范式理解了思想我们来看几个数学建模中最常考、也最实用的动态规划模型。掌握这些范式能解决一大类问题。3.1 0-1背包模型资源分配的基石0-1背包是动态规划的入门课但绝不简单。其核心是每种物品仅有一件选或不选。前面已经给出了状态和转移方程。这里重点讲空间优化和建模变形。空间优化滚动数组观察状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])当前第i行的值只依赖于第i-1行。因此我们可以只用一维数组dp[j]来表示“当前考虑物品时容量为j的最大价值”。但需要注意的是内层循环遍历容量j时必须从大到小遍历。因为dp[j]更新时需要用到上一轮即未考虑当前物品时的dp[j-weight[i]]。如果从小到大遍历dp[j-weight[i]]可能已经被当前物品更新过了这就相当于同一件物品被多次选取变成了“完全背包”问题。# 0-1背包 一维数组实现空间优化 def knapsack_01(weights, values, capacity): n len(weights) dp [0] * (capacity 1) # dp[j] 表示容量为j的背包能装的最大价值 for i in range(n): # 必须逆序保证每个物品只被计算一次 for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]建模变形在实际数学建模中纯粹的0-1背包很少直接出现但思想广泛应用。多维费用背包限制条件不止一个。比如投资问题中既有资金成本限制又有风险承受限制。状态需要升维例如dp[i][j][k]转移时需同时满足两个约束。分组背包物品属于不同的组每组内最多选一件或必须选一件。解决方法是在最外层遍历组每组内对组内物品做一次0-1背包决策。依赖背包物品间有主件/附件依赖关系。通常处理方法是将每个主件及其附件组合的所有选择方案主件 alone 主件附件A 主件附件B 主件附件AB枚举出来作为一个新的“物品组”转化为分组背包问题。我在分析2024年高教杯B题仓储搬运机器人调度时就借鉴了背包思想。虽然那是调度问题但机器人每一趟的载货选择可以看作是在其载重和容积的双重限制下从一批货物中选取价值如优先级、紧急度加权最大的组合本质上是一个带有时间窗和动态物品集的双维背包问题变种。3.2 最长上升子序列模型处理序列问题的利器最长上升子序列是序列型DP的典范。定义dp[i]为以第i个元素结尾的最长上升子序列长度。状态转移方程为dp[i] max(dp[j]) 1其中j i且nums[j] nums[i]。即去找前面所有比当前数小的位置j接在它们形成的子序列后面。朴素DP解法是O(n²)的。但在数学建模中数据规模可能很大这就需要更优的贪心二分查找解法O(n log n)其思路是维护一个tails数组tails[k]表示长度为k1的上升子序列的末尾元素的最小值。这个数组是单调递增的可以通过二分查找来更新。这个优化技巧非常重要。def lengthOfLIS(nums): tails [] for num in nums: # 二分查找第一个 num 的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) # 新建一个更长的子序列 else: tails[left] num # 替换使得该长度子序列的末尾元素更小 return len(tails)建模应用LIS模型不仅用于找递增序列。任何需要寻找一个符合某种单调性质的“最长”子序列问题都可以尝试套用或修改此模型。例如在时间序列分析中寻找“最长趋势稳定段”在调度问题中寻找满足某些约束的最长任务链。3.3 区间DP模型解决链式合并与分割问题区间DP用于解决那些问题可以分解为连续子区间的问题典型代表是矩阵链乘、石子合并。状态通常设计为dp[i][j]表示处理区间[i, j]的最优解。转移时我们需要枚举一个分割点k将区间分成[i, k]和[k1, j]然后合并这两个子区间的最优解加上合并本身的代价。状态转移方程通常形式为dp[i][j] min/max_{i k j} { dp[i][k] dp[k1][j] cost(i, k, j) }。其编程实现通常采用按区间长度递增的顺序进行递推def stone_merge(stones): n len(stones) prefix_sum [0] * (n 1) for i in range(n): prefix_sum[i 1] prefix_sum[i] stones[i] # 前缀和用于快速计算区间和 dp [[0] * n for _ in range(n)] # length 是区间长度 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) # 枚举分割点 for k in range(i, j): # 合并[i,k]和[k1,j]的代价是区间[i,j]的石子总重 cost prefix_sum[j 1] - prefix_sum[i] dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost) return dp[0][n-1]建模应用任何具有“链式”结构且操作合并、分割只涉及相邻部分的问题都可以考虑区间DP。例如生产线上多个工序的排序优化、字符串的最优编码、多边形的最优三角剖分等。在2022年国赛C题古代玻璃制品的成分分析中虽然主体是统计分析但在对成分序列进行分段归类时区间DP的思想寻找最优分割点以使段内相似度最高、段间差异最大可以作为一种潜在的模型思路。4. 数学建模中的DP进阶状态压缩与多阶段决策当问题规模进一步扩大或者约束条件更加复杂时基础的DP模型可能面临“状态爆炸”的挑战。这时就需要一些进阶技巧。4.1 状态压缩DP用位运算描述复杂选择当问题的子集选择情况需要作为状态的一部分时如果直接用集合或布尔数组表示维度会很高。状态压缩DP利用整数的二进制位来表示一个集合每一位代表一个元素是否被选中。这样一个集合就可以用一个整数来表示极大地压缩了状态空间。最典型的例子是旅行商问题。dp[mask][i]表示已经访问过的城市集合为mask二进制表示当前位于城市i的最小花费。mask的第k位为1表示城市k已访问。状态转移时我们枚举下一个要去的城市j需在mask中未访问新的状态为dp[mask | (1 j)][j] min(dp[mask | (1 j)][j], dp[mask][i] dist[i][j])。def tsp(dist): n len(dist) # dp[mask][i]: 访问集合mask最后在i城市的最小成本 dp [[float(inf)] * n for _ in range(1 n)] dp[1][0] 0 # 从城市0出发只访问了城市0mask1 for mask in range(1 n): for i in range(n): if dp[mask][i] float(inf): continue # 尝试从i去往所有未访问的城市j for j in range(n): if mask (1 j): # j已访问 continue new_mask mask | (1 j) dp[new_mask][j] min(dp[new_mask][j], dp[mask][i] dist[i][j]) # 最终要回到起点城市0 ans float(inf) final_mask (1 n) - 1 for i in range(n): ans min(ans, dp[final_mask][i] dist[i][0]) return ans建模应用状态压缩DP适用于元素数量较少通常n 20但需要精确记录每个元素选择状态的问题。例如任务分配问题n个人做n项任务、棋盘覆盖问题如铺瓷砖、以及一些复杂的排班或选址问题。在2025年深圳杯A题等涉及精细化调度或布局的题目中这种技巧很可能派上用场。4.2 多阶段决策与DAG上的DP处理具有时序的优化很多组合优化问题天然具有阶段性例如项目计划、资源随时间分配、多回合博弈等。这类问题可以建模为有向无环图上的最长/最短路径问题。每个阶段是一个状态决策是从一个状态转移到另一个状态转移带有收益或成本。设dp[state]表示到达某个状态时的最优值。由于图是无环的我们可以按照拓扑序或阶段顺序来递推。对于每个状态考察所有能到达它的前驱状态prev_state进行转移dp[state] min/max_{prev_state} { dp[prev_state] cost(prev_state - state) }。建模应用这是动态规划非常强大的一类应用。例如生产库存问题状态可以是第t月库存量s。决策是本月生产多少满足需求后剩余库存进入下个月。转移成本包括生产成本和库存持有成本。投资组合问题状态可以是第t期持有的资产分布。决策是如何调整资产比例。转移收益是资产回报可能还有交易费用。游戏策略问题状态是游戏局面如棋盘、角色属性、回合数。决策是采取的行动。转移收益是行动带来的即时奖励。这类问题的关键在于精准定义状态确保其包含所有影响未来决策的历史信息马尔可夫性同时又要避免状态空间过大。通常需要结合问题背景进行抽象和简化。5. 从理论到论文DP在建模全流程中的实践要点掌握了算法如何在数学建模竞赛中将其转化为一篇优秀的论文这里分享一些结合DP特点的实战心得。5.1 问题分析与模型建立如何想到用DP拿到赛题如何判断是否适合用动态规划我总结了一个简单的 checklist问题是否求最优解最大/最小最多/最少问题能否分解为相似的、规模更小的子问题子问题之间是否存在大量重叠如果暴力搜索是否会有大量重复计算子问题的最优解能否组合成原问题的最优解最优子结构如果以上答案多为“是”那么DP就是一个强有力的候选工具。在论文的“模型建立”部分你需要清晰地阐述阶段划分将问题过程恰当地划分为若干个相互联系的阶段。状态定义用数学语言精确定义dp变量及其含义。这是模型的核心务必严谨。决策与状态转移方程说明在每个阶段有哪些选择决策以及这些选择如何导致状态转移。给出状态转移方程的数学形式。边界条件确定最小子问题初始状态的解是什么。目标函数最终要求解的是哪个状态的值。例如在解决一个资源调度问题时你可以写道“我们将整个调度周期划分为T个离散的时间阶段。定义状态dp[t][r]表示在时间阶段t结束时剩余资源量为r时所获得的最大效益。在阶段t我们可以选择执行任务集S中的某些任务决策变量为x_s... 状态转移方程为dp[t][r] max_{决策可行} { dp[t-1][r] benefit(决策) }其中r是执行决策前所需的资源... 边界条件为dp[0][R] 0其中R为初始资源。最终目标是求max_{r} dp[T][r]。”5.2 算法实现与复杂度分析效率与可行性的平衡在“算法设计”部分你需要描述清楚自底向上递推的过程伪代码或流程图并分析时间和空间复杂度。复杂度分析至关重要它证明了你的算法对题目给定的数据规模是可行的。时间复杂度通常是状态数量 × 每个状态的决策数。例如0-1背包问题状态数为O(n*C)每个状态决策数为O(1)总复杂度为O(nC)。如果n*C在10^6到10^7量级通常可以在几秒内完成。空间复杂度如果使用了滚动数组优化需要特别说明。例如“由于状态转移只依赖于前一行我们可以使用一维数组进行空间优化将空间复杂度从O(nC)降低到O(C)。”如果复杂度较高需要讨论优化可能性例如剪枝根据问题特性提前排除无效状态或决策。单调队列/单调栈优化对于形如dp[i] min/max_{j in [L(i), R(i)]} { dp[j] cost(j, i) }的转移方程如果cost函数有特殊性质如凸性可以用单调数据结构将转移复杂度从O(n)降到O(1)。四边形不等式优化主要用于区间DP优化分割点k的枚举范围。在论文中即使你没有实现这些高级优化也可以将其作为“模型优化方向”进行讨论体现思考的深度。5.3 模型求解与结果分析如何展示和解释DP结果动态规划求解完成后得到的通常不仅仅是一个最优值而是一张完整的dp表。如何从中提取出最优方案是很多新手会忽略的一步。方案还原在递推计算dp值时通常需要同步记录“决策路径”。我们可以用另一个数组pre[i][j]来记录状态(i, j)是由哪个前驱状态通过什么决策转移而来的。计算结束后从目标状态开始根据pre数组逆向回溯就能得到构成最优解的具体选择序列。在结果分析部分除了给出最优值还应展示关键状态可以附上一小部分dp表例如前几行前几列让读者直观感受递推过程。分析方案详细解释得到的最优方案是什么为什么它是合理的。例如在背包问题中列出被选中的物品及其总重量、总价值。灵敏度分析这是数学建模论文的加分项。可以探讨当参数如背包容量、物品价值发生微小变化时最优解和最优方案是否稳定。对于DP模型有时可以观察dp表最后一行或最后一列的变化趋势。模型对比如果问题也可以用贪心、整数规划等方法求解可以做一个简单的对比说明DP在求解精度上的优势贪心可能不是最优或者在求解效率上的特点相比整数规划求解器DP对于特定结构问题更快。5.4 常见“坑点”与调试技巧基于多次参赛和辅导的经验我总结几个DP在数学建模中容易出错的地方数组下标与边界这是最最常见的错误。DP数组大小通常需要开到n1或capacity1循环的起止点要仔细推敲。特别是使用一维数组优化时内层循环的遍历顺序正序/逆序直接关系到问题类型完全背包/0-1背包。初始值设置dp数组的初始化至关重要。对于求最大值问题通常初始化为负无穷-inf对于求最小值问题初始化为正无穷inf。边界状态如dp[0][*]则根据实际问题意义赋予确定值通常为0。不正确的初始化会导致结果错误。状态转移方程的逻辑漏洞确保枚举了所有可能的决策并且转移条件正确。一个有效的检查方法是用手动计算一个小规模例子例如n3, capacity5画出完整的dp表与程序输出对比。空间与时间超限在建模时就要预估状态数量。如果状态数 × 决策数超过10^8通常就需要优化或考虑其他算法。对于Python使用list比dict更快对于多维数组考虑能否降维。浮点数精度如果价值或成本是浮点数比较大小时要小心精度误差避免使用而应使用abs(a-b) eps。在可能的情况下尽量通过缩放转化为整数运算。调试时我的习惯是先写一个暴力搜索/递归版本用于验证小数据样本下DP算法的正确性。在DP代码中关键步骤后打印中间状态尤其是前几轮循环的dp值。对于复杂模型撰写详细的注释说明每个状态、每个转移的含义。动态规划的魅力在于它将一个看似复杂的组合爆炸问题转化为一个结构清晰、逐步推进的填表过程。在数学建模竞赛的高压环境下对DP模型的熟练运用能让你在面对最优决策类问题时拥有一个可靠且高效的解决方案库。它不仅仅是算法更是一种化繁为简、分而治之的系统性思维方式。这种思维对于解决竞赛中乃至实际科研工程中的复杂优化问题都是大有裨益的。