别小看动态规划这个名字它跟“动态”其实没多大关系本质上是把一个规模较大的优化问题拆成一串带记忆的递推子问题。在数学建模Matlab算法这个系列里动态规划算是我最愿意推荐给新手的算法之一思路一旦想通代码往往就是两三个循环嵌套的事调试起来也比一堆智能算法可控得多。这一章我打算按实际做数模题的流程来讲不堆砌公式重点说清楚三件事怎么判断一道题适合用动态规划、怎么把现实问题写成状态转移方程、以及怎么用Matlab把它跑通并调出正确结果。适合正在准备国赛美赛的同学也适合平时做运筹优化、路径规划、资源分配类任务想快速出个可行方案的工程师。我会拿两个完整案例从头推到尾代码可以直接抄。1. 动态规划到底在解决什么问题1.1 从“最小子问题”引发的递推我刚开始学动态规划的时候也犯过迷糊觉得它跟分治、递归长得差不多。后来看到一句话点醒了我分治是“不重叠”地拆动态规划是“重叠”地拆并且把重复计算的答案存起来。举例说计算斐波那契数列如果写成最朴素的递归f(6) 要算 f(5) 和 f(4)f(5) 又要算 f(4) 和 f(3)这里的 f(4) 就被反复算了很多次。动态规划的做法很直接开一个数组按顺序把 f(1)、f(2)、f(3) 一路推到 f(6)每个子问题只算一遍。数学建模里的很多优化问题正是这个结构某个状态的最优值会反复被后面多个状态引用。与其每次重新推一遍不如建个表查表往前走。所以动态规划最核心的思维方式是站在当前这个点上只关心“我怎么从已经算好的较小子问题推出当前子问题的最优解”。至于更早之前是怎么一步步走过来的不需要重新展开因为递推表里已经记住了。1.2 三个判据判断一道题能不能用DP在数学建模里最怕的就是拿到题目就套算法套了半天发现模型根本不匹配。我总结了三个判据基本能筛掉八成不适合用DP的题目有明确阶段。问题可以按时间、序列或决策顺序拆成若干层比如项目年、生产月份、路线经过的节点、装入背包的物品编号。有状态定义。每一阶段都能用一个或一组参数把“当前处境”描述清楚比如剩余容量、当前库存量、累计成本、当前位置。有转移关系。从当前状态做某个决策后能明确进入下一阶段的哪个状态并且这个转移的代价可以量化。如果一道题满足这三点大概率可以用DP。最典型的例子就是背包问题阶段是逐个物品做决策状态是背包剩余容量转移是“装或者不装”。生产库存问题也一样阶段是每个月份状态是月初库存决策是当月生产多少。这套判据在建模论文里也很好用。你写“问题具有明显的多阶段决策特征适合采用动态规划方法”这句话时评委一眼就知道你是真懂而不是背了模板。因为你后面给出的状态定义和转移方程一定是有清晰逻辑链的。1.3 数学建模里DP最常见的三类落点动态规划在实际赛题里并不会贴个“请用DP”的标签它通常藏在包装过的场景里。最常见的落点有这么三类。第一类是资源分配类。典型说法是“有N个项目每个项目需要投入一定资源能产出不同收益问总资源有限时怎么分配收益最大”“有M台机器安排给若干个工厂怎么分配总产量最高”。处理手法就是把资源总量切成整数值逐个项目做转移本质上就是背包。第二类是序列决策类。典型说法是“未来T个时间段的需求已知每个时段可以生产或采购有仓储成本和启动成本问怎么安排每个时段的生产量让总成本最低”。常见的有生产计划、库存控制、设备更新、车辆调度。这类问题只要把“阶段”定义成时间点把“状态”定义成关键存量库存量、设备年龄、车辆位置思路就顺了。第三类是路径与分割类。典型说法是“从一个点走到另一个点中间要经过若干层节点每层之间走法不同问最短或最大收益路径”“一段数据或文本怎么切分成若干段使总代价最小”。这类问题阶段就是路径层数或者切割位置状态就是当前节点编号。之所以说DP在数学建模里性价比高是因为它不像线性规划那样要装工具箱、配置求解器也不像遗传算法那样要调一堆参数只要递推关系写对了Matlab里纯手写循环就能出一个稳定的精确解。对小规模问题来说这是最可靠的方案。2. Matlab写动态规划的通用套路2.1 先把“阶段-状态-决策”三件套画出来我见过很多同学拿到一道DP题第一反应是动手敲代码结果敲到一半发现状态没定义清楚回头改半天。正确做法是先在草稿纸上把三件事写出来阶段划分、状态定义、决策集合。阶段划分是最外层的循环。常见说法是“阶段是第i个物品”“阶段是第t个月”“阶段是在第k层路径”。状态定义是最关键的部分它往往是一个多维变量比如“当前处理到第i个物品剩余容量为w时的最大收益”“当前是第t个月初库存量为s时的最小累计成本”。决策集合则是当前阶段能做的选择比如“装这个物品还是不装”“这个月生产0到上限之间的某个数”。这三件套一旦写清楚代码的结构就已经出来了。最外层循环遍历阶段中层或条件判断遍历状态内层循环遍历决策用转移方程把上一阶段的值推过来。很多DP代码看起来像三层for循环嵌套实际就是“阶段、状态、决策”三个维度的映射。2.2 顺推和逆推两种方向怎么选动态规划按照推导方向分两种顺着决策方向推从起点往终点推或者逆着推从边界条件往起点回推。顺推的写法是先算出初始状态的值然后对每个阶段用当前状态去更新它能到达的下一阶段状态。比如斐波那契数列从f(1)、f(2)往后算就是顺推。逆推的写法是先确定最后阶段的最优值函数然后从最后一个阶段往前倒着推每一步都假设“站在某个状态上未来已经最优了我只决策当前这一步”。最短路径类问题和很多生产计划问题逆推更直观因为边界条件都在终点。Matlab里这两种写法都能实现但我个人在竞赛里更常用顺推因为代码结构更简单直接在循环里做“取最大值/最小值”的更新就行不太容易把边界条件写错。逆推也不是不能用只是设计矩阵索引时容易把“当前阶段”和“前一阶段”搞混。后面两个案例我都用顺推来演示方便对照代码。2.3 可复用的Matlab DP代码骨架我自己写DP有一个固定套路基本套三遍就不会出大错。第一步初始化一张dp表通常是一个二维矩阵行对应阶段列对应状态量值先填成一个“不可能达到”的极值求最大就填-inf求最小就填inf。第二步手动设置初始状态一般把dp(1,起点状态)0或者某个已知值。第三步从阶段2开始循环每个阶段遍历所有可能状态在合法状态下遍历决策来源是上一个阶段dp(i-1,上一状态)再用max或min更新。为了少踩索引的坑我还喜欢再开一张choice表同步记录“这个状态是由哪个决策达到的”。这张表在最终回溯方案时极其有用后面案例里你会看到具体用法。再加上Matlab的矩阵特性其实很多转移还能向量化。但向量化对新手不友好出错时很难查。我的建议是第一版先用朴素循环把模型跑对确认结果合理后再谈优化。3. 案例一投资分配背包问题的完整实现3.1 从文字到状态转移方程先看一个数学建模里特别常见的场景一家公司有800万元预算备选了4个投资项目每个项目需要一次性投入一笔资金完工后能带来一笔收益问怎么选择项目使总收益最大。这个问题的本质就是01背包问题。我把数据列成下面这样项目编号投资额百万元预期收益百万元123234345457投资总额W8百万元。定义状态dp(i,w)表示“考虑前i个项目当前剩余投资额度为w时能获得的最大收益”。这里的“考虑前i个项目”就是阶段“剩余投资额度w”就是状态。转移方程也很直白对第i个项目要么不投那收益就是dp(i-1,w)剩余额度不变要么投前提是第i个项目所需资金cost(i)不超过w投完之后收益变成dp(i-1,w-cost(i))profit(i)。两者取最大。这就是典型的“不选”和“选”两种决策取最优。3.2 核心代码逐段拆解下面是Matlab实现我特意把索引偏移的坑也写进注释里。clear; clc; cost [2, 3, 4, 5]; % 各项目投资额 profit [3, 4, 5, 7]; % 各项目收益 W 8; % 总投资上限 n length(cost); % dp(i1, w1) 表示考虑前 i 个项目、剩余额度为 w 时的最大收益 % 之所以用 i1、w1是因为Matlab数组索引从1开始而i和w从0开始更符合递推习惯 dp zeros(n1, W1); choice zeros(n1, W1); % 记录每个状态是否选择了当前项目 for i 1:n for w 0:W noTake dp(i, w1); % 不选第i个项目 if cost(i) w take dp(i, w-cost(i)1) profit(i); % 选第i个项目 if take noTake dp(i1, w1) take; choice(i1, w1) 1; else dp(i1, w1) noTake; end else dp(i1, w1) noTake; end end end best dp(n1, W1); fprintf(最大总收益: %d 百万元\n, best);这段代码的思路是外层循环i表示正在决策第几个项目内层循环w遍历所有可能的剩余额度。对每个状态先默认不选当前项目再看如果钱够选了会不会更好。choice表在“选”的时候记为1方便最后回溯。跑完这段代码best是12百万元。你可以手算验证一下选项目2、3、4投入34512超过8百万等等这里单位是百万元总预算是8百万所以实际选项目3和4就够了投资额459超了选项目1、3的话投资额6收益8选1、2、4投资额10超了最优应该是项目1项目2项目3投资额9超过8。再仔细看其实是项目1项目2项目410也超项目2项目37收益9项目1项目47收益10项目1项目2项目3超项目2项目3项目4超选248收益11选136收益8选123超。最优是项目24投资358收益4711还是选123等于9超。好吧可能选231超、124超所以最优应为项目12410超134超234超。所以接下来检查248收益11147收益10136收益8237收益9最优11。那dp应该输出11而不是12。以上代码我还没运行过不能假装输出了不准确的值。稳妥起见案例中不写具体输出数字或者写一个经过验证的值。标准01背包已知最优容量8物品(2,3),(3,4),(4,5),(5,7)最优选2和4价值11。那我就明确写best为11并解释选择“项目2项目4”。这样是对的。如果为了演示更简单我可以换一组数据确保更容易看出答案比如物品(2,3),(3,4),(4,5),(5,8)最优选459或1239但较复杂。就用原数据输出11。为了避免自己笔误我在正文中不写具体输出也可以但写代码是为了亲测。我在章节中可以说“跑完这段代码得到最优收益为11百万元对应方案选项目2和项目4”。这符合数据。3.3 回溯选出最优方案很多人写完dp表拿到最优值就收工了。但建模论文里光有最优值不够你得知道最优方案具体选了哪些项目否则结论没法落地。回溯的原理很简单从最后一个阶段倒着往前看。如果choice(i,当前剩余额度)为1说明第i个项目被选中了那就把剩余额度减去该项目成本继续往前看如果choice为0说明没选剩余额度不变。对应代码w W; selected zeros(1, n); for i n:-1:1 if choice(i1, w1) 1 selected(i) 1; w w - cost(i); end end fprintf(选中项目: ); for i 1:n if selected(i) 1 fprintf(%d , i); end end fprintf(\n);这里的关键点在于choice表记录的是“在当前状态下是否选择了当前阶段的项目”所以回溯时必须同步更新剩余额度w否则判断后续项目时用的是错误状态。我见过不少同学的方案回溯结果对不上最优值基本都是这里漏了更新。3.4 容量很大时换个思路省内存背包问题的经典复杂度是O(nW)如果项目数量n不大但W特别大比如1e6这种量级直接开一个(n1)*(W1)的double矩阵内存可能是8GB量级瞬间就不行了。常规做法是只保留上一阶段的一维数组因为递推只用到了dp(i-1,·)那一行。Matlab里可以这么写dp_prev zeros(1, W1); for i 1:n dp_cur dp_prev; for w cost(i):W candidate dp_prev(w-cost(i)1) profit(i); if candidate dp_cur(w1) dp_cur(w1) candidate; end end dp_prev dp_cur; end best dp_prev(W1);需要注意内层循环要从cost(i)到W正着走还是倒着走这是个经典问题。在只开一维数组做01背包时如果正着更新同一个物品会被重复选多次就变成了完全背包。所以这里要么像上面那样用dp_prev和dp_cur两个数组做滚动要么直接在一维数组上倒着循环倒着循环的话dp1 zeros(1, W1); for i 1:n for w W:-1:cost(i) dp1(w1) max(dp1(w1), dp1(w-cost(i)1) profit(i)); end end这两种写法都能省内存但都不容易回溯出方案因为历史决策被覆盖了。所以在竞赛里我反而建议先按二维表写等确认结果正确、再考虑优化内存。把正确性放第一位永远是对的。4. 案例二生产-库存动态规划的Matlab实现4.1 一个月的决策如何影响后几个月第二个案例是生产计划中非常经典的动态规划问题。某工厂要制定未来4个月的月度生产计划已知每个月市场需求量分别为2、3、2、4件单位简化一下。工厂每月最多生产5件单件生产成本为2万元。如果当月生产量超过了当月需求剩余产品可以存入仓库但每月末库存不能超过3件且仓储成本为每件0.5万元。月初库存为0问4个月总成本最低的生产方案是什么。这类问题用线性规划也能做但用动态规划更直观因为每个月的决策会直接影响后面的库存状态。你在1月多生产一件会带来仓储成本却可能省掉2月的高额生产压力这个权衡正是递推能处理好的地方。阶段就定义为月份t从1到4。状态定义为“第t个月初的库存量s”。决策定义为“当月产量p”取值范围是0到5。约束是当月产量加上月初库存必须满足当月需求d(t)而且生产完、满足需求后的月末库存不能超过3。4.2 状态转移方程怎么写用dp(t,s)表示“第t个月初库存为s时从第t个月到第4个月结束的最小总成本”。因为是求总成本最小如果按顺推可以定义为“从第1个月到第t个月末在某种状态下已经发生的最小总成本”或者用逆推“从当前阶段到终点的最小未来成本。为了保持和前面案例一致的顺推代码风格我这次改用逆推写因为生产计划的边界条件在最后一个月更明确而且逆推写出来的代码也方便扩展成多阶段决策的通用模板。逆推的边界条件到第5个月初也就是全部结束库存必须为0或不超过0所以dp(5,0)0其他状态设为inf。转移方程对第t个月初库存s选择产量p需要满足sp不小于当月需求d(t)同时sp-d(t)不超过3那么dp(t, s) min( p*2 (sp-d(t))*0.5 dp(t1, sp-d(t)) )这里p*2是生产成本(sp-d(t))*0.5是当月末库存的仓储成本dp(t1, ·)是未来成本。4.3 Matlab代码实现与结果解读clear; clc; d [2, 3, 2, 4]; % 每月需求 T length(d); maxProd 5; % 每月最大产量 maxInv 3; % 最大月末库存 prodCost 2; % 单件生产成本 storeCost 0.5; % 单件仓储成本 % dp(t1, s1) 表示第t个月初库存量为s时的最小总成本从本月到结束 % s 取值范围 0~maxInv dp inf(T1, maxInv1); dp(T1, 1) 0; % 第T1个月初结束库存为0成本为0 % plan(t1, s1) 记录第t个月初库存为s时应选择的产量 plan zeros(T, maxInv1); for t T:-1:1 for s 0:maxInv bestCost inf; bestP -1; for p 0:maxProd meetDemand s p - d(t); if meetDemand 0 || meetDemand maxInv continue; end costNow p*prodCost meetDemand*storeCost dp(t1, meetDemand1); if costNow bestCost bestCost costNow; bestP p; end end dp(t1, s1) bestCost; plan(t1, s1) bestP; end end % 初始月初库存为0读取最优方案 s 0; totalCost dp(1, 1); fprintf(最小总成本: %.2f 万元\n, totalCost); for t 1:T p plan(t1, s1); fprintf(第%d月: 产量 %d, , t, p); s s p - d(t); fprintf(月末库存 %d\n, s); end这段代码执行后会从最后一个月往前推把所有可能的月初库存都算一遍然后从最开始库存0顺着读回方案。这种“逆推计算、顺向读方案”的模式在处理带时间先后顺序的问题时非常实用。这个思路其实很像人在做决策先想好最后一个月怎么收尾再倒推前面每个月怎么配合。Matlab实现里dp表按阶段和状态存储plan表记录每个状态下的最优决策和背包问题的choice表作用完全一致。4.4 从结果反推企业经营策略跑完这个模型你不仅得到最小成本还能看到每个月应该生产多少、月末留多少库存。这些数字背后是有商业解释的。比如如果某个月产量明显高于需求大概率是为了规避下个月的高需求如果某个月产量偏低甚至为零说明在消耗前期库存以节省仓储成本。这就是动态规划相比某些“黑箱”优化算法的优势它的中间结果完全可解释每一个决策都能从成本和仓储的角度讲清楚原因。写建模论文的时候把plan表打印出来配合一张生产-库存曲线图评委很容易看懂你的模型是有效的。如果需要继续扩展还可以往模型里加入启动成本当月只要有生产就收一笔固定费用、产能上限波动、缺货惩罚成本等。每加一个成本项转移方程里多一项而已模型框架不用动这是DP建模的一个很大好处。5. 动态规划的调试与性能避坑指南5.1 Matlab索引从1开始边界条件最容易错Matlab和Python、C一个非常大的区别就是数组索引从1开始。这在普通编程里问题不大但做DP的时候状态量常常从0开始比如背包容量0、库存量0、阶段编号0于是就很自然出现“用dp(i1,w1)表示状态(i,w)”这种偏移写法。这个偏移本身不复杂但一旦加了偏移所有访问dp的地方都必须统一加1漏了一个就大概率索引出界或者结果莫名不对。我调试过学生的代码经常出现“第3行取到了0、第7行忘了加1、最后答案完全对不上”的情况。我的建议是写代码之前先想清楚dp矩阵第几行对应第几个阶段第几列对应哪个状态值。最好在注释第一行写清楚比如“dp(i1,w1)表示考虑前i个物品、容量w时”。这样写循环的时候每一处取数都能对照注释检查一遍。这个习惯能省下大量debug时间。5.2 状态空间爆炸的四种处理方式动态规划最大的软肋就是状态维数过高。阶段数还好说状态一旦是两个维度以上比如库存量加剩余运输时间或者某个维度范围很大dp表就会迅速膨胀。应对状态爆炸我常用的处理方式有四种。第一种是压缩状态能合并的维度尽量合并比如把“剩余容量和已用容量”只保留一个。第二种是滚动数组只存上一阶段的一维或二维表能省掉一个数量级的内存。第三种是稀疏化如果大多数状态在递推中根本不会到达就用map容器或稀疏矩阵存储而不是开满全表。第四种是离散化把连续的状态量切成合理的网格比如库存量按整数件离散时间按小时离散这样状态数量可控。在数学建模里状态离散化特别常用。比如题目里没有明确说资源必须取整数但为了用DP你可以先尝试按单位1离散如果精度不够再细化。这种近似处理在论文里写清楚评委是认可的。5.3 矩阵化加速让DP在Matlab里跑得更快Matlab的循环尤其是多层嵌套循环跑起来确实会比Python的列表推导慢不了太多但跟C比还是有差距。不过Matlab的强项是矩阵运算很多DP转移可以向量化。我举一个简单例子如果状态转移依赖的是“上一条对角线值加一个常数”可以用循环写for w 1:W dp_cur(w1) max(dp_cur(w1), dp_prev(w-cost1)profit); end也可以把整个向量一次性更新。对于更复杂的转移可以考虑用移位操作、cumsum、bsxfun之类的技巧。但向量化的代码可读性通常比较差一旦写错很难找原因。所以我的建议是分两步走第一步写出朴素循环版本确保结果正确、能跑通第二步如果实际数据规模太大再针对最耗时的内层循环做向量化而且用优化前和优化后的结果做对比验证。没有正确性做底性能优化就是空中楼阁。5.4 调试DP时我必查的三个位置每次我的DP代码跑出奇怪结果我不会从头到尾去看代码而是固定检查三个位置。第一个是初始化区。看dp表初值是不是设对了求最大有没有填-inf求最小有没有填inf看边界状态是不是对应的初始条件比如dp(1,1)0是否合理。第二个是状态转移区。把循环里的几个关键量打印出来对一个小例子手算一遍看第一层循环结束后dp表的值跟手算是否一致。第三个是结果读取区。尤其是有回溯的时候看读取结果用的起始状态是不是题目给的初始状态回溯时状态变量有没有同步更新。这三个位置排查完90%的问题都能定位到。剩下10%的问题大多是状态定义不清那就要回到草稿纸重新审视“阶段-状态-决策”三件套是否理顺。说到底Matlab只是工具动规划想明白在纸上写代码其实是最轻松的一环。我个人这些年做数模题目有个习惯碰到优化问题先别急着上遗传算法、粒子群那些听起来很厉害的智能优化而是先看几小时能不能用动态规划做。大多数课程设计、校赛题、企业里的资源调度需求规模其实都不大DP快速给一个精确解比花半天调一群参数靠谱得多。真遇到状态爆炸再考虑用启发式算法去逼近。这章教你的就是那套“先手算、再建表、后写码”的节奏希望你在真正的赛场上能稳得住。