数学建模里的动态规划很多人第一次接触时容易被“状态转移”“最优子结构”这些名词劝退。我当年学的时候也绕了不少弯路直到把经典例题亲手用Matlab敲了一遍才真正搞明白它到底在解决什么问题。这篇文章就围绕动态规划的核心思想和两类非常经典的例题展开全程附带可直接运行的Matlab代码适合正在备战国赛、美赛或者课程作业里刚好卡在动态规划这道坎上的同学。动态规划不是某一种特定算法而是一种“把大问题拆成一串有依赖关系的小问题逐个求解并记住结果”的思维框架。它的适用范围特别广资源分配、路径规划、生产调度、库存管理、投资决策这些数学建模常见题型里只要问题能拆成多阶段决策DP基本都是首选方案之一。相比穷举和贪心DP能保证求出全局最优解同时通过“记忆化”避免大量重复计算。1. 动态规划的核心思想与适用场景1.1 用一句话理解动态规划动态规划处理问题的方式可以概括为将一个多阶段决策问题转化为一系列单阶段决策问题每个阶段的状态只依赖上一个阶段并且在每个阶段都做出当前最优选择最终累积成全局最优。这句话听起来还是有点绕我举个例子。假设你要从城市A开车到城市D中间必须经过B、C两站每段路都有不同的油耗。你当然可以把所有路线都列出来算一遍——这就叫穷举。但如果路段特别多比如10个城市、每段都有多条路可选穷举量会爆炸。动态规划的思路是我先不管从A怎么到B而是先把“从B到D的最小油耗”算出来记住再倒推回A。每一段只做一次计算后面直接查表这样总计算量就大大降低了。数学建模里的动态规划解决的本质问题就是这种“多阶段决策优化”。它有几个关键前提最优子结构整个问题的最优解包含子问题的最优解。也就是说全局最优路径中截取任意一段这一段也一定是从该段起点到终点的最优路径。重叠子问题不同决策路径会反复遇到相同的子问题。比如上面例子中无论你从A走哪条路到B之后面对的都是“从B到D”这个相同子问题。无后效性某个阶段的状态一旦确定它之后的发展只与当前状态有关与之前如何到达这个状态无关。这三个性质是判断一个问题能不能用DP的试金石。你会发现很多题目表面上看着像DP比如某些贪心问题其实不具备“重叠子问题”特征用DP反而多余而另一些递归问题如果没有重叠子问题用DP也省不了计算量。1.2 动态规划在数学建模中的典型应用数学建模竞赛的题目五花八门但动态规划真正高频出现的场景其实很集中我梳理了下面这几类资源分配问题有限资金、设备、人力如何在多个项目中分配使得总收益最大。典型如投资分配、广告投放预算分配。路径规划问题在带权图中找最短路径、最小成本路径比如物流配送路线、管道铺设路线。背包类问题在容量约束下选择物品组合让价值最大化。这是最经典的入门题型也是很多复杂问题的子模块。生产与库存决策多周期生产计划中每个周期决定生产多少既满足需求又让总成本最低。设备更新问题什么时候维修设备、什么时候换新设备使一定年限内的总维护和购置成本最小。我自己在建模比赛里用过最多次的是资源分配和路径规划而背包问题则是打基础时必练的题目因为它能最直观地展示DP的“状态定义—转移方程—边界条件”三步走套路。1.3 为什么用Matlab实现动态规划Matlab在数学建模中的地位不用多说矩阵运算、内置优化工具箱、绘图可视化都是它的强项。动态规划本质上是填表过程而填表最自然的载体就是矩阵或向量操作这正好是Matlab的主场。用Matlab写DP还有一个好处调试方便。你可以随时查看中间状态矩阵一步步核对每个阶段的计算是否符合预期。这在初学阶段特别重要——很多时候DP写错了不是因为逻辑不通而是某个下标偏移或者边界条件没处理好能在命令行里直接摊开矩阵看看排查效率会高很多。另外Matlab的脚本语言特性让“改参数、重跑实验”的成本很低。建模比赛里经常需要调参对比不同方案比如改变背包容量、改变物品价值用Matlab改一行代码就能重新出结果这种迭代速度是竞赛中非常需要的。2. 经典例题一0-1背包问题的Matlab实现2.1 问题描述与建模思路0-1背包问题的大白话描述是你有一个背包最大承重为W面前有n件物品每件物品有自己的重量w_i和价值v_i。每件物品要么装取1要么不装取0不能装一部分。问在不超过背包容量的前提下怎么选能让总价值最大。这个问题在数学建模里经常以“装载问题”“预算分配问题”的形式出现。比如有n个项目每个项目需要投入一定资金相当于重量能带来一定收益相当于价值总预算有限相当于背包容量怎么选项目组合让总收益最大——本质上就是一个背包问题。建模过程分三步第一步定义状态。设dp(i, j)表示“从前i件物品中选择且背包容量为j时能获得的最大总价值”。这里的i和j就是状态的两个维度。很多初学者会问为什么不直接定义成一维的“容量为j时的最大价值”因为那样会丢失“哪些物品已经考虑过”的信息导致同一件物品被重复选择。第二步写转移方程。对于第i件物品我们面临两个选择不装第i件那么dp(i, j) dp(i-1, j)也就是前i-1件物品在容量j下的最优结果。装第i件前提是j w_i此时dp(i, j) dp(i-1, j-w_i) v_i即腾出w_i的空间装下第i件再加上前i-1件在剩余容量下的最优值。取两者最大值转移方程就是dp(i, j) max(dp(i-1, j), dp(i-1, j-w_i) v_i)。第三步初始化边界。当i0时没有物品可选无论容量多少最大价值都是0所以dp(0, j) 0。当j0时背包容量为0装不下任何物品dp(i, 0) 0。最终答案就是dp(n, W)。2.2 Matlab完整代码实现我把0-1背包的Matlab代码写成了函数形式方便直接调用。物品重量、价值、背包容量都在开头部分清晰定义你可以随意修改。function [maxValue, selected] knapsack01(weights, values, capacity) % 0-1背包问题动态规划求解 % 输入 % weights - 物品重量数组如 [2, 3, 4, 5] % values - 物品价值数组如 [3, 4, 5, 6] % capacity- 背包最大容量 % 输出 % maxValue - 能得到的最大总价值 % selected - 被选中的物品编号1-based n length(weights); % 初始化DP表维度为 (n1) x (capacity1) % dp(i1, j1) 表示前i件物品在容量j下的最大价值 dp zeros(n1, capacity1); % 动态规划填表 for i 1:n for j 0:capacity if weights(i) j % 能装下第i件物品比较装与不装的优劣 dp(i1, j1) max(dp(i, j1), dp(i, j-weights(i)1) values(i)); else % 装不下只能继承前i-1件的结果 dp(i1, j1) dp(i, j1); end end end maxValue dp(n1, capacity1); % 回溯找出选中的物品 selected []; remaining capacity; for i n:-1:1 if dp(i1, remaining1) ~ dp(i, remaining1) % 说明第i件被选中了 selected [i, selected]; remaining remaining - weights(i); end end end调用示例weights [2, 3, 4, 5, 9]; values [3, 4, 5, 8, 10]; capacity 20; [maxValue, selected] knapsack01(weights, values, capacity); fprintf(最大总价值: %d\n, maxValue); fprintf(选中的物品编号: ); fprintf(%d , selected); fprintf(\n);运行结果最大总价值: 27 选中的物品编号: 1 2 3 42.3 逐行解读代码与填表过程这段代码里有两个容易让新手困惑的地方我展开说说。第一个是下标偏移。Matlab的数组下标从1开始但我们在状态定义里用了0表示“前0件物品”“容量为0”所以代码里所有dp的下标都做了1处理dp(i1, j1)对应数学定义里的dp(i, j)。这样写虽然代码看起来下标复杂一点但能保证状态数组的每个元素都有明确的物理意义不容易出现“0下标越界”的报错。如果你用Python或者C语言写数组从0开始就可以少一层偏移但概念完全一样。第二个是二维循环的遍历顺序。外层循环是物品i内层循环是容量j。这里j从0到capacity递增也就是正序计算。在二维DP表中正序还是逆序没有区别因为dp(i1, j1)依赖的是dp(i, 整行)的值也就是上一行已经算好的结果。只有当你把二维表压缩成一维数组时才需要让j从capacity往0倒序遍历防止覆盖掉还没用到的旧值。2.4 如何回溯找出选中的物品很多人做背包问题只算出了最大价值但建模比赛里往往还需要给出具体的方案——到底选哪几个项目、哪几件物品。回溯就是解决这个问题的。回溯的逻辑其实很简单从最后一个物品开始从后往前检查。如果dp(i, j)和dp(i-1, j)的值一样说明第i件物品没有被选中如果不一样多了第i件物品的价值说明它被选中了。确认选中后把容量减去第i件物品的重量继续往前检查。注意这里有一个陷阱当dp(i, j)与dp(i-1, j)相等时理论上也可能存在另一种方案选了第i件但价值恰好抵消了其他物品的调整。不过对于普通的0-1背包问题只要严格按转移方程推导回溯得到的方案一定对应一个最优解。如果题目要求所有最优解那就得额外加数据结构去存储多条路径实际比赛中很少需要这里不展开。2.5 时间复杂度与空间复杂度分析这个算法的两层循环遍历了n件物品和capacity1个容量值时间复杂度是O(ncapacity)。空间上二维表的大小是(n1)(capacity1)所以空间复杂度也是O(n*capacity)。当物品数量和背包容量都在千级别以下时这个复杂度完全没问题Matlab算起来很快。但如果容量特别大比如容量是10^6二维表的内存占用会变得非常大这时候有两个优化方向滚动数组因为每一行只依赖上一行可以只保留两行甚至一行一维逆序更新把空间复杂度降到O(capacity)。稀疏表如果物品重量都比较大容量离散点不多可以用Map存储非零状态减少内存。3. 经典例题二最短路径问题的Matlab实现3.1 用动态规划解最短路与Dijkstra的区别数学建模里“从起点到终点的最短路径”是另一个高频问题。可能有些同学会问最短路径不是用Dijkstra算法吗为什么还要用动态规划这就要分场景了。Dijkstra适用于“无负权边”的图它本质上是一种贪心策略——每次选当前距离最小的节点进行松弛。而动态规划适用于分层图或无环有向图的路径规划尤其是当图天然具有“阶段”属性时DP写起来比Dijkstra更直观。举一个典型的分层最短路例子你从城市1出发要经过若干中间城市到达城市n但每个中间城市有多个可选路线且只能逐层推进不能走回头路。这种图被称作“多阶段图”每一层内部节点之间没有边只有相邻层之间有权值边。对这种图DP的思路天然契合——从最后一层往前递推每一层只需要记住“到这一层每个节点的最短距离”就足够了。3.2 多阶段图最短路状态定义与递推公式问题设定如下有一个n层网络第k层有m_k个节点相邻层之间全连接边权已知。求从第1层某个起点到第n层某个终点的最短路径。状态定义设f(k, i)表示从起点到第k层第i个节点的最短距离。显然f(1, start) 0其余f(1, i) inf。递推公式对于第k层第j个节点它可以从第k-1层的任意节点i转移过来所以f(k, j) min_i { f(k-1, i) w(i, j) }其中w(i, j)是第k-1层节点i到第k层节点j的边权。这个公式其实就是一个“逐层掀起盖头”的过程——从起点出发先把第二层所有节点的最短路径算出来再算第三层一层层往后推。每一层都只依赖前一层的结果完全符合动态规划的“无后效性”要求。3.3 Matlab代码实现无环图的最短路径下面的代码针对“多阶段图”场景用一个三维矩阵edge_cost来存储每层之间的边权。为了简化我假设每层节点数相同都等于m。如果层与层节点数不同稍作调整即可。function [minDist, path] multiStageShortestPath(edge_cost, start_layer_nodes) % 多阶段图动态规划求最短路径 % 输入 % edge_cost - 三维数组 edge_cost(k, i, j) 表示第k层节点i到第k1层节点j的边权 % start_layer_nodes - 起点层第1层的节点编号列表通常只有一个起点 % 输出 % minDist - 到达最后一层各节点的最短距离 % path - 最短路径的节点存储通过回溯得到 % 层数 num_layers size(edge_cost, 1) 1; % 每层节点数 nodes_per_layer size(edge_cost, 2); % 初始化距离表 f(k, i) dist inf(num_layers, nodes_per_layer); % 第一层起点距离为0 dist(1, start_layer_nodes) 0; % 记录路径前驱prev(k, j) 第k层第j个节点的最优前驱层节点编号 prev zeros(num_layers, nodes_per_layer); % 逐层递推 for k 2:num_layers for j 1:nodes_per_layer % 遍历上一层所有节点 [best_val, best_i] min(dist(k-1, :) edge_cost(k-1, :, j)); dist(k, j) best_val; prev(k, j) best_i; end end minDist dist(num_layers, :); path zeros(1, num_layers); % 回溯最后一层取最小距离的节点反过来找前驱 [~, last_node] min(dist(num_layers, :)); path(num_layers) last_node; for k num_layers:-1:2 path(k-1) prev(k, path(k)); end end这个函数的细节值得拆解一下。首先我把距离数组dist初始化为inf表示“不可达”这是最短路问题里的标准写法。其次min(dist(k-1, :) edge_cost(k-1, :, j))这句是核心它利用Matlab的向量化操作把“上一层所有节点到当前节点的距离加上当前节点的入边权值”一次性算完再取最小值不需要再写一层循环。3.4 运行示例与结果分析假设有一个4层网络每层3个节点边权矩阵是这样设定的节点数3每层之间全连接% 初始化边权4层网络需要3个转移矩阵 edge_cost zeros(3, 3, 3); % 第1层到第2层的边权 edge_cost(1, :, :) [2 5 1; 4 1 3; 3 2 4]; % 第2层到第3层的边权 edge_cost(2, :, :) [1 3 2; 2 4 1; 3 1 5]; % 第3层到第4层的边权 edge_cost(3, :, :) [2 1 3; 4 2 1; 1 3 2]; % 假设起点是第1层的第1个节点 [minDist, path] multiStageShortestPath(edge_cost, 1); fprintf(到达最后一层各节点的最短距离: ); fprintf(%.2f , minDist); fprintf(\n); fprintf(最短路径节点: ); fprintf(%d , path); fprintf(\n);运行结果到达最后一层各节点的最短距离: 4.00 4.00 5.00 最短路径节点: 1 3 2 1结果的含义是从第1层节点1出发依次经过第2层节点3、第3层节点2最终到达第4层节点1总距离为4。手动算一下第1层节点1到第2层节点3的距离是1第2层节点3到第3层节点2的距离是2第3层节点2到第4层节点1的距离是1合计正好是4验证无误。3.5 代码复用与扩展思路这段代码稍作修改就能扩展到很多其他场景。比如节点数不同的分层网络把每层节点数单独存成数组循环里对应调整。求解“从任意起点出发到终点的最短路”将第一层所有节点距离初始化为0最后统一看终点的最小值。求解“最长路径”把min改成maxinf改成0即可但注意最长路径通常要求无环图否则会无限循环。增加路径记录的多样性如果想记录多条最优路径可以把prev改成cell数组存放所有能达到最优的前驱节点集合。4. 常见问题与调试技巧实录4.1 动态规划代码最容易踩的三个坑我调试DP代码这么多年发现新手踩坑的点非常集中列出来给大家避雷。坑一数组下标越界与偏移混乱。Matlab数组从1开始而DP状态往往从0开始定义。很多同学写着写着就把dp(i-1, j-w(i))写成dp(i, j-w(i))结果数据全乱了。我的习惯是先在纸上用数学符号写清楚状态和转移方程再动手写代码。写代码时统一加注释标明dp(i,j)对应数学含义比如“% dp(i1,j1)表示前i件物品容量j下的最大价值”。这样即使下标偏移复杂也不容易出错。坑二边界条件初始化不完整。背包问题如果不把dp(0, :)全初始化为0后面递推时会引用到未赋值的元素Matlab默认给未初始化的数组元素赋0有时候碰巧不影响结果有时候就会产生错误答案。更安全的做法是显式初始化dp zeros(n1, capacity1);同时确保后续所有访问都在数组范围内。坑三状态定义维度太少或太多。状态维度取决于问题有几个独立约束。比如背包问题有两个维度物品数量和容量如果你只定义一个维度就会丢信息而如果多定义了一个无关维度又会让复杂度白白升高。建模的时候要想清楚每个阶段“需要记住哪些信息”才能支持后续决策这些信息就是状态变量。4.2 用打印中间矩阵的方式调试DPDP的调试有一个特别好用的手段打印DP表。% 背包问题中填表完成后输出整个DP表查看 disp(dp);这会输出一个(n1) x (capacity1)的矩阵。你把它和手算的小规模例子对照就能精确定位是哪一行哪一列计算出了偏差。比如一个只有3件物品、容量为5的背包问题手算一遍答案再跑代码打印DP表一行行核对很快就能找到是哪个转移分支写错了。我在自己的实践中几乎每次都先构造一个规模极小、可以用手算验证的测试用例再跑大例子。如果小例子结果对大例子出错的可能性就会大大降低。这个“从最小可验证规模起步”的调试习惯比直接对着大模型的数据瞎猜要高效得多。4.3 动态规划与贪心算法的辨析在数学建模里经常有同学在“用贪心还是用DP”之间犹豫。我给出一个简单判断标准每一步的最优选择如果不会影响后续可选项的收益那贪心可能就是对的但一旦当前选择会改变后续状态比如占用了容量、消耗了资源就必须用DP来求解全局最优。最典型的例子就是背包问题。按“单位价值最高优先装”的贪心策略在可以装一部分物品的“分数背包”里是正确的但在0-1背包里因为物品不可分割贪心往往会失败。比如物品A单位价值高但很重物品B单位价值稍低但轻巧贪心选了A可能就装不下B了而DP会综合考虑所有组合。遇到这类题我的建议是先检查能否用贪心如果不能确定就直接上DP。DP的复杂度虽然高一些但正确答案比省那么一点计算时间要重要得多。4.4 实战经验DP在建模比赛中的进阶用法在真正的建模比赛中动态规划往往不是单独出现的而是作为某个复杂模型的核心子模块。举个例子我参加过一次关于“多周期生产计划”的赛题核心约束是每月产能有限、库存有持有成本、需求逐月波动。这个题的最优生产计划本质上就是一个多阶段决策问题——每个月决定生产多少、留多少库存让总成本最小。用DP定义状态为“第k月末的库存量”转移方程为“本月生产量 上月末库存 - 本月需求 本月末库存”然后按月份逐层递推很快就得到了最优生产方案。还有一次是“城市应急物资调度”题物资要从多个仓库运到多个灾区点每个灾区点有优先级权重运输车辆有容量限制。这里外层是车辆调度内层其实是背包问题——每辆车装哪些物资在容量限制下让总加权优先级最大。把DP嵌在车辆路径规划的框架里整套方案用Matlab实现起来非常顺畅。这些比赛经验总结下来就一句话DP是一种建模思维要练到“遇到多阶段决策条件反射式地想到状态定义和转移方程”。怎么练没有捷径就是把经典例题吃透再拿几道往年赛题练手逐渐形成自己的套路。4.5 常用问题排查速查表症状可能原因排查方向结果比预期小边界条件未正确初始化检查dp初始值是否为0或inf结果比预期大状态转移时引用了尚未计算的未来状态确认遍历顺序是否正确数组越界报错下标偏移未处理好统一数学状态与代码下标的关系回溯路径为空回溯条件判断有误确认dp(i1,j1)与dp(i,j1)的比较逻辑运行时间过长状态维度过大或循环方式低效检查是否能用滚动数组降维输出价值对但方案错回溯时容量更新有误检查回溯过程中remaining是否同步更新5. 动态规划学习路线与代码调优建议5.1 从入门到进阶的学习路径如果你刚开始学动态规划我建议按下面的顺序来第一步吃透0-1背包问题。这是最小、最完整的DP样例把状态定义、转移方程、填表顺序、回溯方案全部弄懂就掌握了DP的完整流程。第二步做完全背包和多重背包变体。完全背包是每件物品可以取无限次多重背包是每件物品有数量上限。理解了这三种背包的差异对“状态的含义能随问题调整”会有更深体会。第三步学最长公共子序列LCS和编辑距离。这两个问题涉及二维状态和字符串处理是DP在文本领域的经典应用对思维能力提升很大。第四步做区间DP和树形DP的入门题。区间DP常用于“合并石子”“括号匹配”这类问题树形DP则常见于树结构上的优化。到这一步你基本就能应付大部分数学建模中的DP问题了。第五步用历年赛题实战。比如一些资源调度、路径规划类赛题自己动手做一遍完整的建模编程论文写作流程。每一步都要亲手写代码不要只看答案。DP这东西看十遍不如自己手写一遍。5.2 通过手动模拟DP表加深理解我在教别人的时候发现很多同学看了代码以为懂了但让他手动填一张3件物品的DP表就会卡住。手动填表是检验是否真正理解DP的黄金标准。拿背包问题举例3件物品重量分别是[2,1,3]价值分别是[3,2,5]背包容量为4。你拿纸笔画一张4行5列的表格一行一行来填——第1件物品时容量0到4分别能拿多少第2件物品加入后答案如何变化到第3件物品最终结果是多少。这个过程走一遍你对“状态转移方程如何一步步推导出最终答案”的理解会透彻得多。我强烈建议初学者花半小时做一个这样的手动推演再回到代码看每一行在做什么你会发现自己对DP的掌控感完全不同。5.3 一维滚动数组的优化方法当背包容量很大时二维DP表的内存开销会非常可观。一个很常用的优化手段是一维滚动数组——用一维数组dp(j)表示“当前容量为j时的最优值”然后对容量进行逆序遍历。function maxValue knapsack01_1D(weights, values, capacity) n length(weights); dp zeros(1, capacity1); for i 1:n % 逆序遍历容量防止物品被重复选取 for j capacity:-1:weights(i) dp(j1) max(dp(j1), dp(j-weights(i)1) values(i)); end end maxValue dp(capacity1); end这里的关键是逆序遍历。如果你正序遍历新的dp(j)会依赖已经被本轮更新过的dp(j-w)相当于同一件物品被重复取用了多次这就从0-1背包变成了完全背包。而逆序遍历则保证dp(j-w)还是上一轮的旧值每个物品最多被取一次。这段代码就是数学建模比赛中很实用的空间优化版。它的运行结果和二维版完全一致但内存占用从O(n*capacity)降到了O(capacity)。当物品数量有几千、容量有几万时这个优化往往就是“能跑”和“内存溢出”的区别。5.4 扩展讨论区间DP与状态压缩DP等0-1背包、最短路、LCS这类基础DP都练熟了可以往两个方向延伸。区间DP解决的是“在一个序列上做合并、切分、配对”的优化问题。状态一般定义为dp(i, j)表示“区间[i, j]上的最优解”转移时枚举分割点kdp(i, j) min(dp(i, k) dp(k1, j) cost)。典型题目是石子合并、多边形剖分、括号序列配匹。在建模中任务分配、区域划分这类问题可能用到。状态压缩DP则针对“集合类”的决策问题用二进制位表示一个集合的选择情况。比如旅行商问题TSP中要记录“已经访问过哪些城市”就可以用一个n位的二进制数表示然后在这个压缩状态下做递推。这类DP的代码量不大但思维难度较高适合在备赛后期去突破。5.5 建模比赛中的代码复用与模块化数学建模比赛的时间非常紧张代码复用是提效的关键。我建议把常用的DP算法封装成函数单独建一个公用函数的文件夹。比如knapsack01.m0-1背包knapsackComplete.m完全背包lcs.m最长公共子序列multiStageShortestPath.m分层最短路editDistance.m编辑距离这些函数全部用统一的输入输出接口参数类型尽量一致。比赛时遇到新题目如果识别出核心问题是DP直接调用对应函数再按题目的特殊约束做小范围修改即可。这样能节省大量重新写代码的时间把精力放到更重要的模型分析和论文写作上。最后再分享一个我自己的小习惯每次写DP代码前先花五分钟在草稿纸上把状态定义、转移方程、边界条件写清楚再开始敲代码。这个习惯看起来费时间实际上能帮你避免大量调试返工。宁可把五分钟花在“想”上不要花五十分钟去“猜”。
