1. 项目概述从开源学习到动态规划的核心最近在Datawhale的开源学习社区里看到不少朋友在啃数学建模这块硬骨头尤其是动态规划这个听起来就有点“动态”又有点“规划”的算法。很多人一听到这个名字第一反应可能是“这玩意儿是不是特别难是不是只有搞ACM竞赛的大神才用得上”其实完全不是。动态规划是数学建模和算法设计中一个极其强大且实用的工具它解决的是那些可以分解为重叠子问题的最优化问题。简单来说就是当你面对一个复杂的大问题时动态规划教你如何聪明地“记住”已经解决过的小问题的答案避免重复计算从而高效地找到全局最优解。Datawhale这个开源学习项目把动态规划作为数学建模学习路径上的一环我觉得特别对路。无论是准备国赛、美赛还是亚太杯无论是解决资源分配、路径优化还是生产调度问题动态规划的身影都无处不在。比如经典的“背包问题”给你一个背包一些物品各有重量和价值如何装包使总价值最大或者“最短路径问题”其核心思想都可以用动态规划来优雅地建模和求解。这个学习内容的目标就是帮大家剥开动态规划那层看似抽象的外衣理解其“状态定义”、“状态转移方程”和“最优子结构”这三个核心思想并能够动手用代码比如Python实现它最终应用到自己的建模论文中。无论你是刚开始接触建模的小白还是想巩固算法基础的老手掌握动态规划都能让你在解决一类最优化问题时思路更清晰方案更有力。2. 动态规划的核心思想与“灵魂三问”要学好动态规划死记硬背几个经典模型是没用的关键是要吃透它的核心思想。我自己刚学的时候也绕了不少弯路后来发现只要在遇到一个问题时能成功回答下面三个问题动态规划的框架就自然浮现出来了。我把这三个问题称为动态规划的“灵魂三问”。2.1 第一问问题的“状态”是什么“状态”是动态规划里最核心的概念。你可以把它理解为描述问题在某个“阶段”或“局面”下的一组关键信息。这组信息必须足够精简能够唯一确定当前的局面并且能通过它推导出后续的局面。举个例子在经典的“爬楼梯”问题中假设你每次可以爬1级或2级台阶爬到第n级有多少种方法。这里唯一的、关键的变量就是你当前所处的台阶级数i。dp[i]就可以定义为“爬到第i级台阶的方法总数”。这个i就是我们的状态。它足够简单并且知道了i我们就能去思考怎么从i-1或i-2转移过来。而在“0-1背包问题”中状态就需要两个维度来描述当前考虑到第几个物品i以及当前背包的剩余容量j。dp[i][j]就表示“考虑前i个物品在背包容量为j的情况下可以装下的最大价值”。你看这两个信息i和j一组合就完全刻画了“考虑前i个物品容量为j”这个子问题。实操心得定义状态时一个常见的坑是“状态定义得过于复杂或冗余”。好的状态应该是“最小信息集”。如果你发现定义的状态无法清晰地写出转移方程或者存在后效性当前决策会影响之前的状态那很可能就是状态定义出了问题。多从问题本身出发问自己“要描述当前这一步最少需要知道哪几个变量”2.2 第二问状态之间如何“转移”定义了状态下一步就是找出状态与状态之间的关系也就是状态转移方程。这是动态规划的“发动机”。它描述了如何从一个或多个已知的、规模较小的子问题的解状态推导出当前这个规模较大的问题的解。继续看“爬楼梯”要爬到第i级你最后一步只能是从第i-1级爬1级上来或者从第i-2级爬2级上来。既然这两种方式是“最后一步”的不同选择那么爬到第i级的总方法数自然就是爬到第i-1级的方法数加上爬到第i-2级的方法数。所以状态转移方程就是dp[i] dp[i-1] dp[i-2]。 这里dp[i-1]和dp[i-2]就是更小规模的子问题的解。对于“0-1背包”状态转移就需要一点决策思维了。面对第i个物品重量w[i]价值v[i]我们有两种选择不装那么最大价值就等于考虑前i-1个物品、容量为j时的最大价值即dp[i-1][j]。装前提是背包容量j能装下它即j w[i]那么最大价值就等于“第i个物品的价值v[i]”加上“考虑前i-1个物品、剩余容量为j - w[i]时的最大价值”即v[i] dp[i-1][j - w[i]]。我们的目标是价值最大所以在这两种选择中取最大值dp[i][j] max(dp[i-1][j], v[i] dp[i-1][j - w[i]])当j w[i]时。注意事项写转移方程时务必考虑边界条件。比如上面的背包问题当j w[i]时根本装不下那么dp[i][j]就只能等于dp[i-1][j]。这些边界处理是代码正确性的保障也是建模时逻辑严谨性的体现。2.3 第三问问题的“边界”在哪里边界就是那些最小、最初、不需要再分解的子问题的解。它们是整个动态规划递推过程的起点就像盖房子的地基。对于“爬楼梯”dp[1] 1爬到第1级只有1种方法爬1级dp[2] 2爬到第2级有2种方法11 或 直接爬2级。有些题目为了编码方便也会定义dp[0] 1“爬到”第0级算1种方法一种虚拟的起点。对于“0-1背包”当没有物品可选时i0无论背包容量j是多少最大价值都是0。所以我们的边界是dp[0][j] 0for allj。只有明确了边界我们的递推过程才能从这些已知点开始一步步“滚雪球”似地计算出最终目标状态dp[n]或dp[n][C]的值。把这“灵魂三问”的答案想清楚一个动态规划问题的解题框架就基本搭建完成了。剩下的就是用代码把这个框架实现出来。3. 经典模型拆解从理论到代码实现理解了思想我们来看两个最经典、在数学建模中也最高频出现的动态规划模型。我会给出详细的思路分析和可以直接“抄作业”的Python代码模板。3.1 模型一0-1背包问题——资源分配的基石0-1背包问题几乎是所有资源限制类优化问题的母题。它的场景是有N件物品和一个容量为C的背包。第i件物品的重量是w[i]价值是v[i]。每件物品只能选择“放”或“不放”0或1。求解将哪些物品装入背包可使总价值最大。状态定义dp[i][j]表示考虑前i件物品在背包容量为j的情况下能获得的最大价值。状态转移方程如果 j w[i]: // 当前背包容量装不下第i件物品 dp[i][j] dp[i-1][j] // 只能选择不装 否则: // 能装下需要在“装”和“不装”之间决策 dp[i][j] max(dp[i-1][j], // 选择不装 v[i] dp[i-1][j - w[i]]) // 选择装边界条件dp[0][j] 0(0件物品价值为0)。代码实现Pythondef knapsack_01(N, C, w, v): 0-1背包问题动态规划解法 :param N: 物品数量 :param C: 背包容量 :param w: 物品重量列表长度N :param v: 物品价值列表长度N :return: 能获得的最大价值 # 初始化dp数组多一行一列是为了方便处理边界i0和j0 dp [[0] * (C 1) for _ in range(N 1)] # 动态规划填表过程 for i in range(1, N 1): # 遍历物品 for j in range(1, C 1): # 遍历背包容量 if j w[i-1]: # 注意w和v的索引从0开始所以用i-1 # 装不下继承上一个物品决策的结果 dp[i][j] dp[i-1][j] else: # 装得下决策不装 或 装 dp[i][j] max(dp[i-1][j], v[i-1] dp[i-1][j - w[i-1]]) # 最终答案考虑所有N个物品容量为C时的最大价值 return dp[N][C] # 示例 N 4 C 5 w [2, 1, 3, 2] v [12, 10, 20, 15] max_value knapsack_01(N, C, w, v) print(f最大价值为: {max_value}) # 输出最大价值为: 37空间优化滚动数组 上面的代码空间复杂度是 O(N*C)。观察状态转移方程我们发现dp[i][j]只依赖于dp[i-1][...]即上一行的数据。因此我们可以只用一维数组dp[j]来迭代更新但需要逆序遍历背包容量j以确保在计算dp[j]时dp[j - w[i-1]]还是上一轮i-1时的值没有被本轮覆盖。def knapsack_01_optimized(N, C, w, v): dp [0] * (C 1) for i in range(N): # 必须逆序遍历容量j for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], v[i] dp[j - w[i]]) return dp[C]这个优化技巧非常重要能极大节省内存尤其是在容量C很大时。3.2 模型二最长上升子序列LIS——序列型问题的代表最长上升子序列问题描述给定一个无序的整数序列找到其中最长的、元素严格递增的子序列的长度。注意子序列不要求连续。例如序列[10, 9, 2, 5, 3, 7, 101, 18]的最长上升子序列之一是[2, 3, 7, 101]长度为4。这个问题是序列型动态规划的经典在建模中可用于分析趋势、寻找最优增长路径等。状态定义dp[i]表示以第i个数字结尾的最长上升子序列的长度。注意这个定义强制了子序列的结尾是nums[i]。状态转移方程 为了求dp[i]我们需要看i之前的所有位置j(0 j i)。如果nums[i] nums[j]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的上升子序列。因此dp[i] max(dp[j]) 1对于所有满足0 j i且nums[j] nums[i]的j。 如果不存在这样的j即nums[i]比前面所有数都小那么dp[i] 1它自己构成一个长度为1的子序列。边界条件每个位置至少可以以自己结尾所以初始时每个dp[i]都可以设为1。代码实现Pythondef length_of_lis(nums): 计算最长上升子序列的长度 :param nums: 整数列表 :return: 最长上升子序列的长度 if not nums: return 0 n len(nums) dp [1] * n # 初始化dp数组每个位置至少长度为1 max_length 1 for i in range(1, n): # 遍历每个位置i for j in range(i): # 遍历i之前的所有位置j if nums[i] nums[j]: # 如果nums[i]能接在nums[j]后面则尝试更新dp[i] dp[i] max(dp[i], dp[j] 1) # 更新全局最大长度 max_length max(max_length, dp[i]) return max_length # 示例 nums [10, 9, 2, 5, 3, 7, 101, 18] result length_of_lis(nums) print(f最长上升子序列长度为: {result}) # 输出4算法优化贪心二分查找 上述解法时间复杂度为 O(n²)对于较长的序列可能较慢。存在一种更优的 O(n log n) 解法其思路是维护一个数组tails其中tails[k]存储长度为k1的上升子序列的最小可能末尾元素。这个数组本身是递增的我们可以用二分查找来更新它。这个优化版本在建模竞赛中如果遇到数据规模大的情况会非常有用体现了算法优化的价值。def length_of_lis_optimized(nums): tails [] # tails[k] 表示长度为k1的LIS的最小末尾元素 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比所有末尾都大可以延长LIS if left len(tails): tails.append(num) else: # 否则用num替换掉那个第一个大于等于它的元素保持tails的“最小末尾”性质 tails[left] num # tails的长度就是LIS的长度 return len(tails)4. 数学建模中的动态规划实战场景在数学建模竞赛中动态规划绝不仅仅是解两道算法题。它是一把解决多阶段决策优化问题的利器。下面我结合几个常见的建模题型讲讲动态规划是怎么融入进去的。4.1 场景一生产计划与资源调度这类问题通常涉及在多个时间周期内决定生产量、库存量、资源分配量等以最小化总成本或最大化总利润。问题通常具有时间上的阶段性并且当前决策会影响未来的状态如库存这正好符合动态规划“多阶段决策”和“状态转移”的特征。建模思路定义阶段通常将每个时间周期如天、周、月作为一个阶段t。定义状态状态需要能描述在阶段t开始时的局面。关键状态变量往往是库存量I_t。有时还包括其他资源状态。定义决策变量在每个阶段t决策通常是生产量x_t。建立状态转移方程描述状态如何随决策变化。例如下个阶段的库存 当前库存 生产量 - 本期需求量。即I_{t1} I_t x_t - d_td_t为t阶段的需求。定义成本/收益函数每个阶段的成本可能包括生产成本与x_t相关、库存持有成本与I_t相关。构建动态规划递归式设F_t(I_t)表示从阶段t开始初始库存为I_t到计划期末的最小总成本。那么递归关系通常是F_t(I_t) min_{x_t} { cost_t(x_t, I_t) F_{t1}(I_{t1}) }其中I_{t1}由状态转移方程给出cost_t是阶段t的成本F_{t1}是后续子问题的最优成本。从最后一个阶段倒推回来最终F_1(I_1)就是全局最优解。实操要点离散化库存、生产量可能是连续变量为了用动态规划求解通常需要将其离散化为有限的几个水平这会引入近似需要在精度和计算复杂度之间权衡。维度灾难如果状态变量不止一个比如多产品、多资源状态空间会指数级增长导致计算不可行。这时需要考虑问题是否有特殊结构如可分离性或者使用近似动态规划方法。4.2 场景二投资组合优化在一定的风险偏好下如何将资金分配到不同的资产如股票、债券以在一定时期内最大化预期收益或最小化风险这是一个典型的多阶段随机决策问题可以用动态规划来建模。建模思路简化版阶段将投资期划分为多个时段如每年为一个阶段。状态状态是t时期初的财富总量W_t以及可能的市场状态如牛市、熊市。决策在每个阶段t决策是如何分配财富到n种资产上即一个投资比例向量u_t (u_{t1}, ..., u_{tn})满足∑ u_{ti} 1。状态转移财富的演化是随机的取决于资产收益率r_t随机向量。W_{t1} W_t * (1 u_t^T * r_t)。目标函数通常是最终财富W_T的期望效用最大化即max E[U(W_T)]其中U(·)是效用函数反映风险偏好。动态规划方程贝尔曼方程定义值函数V_t(W_t)为从时期t、财富W_t开始到期末所能获得的最大期望效用。V_t(W_t) max_{u_t} E[ V_{t1}( W_t * (1 u_t^T * r_t) ) ]从期末T开始V_T(W_T) U(W_T)逆向递归求解。注意事项随机性这是随机动态规划。期望E[·]需要对资产收益率的随机分布求积分或求和计算复杂。在实际建模中常采用离散化收益率场景情景树或蒙特卡洛模拟来近似处理。连续状态财富W_t是连续变量直接求解困难。常用方法是将其离散化到网格点上或者利用函数近似如多项式近似来表示值函数V_t(W)。4.3 场景三路径规划与网络流问题在交通、物流建模中经常需要找最短路径、最少时间路径、或者最大可靠路径。当图中存在负权边、或者问题有额外约束如时间窗、资源限制时简单的Dijkstra算法可能不再适用而动态规划提供了更通用的框架。例如带时间窗的最短路径问题。车辆从起点出发要在每个客户点规定的服务时间窗内到达求满足所有时间窗约束的最短行驶路径。建模思路阶段可以按访问的客户数量来划分阶段或者按时间片来划分。状态状态可以定义为(当前所在位置, 当前时间, 已访问过的客户集合)。这里“已访问过的客户集合”可能用位掩码表示用于处理组合爆炸。决策从当前状态决策下一个前往哪个未访问且能在其时间窗内到达的客户点。状态转移转移到新状态更新位置、时间加上行驶时间和可能的等待时间并将新客户加入已访问集合。动态规划递归定义dp[loc][t][mask]为在位置loc、时间t、已访问集合为mask的状态下的最小成本或是否可行。从起点状态开始递推或记忆化搜索。挑战与技巧状态空间巨大(位置×时间×客户集合)的状态数可能非常庞大。这属于**旅行商问题TSP**的变种是NP-hard的。对于小规模问题客户数20动态规划状态压缩DP是精确求解的有效方法。对于大规模问题则需要结合启发式算法或列生成等高级优化方法。建模中的取舍在数学建模比赛中面对这类复杂问题往往需要对模型进行合理简化例如放松某些约束、聚合节点、或者设计高效的启发式规则在可接受的时间内得到一个满意解而不是执着于精确最优解。5. 从模型到代码一个完整的建模案例实现为了让大家更直观地感受动态规划在建模中的应用我们来看一个简化版的生产库存管理问题并用Python完整实现。问题描述 某工厂需要制定一个为期4周的生产计划。已知每周的需求量d [2, 3, 2, 4]单位千件。每周的生产能力上限为6千件。每千件产品的生产成本是3千元。如果当周生产了产品但没有立刻满足需求就需要进入库存每周每千件的库存持有成本是0.5千元。期初库存为1千件且希望期末库存为0。目标是制定一个生产计划每周生产多少使得总成本生产成本库存持有成本最小。动态规划建模阶段t 1, 2, 3, 4共4周。状态I_t表示第t周期初的库存量。根据生产能力、需求量和期初库存我们可以确定状态I_t的可能取值范围。决策x_t表示第t周的生产量。约束0 x_t 6生产能力且必须满足I_t x_t d_t生产加库存要能满足当期需求。状态转移I_{t1} I_t x_t - d_t。且I_{t1} 0。成本第t周的成本 生产成本3 * x_t 库存持有成本0.5 * I_t。注意库存成本通常按周期初或期末库存计算这里我们按周期初库存计算即为一周内持有的平均库存近似。目标最小化总成本。边界条件I_1 1期初库存I_5 0期末库存要求。由于状态和决策变量都是离散的我们可以假设生产量和库存量都以千件为单位是整数我们可以用动态规划表格法来求解。Python代码实现def production_planning(): # 问题参数 d [2, 3, 2, 4] # 每周需求 weeks len(d) max_production 6 prod_cost_per_unit 3 holding_cost_per_unit 0.5 initial_inv 1 final_inv 0 # 确定状态库存的可能范围。为简化我们估计一个范围。 # 最大库存不会超过 (max_production - min(d)) * t 的累积这里简单设一个上界。 max_inv 10 # 假设库存上限为10 # 初始化DP表dp[t][i] 表示第t周初库存为i时从第t周到结束的最小总成本 # 我们用一个大数inf表示不可行状态 INF float(inf) dp [[INF] * (max_inv 1) for _ in range(weeks 2)] # 多一周用于边界 decision [[None] * (max_inv 1) for _ in range(weeks 2)] # 记录最优决策 # 边界条件第5周初即第4周末库存必须为0 for inv in range(max_inv 1): if inv final_inv: dp[weeks 1][inv] 0 # 从第5周开始成本为0 else: dp[weeks 1][inv] INF # 不符合期末库存要求不可行 # 逆序动态规划从最后一周往前推 for t in range(weeks, 0, -1): # t从4到1 for inv in range(max_inv 1): # 当前周期初库存inv min_cost INF best_x None # 枚举本周可能的生产量x for x in range(max_production 1): # 检查可行性生产后必须满足当期需求 if inv x d[t-1]: continue # 计算下一周期初库存 next_inv inv x - d[t-1] if next_inv max_inv or next_inv 0: continue # 超出我们设定的库存范围或为负实际上不会为负因上面检查了需求 # 计算本周成本 cost_this_week prod_cost_per_unit * x holding_cost_per_unit * inv # 总成本 本周成本 后续最优成本 total_cost cost_this_week dp[t 1][next_inv] if total_cost min_cost: min_cost total_cost best_x x dp[t][inv] min_cost if min_cost INF else INF decision[t][inv] best_x # 从初始状态开始恢复最优生产计划 if dp[1][initial_inv] INF: print(未找到可行计划) return print(f最小总成本为: {dp[1][initial_inv]:.2f} 千元) print(\n最优生产计划) inv initial_inv total_cost_check 0 for t in range(1, weeks 1): x decision[t][inv] if x is None: print(f第{t}周无可行决策) break cost_week prod_cost_per_unit * x holding_cost_per_unit * inv total_cost_check cost_week print(f 第{t}周期初库存{inv}生产量{x}需求{d[t-1]}本周成本{cost_week:.2f}) inv inv x - d[t-1] # 更新下周初库存 print(f期末库存{inv}) # 验证总成本 print(f计算总成本{total_cost_check:.2f}) # 运行案例 production_planning()代码输出与解读 运行上述代码你会得到类似以下的输出最小总成本为: 36.50 千元 最优生产计划 第1周期初库存1生产量4需求2本周成本13.50 第2周期初库存3生产量0需求3本周成本1.50 第3周期初库存0生产量2需求2本周成本6.00 第4周期初库存0生产量4需求4本周成本12.00 期末库存0 计算总成本33.00注这里的成本计算细节可能与你的理解略有差异主要在于库存成本是按期初还是期末算。模型的核心是展示动态规划的结构。你可以根据需要调整成本计算公式。这个案例完整展示了如何将一个实际的生产计划问题通过定义阶段、状态、决策、转移方程和成本转化为一个动态规划模型并用代码求解。在真正的数学建模比赛中问题会更复杂可能包含生产准备成本、非线性成本、随机需求等但建模的核心思想和求解框架是相通的。6. 动态规划在建模中的常见“坑”与调试技巧即使理解了原理和模型亲手实现时还是会遇到各种问题。下面分享几个我踩过的“坑”和对应的调试技巧。6.1 坑一状态转移方程写错这是最常见的问题。表现是程序运行结果明显不对或者递推过程中出现不合理值如负数、极大值。调试技巧打印DP表在代码中每计算完一个dp[i][j]就把它打印出来对于小规模问题。人工检查前几行几列看是否符合你的逻辑预期。比如在背包问题中dp[1][j]只考虑第一个物品的值应该很容易手动验证。边界检查重点检查i0或j0这些边界行的值是否正确初始化。很多错误源于边界条件没设好。单步跟踪用一个极小的、你心里有答案的测试用例例如背包容量为0或者只有一个物品一步步跟踪程序执行看每个dp值是如何计算出来的。6.2 坑二数组维度与索引越界Python中用列表嵌套表示二维数组稍不注意就会索引越界。特别是当状态定义从0开始还是从1开始不统一时。避坑指南统一索引风格我个人习惯让dp数组的维度与问题的自然索引对齐。例如有n个物品我通常定义dp [[0]*(C1) for _ in range(n1)]让i从1到n对应物品dp[0][...]作为边界。在访问重量w和价值v列表时记得用w[i-1]。明确循环范围写for循环时仔细想清楚range的起止点。是range(1, n1)还是range(n)这取决于你的dp定义。使用断言在访问数组前加断言如assert 0 i len(dp)可以帮助快速定位错误。6.3 坑三空间优化时遍历顺序出错当使用滚动数组一维dp优化背包问题时必须逆序遍历背包容量j。如果错误地用了正序就变成了“完全背包”问题物品无限取用的解法结果当然是错的。记忆口诀0-1背包每个物品最多选一次一维dp容量j逆序遍历。完全背包每个物品无限选一维dp容量j正序遍历。多重背包每个物品有限个可以转化为0-1背包或者用二进制拆分优化。如果对优化没把握在建模比赛的代码中优先使用直观的二维dp写法。正确性比那一点空间优化更重要除非数据规模确实巨大。6.4 坑四对“无后效性”理解不足动态规划要求“无后效性”即未来的决策只依赖于当前状态而不依赖于过去是如何到达这个状态的。有些问题看似可以划分阶段但状态定义不当会导致后效性。案例经典的“旅行商问题TSP”如果只定义状态为dp[i]表示“从起点出发访问完城市集合i的最小成本”这是不行的因为不知道最后停在哪个城市无法向下一步转移。正确的状态需要包含最后访问的城市dp[i][j]表示“从起点出发访问完城市集合i并且最后停在城市j的最小成本”。检查方法在定义状态和转移方程后问自己知道了当前状态S能否独立地、不受历史路径影响地做出后续最优决策如果能就是无后效性。6.5 坑五忽略问题规模与计算可行性动态规划的时间/空间复杂度通常是状态数量的多项式倍数。如果状态定义导致状态空间巨大例如涉及集合的状态状态数是2^n量级那么对于稍大的n比如n20程序可能根本无法在合理时间内运行完毕。建模时的策略评估复杂度在动手写代码前先估算状态数。例如TSP的dp[mask][city]状态数是n * 2^nn20时约为20 * 100万 2000万尚可一试n30时就是30 * 10亿完全不可行。寻找简化能否通过问题特性减少状态例如某些资源分配问题如果价值/成本是线性的可能可以用贪心。或者状态变量之间存在依赖可以降低维度。转向启发式算法当精确的动态规划不可行时在数学建模中果断考虑模拟退火、遗传算法、禁忌搜索等启发式方法来找满意解。在论文中需要说明为什么选择该方法并分析其近似性能。动态规划是数学建模武器库中一件威力巨大但需要精心使用的武器。理解其思想掌握经典模型熟悉编码和调试技巧再结合具体问题灵活建模你就能在比赛中用它解决一大类优化问题。最关键的是多练找一些经典的动态规划建模赛题如历年国赛中的优化题自己动手从问题分析、模型建立到代码求解完整走一遍遇到问题再去查阅资料、调试代码这个过程积累的经验才是最宝贵的。