1. 从一道“切钢条”的题说起为什么动态规划是数学建模的“王牌算法”如果你参加过数学建模竞赛或者正在准备那你一定听过“动态规划”这个名字。它常常和“最优化”、“状态转移”这些听起来就有点唬人的词绑在一起出现在赛题解析或者优秀论文的算法部分。很多新手拿到一个题目一看“哦这题可以用动态规划”然后就去翻模板、找代码结果往往是套了半天要么程序跑不出来要么结果不对最后只能草草收场留下一句“动态规划太难了”。今天我想从一个最经典的例子——“钢条切割问题”开始彻底掰开揉碎跟你聊聊动态规划到底是个啥更重要的是在数学建模的实战中我们到底该怎么用它。这不是一篇教科书式的理论复述而是一个踩过无数坑的过来人跟你分享怎么把这块“硬骨头”变成你手里最趁手的工具。想象一下这个场景你是一家钢条加工厂的厂长。现在有一根长度为 n 英寸的钢条不同长度的钢条在市场上的售价不同比如1英寸卖1块2英寸卖5块但3英寸可能只卖8块因为客户需求不同。你的切割机可以无成本地将钢条切成任意整数英寸的段。问题是怎么切才能让这根钢条卖出的总价钱最高这听起来像个简单的算术题对吧但当你真正去尝试时会发现事情没那么简单。比如钢条长度 n4价格表如下长度 i1234价格 p[i]1589最笨的办法是什么我们称之为“暴力枚举”。长度为4的钢条它的切割方案其实对应着整数4的“分割”方式。比如不切4切成13切成22切成112切成1111。我们分别计算不切收益 r p[4] 9切成13收益 r p[1] p[3] 1 8 9切成22收益 r p[2] p[2] 5 5 10切成112收益 r p[1] p[1] p[2] 1 1 5 7切成1111收益 r 4 * p[1] 4显然最优方案是切成两段2英寸的收益为10。这个方法在n很小的时候可行。但你想过没有当n30时分割方案的数量是一个天文数字具体是2^(n-1)量级。你的计算机就算跑冒烟了也算不完。这就是所谓的“组合爆炸”也是很多优化问题直接求解的噩梦。而动态规划就是用来优雅地解决这类噩梦的。它的核心思想极其朴素就两点1. 记住你已经算过的东西避免重复计算2. 把大问题拆成小问题并找到它们之间的联系。听起来是不是有点像“分治法”没错但动态规划多了一个“记笔记”的步骤正是这一步让它从理论走向了实用。对于钢条问题动态规划是这么思考的我们定义 r[n] 为长度为 n 的钢条能获得的最大收益。那么对于这根钢条我们第一次切割可以切下长度为 i (1 i n) 的一段。切下这一段后我们立刻获得收益 p[i]剩下的钢条长度是 n-i。而剩下这部分钢条的最大收益是多少没错就是 r[n-i]因为我们定义 r[k] 就是长度为k时的最优解。于是我们得到了一个关系式r[n] max(p[i] r[n-i])其中 i 从1遍历到 n。这个式子就是“状态转移方程”是整个动态规划的灵魂。它告诉我们要算 r[n]你需要知道所有更短的 r[k] (k n)。这自然引导我们从小往大算先算 r[1]很简单就是不切r[1]p[1]1再算 r[2]比较不切、和切11两种情况然后算 r[3], r[4]…… 在算 r[4] 的时候我们查一下之前算好的 r[1], r[2], r[3] 的值就行了完全不需要重新枚举所有分割方案。注意这里有一个初学者极易混淆的点。在状态转移方程 r[n] max(p[i] r[n-i]) 中右边的 r[n-i] 代表的是“剩下部分的最优解”。这意味着我们在求解 r[n] 时默认了子问题 r[n-i] 已经以一种最优的方式被求解了。这个假设被称为“最优子结构”是动态规划能成立的前提。你必须确保你的问题具备这个性质否则动态规划不适用。你看通过“记笔记”用一个数组r记录所有子问题的解和“找关系”状态转移方程我们把一个指数级复杂度的问题变成了一个大概只需要 O(n²) 次计算的问题对于每个n遍历i从1到n。当n30时这只需要几百次计算瞬间搞定。这就是动态规划的魅力。它不产生新的魔法只是用一种聪明的方式避免了愚蠢的重复劳动。在数学建模中无论是资源分配、路径规划、生产调度还是投资组合只要你发现这个问题可以“分阶段”决策并且“这一阶段的最优选择能基于之前阶段的状态来决定”那么动态规划很可能就是你的菜。接下来的内容我们就深入这个“菜园”看看里面到底有哪些宝贝以及怎么才能把它们端上数学建模的餐桌。2. 动态规划的三要素与两大“门派”自顶向下 vs. 自底向上在真正动手用动态规划解题之前我们必须把它的“家规”搞清楚。很多人代码写不出来根本原因是对动态规划的基本要素理解模糊。动态规划能解决的问题通常具备三个核心特征缺一不可。2.1 动态规划成立的三个基石第一最优子结构。这是动态规划的“灵魂假设”。它意味着一个问题的最优解包含了其子问题的最优解。就像上面的钢条切割长度为n的钢条的最优切割方案必然由第一次切割后两段钢条的各自最优切割方案组成。如果子问题不是最优的那么你拼凑出来的大问题解也不可能最优。用反证法很容易理解如果大问题最优但它的一个子问题解不是最优那么我换一个更优的子问题解就能得到一个更好的大问题解这就矛盾了。在建模时你需要向评委或读者证明至少是说明你的问题具备这个性质。例如在最短路径问题中从A到C的最短路径如果经过B那么这条路径上从A到B的段落也必然是A到B的最短路径。第二重叠子问题。这是动态规划“省时间”的关键。它指的是在递归求解过程中不同的决策路径会反复遇到相同的子问题。比如在计算斐波那契数列 F(5) F(4) F(3) 时计算 F(4) 需要 F(3) 和 F(2)计算 F(3) 又需要 F(2) 和 F(1)。你看F(2) 被计算了多次。如果不用动态规划“记笔记”这种重复计算会浪费大量时间。重叠子问题性质决定了我们有必要把子问题的解存起来。第三无后效性。这个性质保证了“历史”对“未来”决策的影响已经完全体现在当前的“状态”里了。未来的决策只依赖于当前的状态而与如何到达这个状态的路径无关。比如在爬楼梯问题每次走1或2阶问上n阶有多少种方法中当你站在第k阶台阶上时你走到这里之前是两步两步上来的还是一步一步上来的完全不影响你后续走到第k1或k2阶的方法数。你当前的状态位置k包含了所有对未来有用的信息。很多同学在建模时构造的状态不具备无后效性导致方程写不出来。比如如果一个问题的收益不仅取决于当前资源量还取决于之前资源的消耗顺序那这个“顺序”就必须作为状态的一部分否则就违反了无后效性。2.2 两大实现“门派”记忆化搜索与递推理解了三大要素我们来看看怎么把它变成代码。主流有两种实现方式我习惯称它们为两大“门派”各有优劣。门派一自顶向下的记忆化搜索这种方法最符合人类的直觉思维。它就是直接按照问题的原始定义写出一个递归函数。比如求钢条切割最大收益cut_rod(n)。def cut_rod(n, price): if n 0: return 0 max_val -float(inf) for i in range(1, n1): max_val max(max_val, price[i] cut_rod(n-i, price)) return max_val但这就是最开始的暴力递归效率极低。记忆化搜索的精髓在于我们加一个“备忘录”通常是一个数组或字典在每次计算cut_rod(k)之前先查一下备忘录里有没有已经算好的结果有就直接返回没有才计算并在计算后存入备忘录。def cut_rod_memo(n, price, memo): if n 0: return 0 if memo[n] is not None: # 查备忘录 return memo[n] max_val -float(inf) for i in range(1, n1): max_val max(max_val, price[i] cut_rod_memo(n-i, price, memo)) memo[n] max_val # 存备忘录 return max_val # 初始化备忘录长度为n1用None表示未计算 memo [None] * (n1) result cut_rod_memo(n, price, memo)优点思路直观代码几乎就是状态转移方程的直接翻译写起来不容易错。按需计算只计算实际被递归调用到的子问题如果某些子问题不会被用到就不会浪费时间去算。在某些状态空间很大的问题中这可能节省大量时间。缺点递归开销递归调用有函数调用的开销如果递归深度很大比如n上万可能会导致栈溢出尽管Python等语言递归深度有限通常1000左右。代码稍慢递归调用比循环慢一些。门派二自底向上的递推表格法这是更经典、更教科书式的动态规划实现。我们明确地定义一张表格通常是数组dp[]并规定dp[i]的含义状态。然后我们从最小的、边界已知的子问题开始通过循环一步步递推出更大问题的解。对于钢条切割我们定义dp[i]为长度为i的钢条的最大收益。初始化dp[0] 0长度为0收益为0。递推顺序我们从小到大计算i从1到n。状态转移对于每个i我们枚举第一次切割的长度j(1 j i)dp[i] max(price[j] dp[i-j])。def cut_rod_dp(n, price): dp [0] * (n1) # dp[0]已经初始化为0 for i in range(1, n1): # 计算长度从1到n的钢条 max_val -float(inf) for j in range(1, i1): # 枚举第一刀切多长 max_val max(max_val, price[j] dp[i-j]) dp[i] max_val return dp[n]优点效率高纯粹的循环没有递归调用开销运行速度快。结构清晰表格dp清晰地展示了所有子问题的解有时方便我们回溯找出具体的最优方案比如具体怎么切的。避免栈溢出适合处理大规模问题。缺点可能计算冗余会计算出所有子问题的解即使有些解最终用不上。需要确定计算顺序你必须保证在计算dp[i]时它所依赖的dp[i-j]都已经计算好了。这在一些复杂问题比如状态有多个维度中需要仔细设计循环顺序。实操心得在数学建模竞赛中我强烈推荐优先使用自底向上的递推法。原因有三一是代码更简洁运行更稳定不容易出现递归深度问题二是最终的dp数组本身可能就是论文中需要展示的中间结果或图表数据来源三是当题目需要你输出具体方案不仅是最优值时从填好的dp表回溯比从递归函数回溯更直观。当然如果你一开始对状态转移关系想不清楚可以先用记忆化搜索的思路把方程写出来再转化为递推代码这是一个很好的调试和思维过渡方法。3. 背包九讲先吃透这两个经典模型0-1背包与完全背包动态规划的应用千变万化但“背包问题”是其最典型、也最常被考到的模型。网上有“背包九讲”这样的经典资料但对于数学建模入门而言你不需要一开始就啃下所有。只要彻底理解0-1背包和完全背包这两个核心模型你就能解决竞赛中一大半的资源分配类问题。它们的区别就藏在一个看似微小的细节里。3.1 0-1背包每个物品只能选一次问题描述有一个容量为V的背包和N件物品。第i件物品的体积是v[i]价值是w[i]。每件物品只能选择一次要么放要么不放。问在不超过背包容量的前提下能装入物品的最大总价值是多少这像极了数学建模中的资源分配问题有限的预算背包容量多个投资项目物品每个项目有成本体积和预期收益价值且每个项目最多投资一次0-1选择。比如国家科研基金分配、公司广告投放渠道选择等。状态定义这是最关键的一步。我们定义dp[i][j]表示只考虑前i件物品物品编号从1到i在背包容量恰好为j时能获得的最大价值。这里“恰好为j”的定义有时会让初学者困惑另一种更常见的定义是“容量不超过j”两者在初始化上稍有不同但核心转移思想一致。我们采用“恰好”的定义因为它更严谨且在需要恰好装满的问题中直接适用。状态转移方程对于第i件物品我们只有两种选择不放入背包那么问题就转化为“只考虑前 i-1 件物品容量为 j 时的最大价值”即dp[i-1][j]。放入背包前提是j v[i]放入后背包容量减少v[i]价值增加w[i]。问题转化为“只考虑前 i-1 件物品容量为j - v[i]时的最大价值”再加上w[i]即dp[i-1][j - v[i]] w[i]。我们要的是最大价值所以在这两种选择中取最大值dp[i][j] max(dp[i-1][j], dp[i-1][j - v[i]] w[i])当j v[i]时 如果j v[i]物品根本放不下则dp[i][j] dp[i-1][j]。初始化dp[0][0] 0表示考虑0个物品、容量为0时价值为0。对于其他j 0dp[0][j] -inf负无穷因为用0个物品无法凑出任何大于0的容量在“恰好”定义下这是一个非法状态。如果定义是“不超过”则dp[0][j] 0。代码实现二维数组def zero_one_pack(N, V, v, w): # 初始化dp数组 dp[i][j] dp [[-float(inf)] * (V1) for _ in range(N1)] dp[0][0] 0 for i in range(1, N1): # 遍历物品 for j in range(0, V1): # 遍历容量 # 不选第i件物品 dp[i][j] dp[i-1][j] # 如果能选第i件物品则尝试选 if j v[i]: dp[i][j] max(dp[i][j], dp[i-1][j - v[i]] w[i]) # 最终答案是 dp[N][0...V] 中的最大值因为容量不一定恰好用完 return max(dp[N])空间优化滚动数组 仔细观察转移方程dp[i][j]只依赖于dp[i-1][...]即上一行的数据。那么我们完全可以只用一维数组dp[j]来表示“当前考虑物品时容量为j的最大价值”。但这里有一个至关重要的细节内层循环遍历容量j必须从大到小遍历从V到0。def zero_one_pack_opt(N, V, v, w): dp [-float(inf)] * (V1) dp[0] 0 # 容量为0时价值为0 for i in range(1, N1): # 遍历物品 for j in range(V, v[i]-1, -1): # 关键从容量的最大值倒序遍历到v[i] # 此时的dp[j]相当于旧的dp[i-1][j] dp[j-v[i]]相当于旧的dp[i-1][j-v[i]] dp[j] max(dp[j], dp[j - v[i]] w[i]) return max(dp)为什么必须倒序因为我们要保证在更新dp[j]时dp[j - v[i]]还是“上一轮”i-1时的值。如果正序遍历当更新到dp[j]时dp[j - v[i]]可能已经在同一轮i时被更新过了这就相当于同一件物品被考虑了多次违背了0-1背包“每个物品仅一次”的规则。这个细节是面试和笔试的常考点务必理解。3.2 完全背包每个物品可以选无限次现在把问题改一下每种物品有无限件。这就是完全背包。这对应着可以重复投资的项目或者原材料可以无限采购的场景。状态定义可以和0-1背包一样dp[i][j]。但转移方程不同了。对于第i件物品我们可以选择放0件、1件、2件……直到放不下为止。dp[i][j] max(dp[i-1][j], dp[i-1][j - v[i]] w[i], dp[i-1][j - 2*v[i]] 2*w[i], ...)这样需要多一层循环枚举件数k复杂度是O(NVΣ(V/v[i]))效率不高。我们观察一下有没有更优的转移考虑dp[i][j]和dp[i][j - v[i]]的关系。dp[i][j] max( 不选i: dp[i-1][j], 至少选一件i: dp[i][j - v[i]] w[i] )这个“至少选一件i”的选项很有意思dp[i][j - v[i]]表示在容量为j-v[i]时仍然考虑前i件物品注意第一个维度是i不是i-1的最优解。这个解里可能已经包含了若干件第i个物品了我再加一件i就相当于在dp[i][j - v[i]]的基础上又多放了一件i。这样就巧妙地涵盖了放任意多件第i个物品的情况。所以完全背包的转移方程为dp[i][j] max(dp[i-1][j], dp[i][j - v[i]] w[i])当j v[i]时空间优化一维数组 同样可以用一维数组优化。而这里内层循环遍历容量j必须从小到大遍历从0到V。def complete_pack_opt(N, V, v, w): dp [0] * (V1) # 完全背包通常定义“不超过”初始化为0即可 for i in range(1, N1): for j in range(v[i], V1): # 关键从容量的最小值v[i]正序遍历到V dp[j] max(dp[j], dp[j - v[i]] w[i]) return dp[V]为什么这里是正序因为我们需要在更新dp[j]时dp[j - v[i]]已经是本轮更新过的值。这正好符合完全背包“物品无限”的特性我可以基于已经放过当前物品的状态再放一个。核心对比与记忆技巧0-1背包物品唯一一维优化下容量j倒序循环。可以理解为“为了不让当前物品重复使用必须用上一轮未更新的状态”。完全背包物品无限一维优化下容量j正序循环。可以理解为“允许当前物品重复使用所以可以用本轮已更新的状态”。 这个“正序/倒序”的区别是背包问题的精髓也是区分两类问题的代码标志。在数学建模中你首先要判断题目属于哪种类型然后套用对应的循环顺序。4. 最长上升子序列理解“状态”设计的艺术背包问题教我们如何定义“容量”状态。而“最长上升子序列”问题则展示了另一种经典的状态设计思路以某个元素为结尾。这个问题在序列分析、数据预测等建模场景中非常常见。问题描述给定一个长度为n的整数序列nums找到其中最长的严格递增子序列的长度。子序列不要求连续。例如[10, 9, 2, 5, 3, 7, 101, 18]的最长上升子序列是[2, 3, 7, 101]长度为4。最直接的暴力方法是枚举所有子序列判断是否上升复杂度是O(2^n)不可行。动态规划如何思考状态定义我们定义dp[i]表示以第i个元素nums[i]为结尾的最长上升子序列的长度。注意这个定义强制了子序列的最后一个元素必须是 nums[i]。为什么要这么定义因为这样我们才能建立子问题之间的联系。状态转移方程对于位置i我们想知道dp[i]是多少。以nums[i]结尾的上升子序列它的前一个元素可能是nums[0], nums[1], ..., nums[i-1]中的任何一个只要那个元素比nums[i]小。所以我们需要检查所有j i 如果nums[j] nums[i]那么nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的子序列其长度为dp[j] 1。 我们要找的是其中最长的那个所以dp[i] max(dp[j] 1)对于所有j i且nums[j] nums[i]。 如果不存在这样的j即nums[i]比前面所有数都小那么以它结尾的子序列就是它自己长度为1。所以我们需要初始化所有dp[i] 1。计算过程我们从小到大计算i从 0 到 n-1。对于每个i我们都遍历所有j i来更新dp[i]。def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n # 每个元素本身至少是一个长度为1的子序列 max_length 1 for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) max_length max(max_length, dp[i]) # 随时更新全局最大值 return max_length这个算法的时间复杂度是 O(n²)空间复杂度 O(n)。对于 n 在 10^4 量级以内的问题这个解法是可行的。优化思路贪心二分查找 当 n 很大比如 10^5时O(n²) 的算法会超时。有一个更优的 O(n log n) 的解法它虽然不是纯动态规划但思想非常巧妙在建模中如果遇到数据量大的序列问题这个优化是必须掌握的。我们维护一个数组tailstails[k]的值代表长度为 k1 的所有上升子序列中结尾元素的最小值。这个数组本身是严格递增的为什么因为更长的子序列它的结尾元素不可能比更短的子序列的结尾元素小。遍历原数组nums的每个元素x如果x大于tails中的所有元素即大于最后一个元素说明我们可以得到一个更长的上升子序列将x追加到tails末尾。否则我们在tails数组中二分查找第一个大于等于x的元素的位置i并用x替换tails[i]。这意味着我们找到了一个结尾元素更小的、长度为i1的上升子序列。最终tails的长度就是最长上升子序列的长度。def length_of_lis_nlogn(nums): tails [] for num in nums: # 二分查找左边界在tails中找到第一个 num 的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid # 如果left等于tails长度说明num比所有结尾都大 if left len(tails): tails.append(num) else: tails[left] num return len(tails)这个算法为什么正确替换操作tails[i] x并不会改变当前tails数组的长度即当前找到的最长上升子序列长度但它让未来有机会构造出更长的子序列的可能性增大了因为结尾元素变小了后面更容易接上更大的数。这是一种贪心策略。建模中的应用与扩展 “以i结尾”这种状态设计是处理序列相关问题的法宝。比如最大子数组和dp[i]表示以nums[i]结尾的最大子数组和转移方程dp[i] max(nums[i], dp[i-1] nums[i])。最长公共子序列状态定义为dp[i][j]表示字符串A前i个字符和字符串B前j个字符的LCS长度。编辑距离状态定义为dp[i][j]表示将单词A的前i个字符转换为单词B的前j个字符所需的最少操作数。 在数学建模中如果你遇到的时间序列数据需要找规律、做匹配、计算相似度不妨想想能不能定义类似的状态。例如在分析股票价格序列中“最长上涨波段”或者在地震波形数据中匹配特定模式其底层思想都是相通的。5. 从理论到实践数学建模中动态规划的完整工作流了解了经典模型我们最后来串讲一下在数学建模竞赛有限的几天时间里如何系统化地应用动态规划解决问题。这不仅仅是一个算法步骤更是一个从问题理解到论文呈现的完整工作流。5.1 第一步问题识别与抽象——这真的是个DP问题吗拿到赛题不要一看到“最优”、“最大”、“最小”就想着用动态规划。首先问自己几个问题问题能否被分解为多个阶段比如时间顺序第1天、第2天…、空间顺序从左到右、从上到下、决策顺序先决定A再决定B。每个阶段是否有若干种状态比如在资源分配中状态就是剩余的资源量在路径规划中状态就是当前所在的位置。当前阶段的决策是否只依赖于当前状态而与如何到达此状态无关无后效性整体最优解是否由相关子问题的最优解构成最优子结构如果以上答案都是“是”那么动态规划就是一个强有力的候选工具。例如2023年国赛A题“定日镜场优化设计”中虽然主体是模拟和优化算法但在对单个定日镜的跟踪控制进行离散时间步长下的能耗优化时就可以建模为一个多阶段决策问题每个阶段时刻的状态是镜子的角度和角速度决策是施加的扭矩目标是最小化总能耗这便是一个动态规划问题。5.2 第二步状态设计与转移方程——找到“状态变量”是关键这是动态规划最难也最核心的一步。状态设计没有万能公式但有常用套路线性/序列问题常用“以第i个元素结尾”的状态如LIS、最大子数组和。背包/资源分配问题状态中一定有一维或多维表示“剩余资源量”如背包容量、剩余资金、剩余时间。网格/路径问题状态通常是二维坐标(i, j)表示走到网格的(i, j)位置。复杂问题状态可能需要多个维度。例如在带时间窗的车辆路径问题中状态可能是(当前城市, 已访问城市集合, 当前时间)。状态空间会非常大这时可能需要结合状态压缩用二进制位表示集合等技巧。一个实用技巧先想一个最简单的暴力搜索函数dfs(状态)这个函数的参数就是你的“状态”返回值是在这个状态下能达到的最优值。然后这个函数内部的递归调用关系就是你的状态转移方程。最后把这个递归函数“翻译”成递推的dp数组。5.3 第三步确定边界与计算顺序——填表法的艺术状态方程写出来后要明确边界条件最小、最初的那些子问题的解是什么通常是dp[0]、dp[0][0]或者dp[i][0]、dp[0][j]。这些是递推的起点必须手动初始化正确。计算顺序计算dp[i][j]时它所依赖的子问题比如dp[i-1][j],dp[i][j-1]必须已经计算出来。这决定了你的循环嵌套顺序。对于二维DP常见的顺序有从上到下、从左到右或者按照阶段第一维顺序计算。在背包问题中我们看到了顺序正序/倒序对问题本质的影响。5.4 第四步编程实现与调试——从伪代码到可运行代码在建模环境中通常是MATLAB或Python将上述思路转化为代码。Python使用列表list或NumPy数组来存储dp表。注意Python的列表索引从0开始而我们的状态定义常常从1开始可以在列表前补一个0号元素来对齐避免思维混乱。MATLAB使用矩阵注意MATLAB索引从1开始这有时反而更符合我们的思维习惯。但要注意矩阵操作的性能避免在循环中频繁重塑矩阵。调试建议从小例子开始用题目给的样例或者自己构造的极小规模数据比如n3,4手动模拟dp表的填充过程再与程序输出对比。打印中间状态在循环中打印关键的dp值看是否符合预期。验证边界特别注意边界情况n0, n1容量为0等程序是否能正确处理。5.5 第五步结果分析与论文撰写——如何优雅地呈现你的DP模型动态规划模型在论文中需要清晰、严谨地呈现。模型叙述部分定义符号清晰定义所有变量、下标、集合。例如设dp[i][j]表示在前i个项目中总预算不超过j万元时的最大综合效益。阐述状态与决策说明“状态”是什么“决策”是什么。例如“本阶段的状态为剩余预算和当前考虑的项目索引。决策为是否投资当前项目。”给出状态转移方程用数学公式清晰地写出方程并配以文字解释。这是模型的核心务必突出。说明边界条件与目标函数写出初始状态如何赋值最终要输出的答案是什么例如max(dp[N][*])或dp[N][V]。算法描述部分可以用伪代码或流程图来描述自底向上的填表过程。伪代码要简洁突出循环结构和转移方程。说明算法的时间复杂度和空间复杂度。例如“该动态规划算法需要填充一个(N1) x (V1)的表格故时间复杂度为 O(NV)空间复杂度通过滚动数组优化可降至 O(V)。在本题数据规模下N100, V10000可以在1秒内完成计算。” 这展示了你对算法效率的把握。结果分析部分不仅给出最终的最优值如果可能回溯出最优方案。例如在背包问题中可以从dp[N][V]倒推根据状态转移的选择记录下具体选了哪些物品。这比单纯一个数字更有说服力。可以展示关键的中间结果表格dp表的一部分作为佐证但不必全部粘贴选取有代表性的片段即可。进行灵敏度分析。这是建模论文的加分项。例如改变背包容量V资源总量观察最优值的变化趋势并分析其经济学或管理学含义。或者分析某个关键参数如物品价值的波动对最终方案稳定性的影响。动态规划不是银弹但它是一把极其锋利的刀。当你面对一个具有重叠子问题和最优子结构的最优化问题时熟练地运用动态规划往往能为你劈开一条通往简洁优美解法的道路。它的思想——以空间换时间记录过去以避免未来重复劳动——其意义甚至超越了算法本身成为一种重要的思维方式。在数学建模这场智力与时间的赛跑中掌握动态规划无疑是为自己装备了一个强大的加速器。