1. 从“最优解”到“最优决策”动态规划的核心思想如果你参加过数学建模竞赛或者刷过一些算法题大概率对“动态规划”这四个字又爱又恨。爱的是一旦掌握了它很多看似复杂无比的问题都能迎刃而解代码简洁高效恨的是它的思维门槛不低状态转移方程常常让人抓耳挠腮。网上教程虽多但要么过于理论满篇数学公式要么过于零散只讲几个经典例题缺乏系统性的思维构建。这正是我当初学习时的痛点也是我决定整理这套“动态规划入门系列”的初衷。我不是什么学术大牛就是一个在数学建模和算法竞赛里摸爬滚打多年的“老手”网名“清风”。这套课程的目标很明确不讲虚的只讲干的用最直白的语言和最具代表性的案例带你从零搭建起动态规划的思维框架并直接应用到数学建模和实际问题中。动态规划到底是什么你可以把它理解为一种“聪明”的穷举法。它解决的是多阶段决策问题核心思想是“记住过去服务未来”。简单说就是把一个大问题分解成一系列小问题通过解决小问题并记录它们的答案即“状态”来避免重复计算最终高效地得到大问题的最优解。这听起来有点像“分治法”但关键区别在于动态规划分解出的子问题往往是重叠的而分治法的子问题通常是独立的。正是这种“重叠子问题”的特性使得“记忆化”缓存中间结果变得极具价值。另一个核心特性是“最优子结构”即一个问题的最优解包含了其子问题的最优解。这两个特性是判断一个问题能否用动态规划解决的黄金标准。这套课程将完全围绕这两个核心展开。我们会从最经典的“斐波那契数列”和“爬楼梯”问题入手让你直观感受什么是重叠子问题和记忆化搜索。然后我们会深入动态规划的两大实现范式自顶向下的记忆化搜索递归缓存和自底向上的递推迭代填表。很多人觉得后者才是“正统”的动态规划但我认为从前者的递归思维过渡更能理解状态转移的本质。之后我们将进入实战核心背包问题。从01背包到完全背包再到多重背包背包问题是理解状态定义和转移方程的绝佳练兵场。最后我们会将视角拉升探讨动态规划在序列问题如最长公共子序列、编辑距离、路径规划问题以及数学建模中的具体应用。我的目标是当你学完这个系列不仅能轻松应对力扣上的动态规划标签题更能在一道数学建模赛题面前敏锐地识别出其中隐藏的动态规划结构并自信地将其转化为模型。2. 动态规划的两大基石与思维起点2.1 重叠子问题从斐波那契数列看重复计算的代价让我们从一个老朋友开始斐波那契数列。它的定义是 F(0)0, F(1)1, F(n)F(n-1)F(n-2) (n2)。如果让你写一个递归函数来计算 F(5)你可能会这样想F(5) F(4) F(3)。那么就需要先算 F(4) 和 F(3)。计算 F(4) 又需要 F(3) 和 F(2)计算 F(3) 又需要 F(2) 和 F(1)…… 如果我们画出这个递归树会惊讶地发现F(3) 被计算了2次F(2) 被计算了3次F(1) 和 F(0) 被计算的次数更多。当 n 变大时这种重复计算是指数级增长的效率极低。这就是典型的“重叠子问题”。计算 F(n) 的过程中许多更小的 F(k) 被反复需求、反复计算。动态规划的第一个妙招就是解决这个问题记下来。我们开一个数组dpdp[i]表示 F(i) 的值。当我们第一次计算出dp[3]后就把它存起来。下次再需要 F(3) 时直接去数组里取而不是重新递归计算。这种方法被称为“记忆化搜索”Memoization它是自顶向下动态规划的雏形。通过一个简单的缓存我们就把时间复杂度从恐怖的 O(2^n) 降到了 O(n)。这个例子虽然简单但它揭示了动态规划最根本的动机通过空间换时间避免对相同子问题的重复求解。注意这里容易混淆两个概念——“记忆化搜索”和“动态规划”。在狭义上有些人认为只有自底向上的递推填表才是动态规划。但在更广义的算法思想层面自顶向下的记忆化搜索同样是动态规划思想的体现它更符合人类“分而治之”的直觉。在实际学习和解题中我强烈建议从记忆化搜索入手因为它能让你更专注于定义“状态”即dp[i]代表什么和“状态转移”即如何用已知状态求未知状态而不必一开始就纠结于循环的次序。2.2 最优子结构拼出最优解的积木如果说“重叠子问题”是动态规划的应用场景那么“最优子结构”就是动态规划能够正确工作的理论保证。它的意思是一个问题的最优解可以由其子问题的最优解有效地构造出来。我们用一个更实际的例子来说明“爬楼梯”问题。假设你正在爬楼梯需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶我们定义dp[i]为爬到第 i 阶楼梯的方法总数。那么思考最后一步要到达第 i 阶你只能从第 i-1 阶爬1步上来或者从第 i-2 阶爬2步上来。因此到达第 i 阶的方法数就等于到达第 i-1 阶的方法数加上到达第 i-2 阶的方法数。即dp[i] dp[i-1] dp[i-2]。看dp[i]这个“大问题”的最优解此处“最优”指所有可能的方法数完全由dp[i-1]和dp[i-2]这两个“子问题”的最优解决定。dp[i-1]本身必须是从起点到第 i-1 阶的所有方法数它不能再是某个更差的解否则拼出来的dp[i]就不是总方法数了。这就是最优子结构子问题的最优解是构建原问题最优解的基础。在背包问题、最短路径问题中这个特性更为明显。如果一个问题不具备最优子结构那么动态规划就无法应用。例如求图中最长简单路径不能重复经过节点就不具备最优子结构因为从A到C的最长路径可能不是由A到B的最长路径和B到C的最长路径简单拼接而成拼接后可能出现重复节点。2.3 状态定义一切思考的起点动态规划解题一半以上的精力都在于如何定义“状态”。状态就是我们用来描述子问题的变量。一个清晰、准确的状态定义直接决定了后续转移方程是否容易写出以及算法的效率。状态定义需要抓住问题的本质。通常状态需要包含足够的信息使得在已知状态下后续的决策可以独立进行而不需要回头查看历史。对于“爬楼梯”状态很简单就是一维的dp[i]表示到达第 i 阶的方案数。对于经典的“01背包问题”状态通常是二维的dp[i][j]表示考虑前 i 件物品在背包容量为 j 的情况下所能获得的最大价值。这里的i和j共同定义了一个子问题只处理前 i 个物品且容量限制为 j 时的情况。如何找到正确的状态定义我的经验是先问自己要解决的原问题是什么比如原问题是“用容量为V的背包装前N件物品的最大价值”。那么子问题自然就可以通过缩小规模来定义“用容量为j的背包装前i件物品的最大价值”。状态定义不是凭空想象的它是对原问题规模的一种参数化描述。一个实用的技巧是先尝试用最直观、最“暴力”的方式描述子问题哪怕维度很高。在后续优化中再观察状态转移方程看能否压缩状态维度例如01背包的dp数组可以从二维优化到一维。3. 背包问题动态规划的经典练兵场3.1 01背包拿与不拿的哲学01背包是动态规划入门无法绕开的里程碑。问题描述有N件物品和一个容量为V的背包。第i件物品的体积是v[i]价值是w[i]。每件物品只有一件可以选择放或不放。求解将哪些物品装入背包可使总价值最大。我们定义状态dp[i][j]为只考虑前 i 件物品在背包容量恰好为 j 的情况下能获得的最大价值。注意这里我强调“恰好”有些定义是“不超过”两者在初始化上略有不同“恰好”的定义有时更清晰。状态转移方程是核心dp[i][j] max(dp[i-1][j], dp[i-1][j - v[i]] w[i]) (当 j v[i]) dp[i][j] dp[i-1][j] (当 j v[i])这个方程需要彻底理解对于第i件物品我们只有两种选择。不拿那么最大价值就等于只考虑前i-1件物品、容量为j时的最大价值即dp[i-1][j]。拿前提是背包容量j能装下它j v[i]。如果拿我们需要先为第i件物品腾出空间v[i]。那么在拿它之前背包的状态应该是只考虑前i-1件物品、容量为j - v[i]时的最大价值即dp[i-1][j - v[i]]。然后加上第i件物品的价值w[i]就得到了拿它之后的总价值。我们的决策就是在这两者中取最大值。这个方程完美体现了最优子结构dp[i][j]的最优解由dp[i-1][j]和dp[i-1][j-v[i]]这两个子问题的最优解推导而来。初始化与遍历顺序通常我们将dp[0][j]初始化为0考虑0件物品价值为0。遍历时i从1到Nj从0到V。最终答案不一定在dp[N][V]如果定义是“恰好”需要遍历所有j取最大值如果定义是“不超过”dp[N][V]就是答案。3.2 空间优化滚动数组与一维数组直接使用二维数组空间复杂度是 O(NV)。观察状态转移方程dp[i][j]只依赖于dp[i-1][...]即上一行的数据。这意味着我们不需要保存整个二维表只需要保存两行上一行和当前行即可这就是“滚动数组”思想可以将空间优化到 O(2V)。更进一步我们可以优化到一维数组。定义dp[j]表示容量为 j 的背包能获得的最大价值。那么状态转移如何体现我们需要用“旧”的dp相当于dp[i-1]来更新“新”的dp相当于dp[i]。关键点在于遍历顺序容量 j 必须从大到小遍历。# 一维dp数组实现01背包 dp [0] * (V 1) for i in range(1, N 1): for j in range(V, v[i] - 1, -1): # 从大到小遍历 dp[j] max(dp[j], dp[j - v[i]] w[i])为什么要从大到小因为dp[j]依赖于dp[j - v[i]]而这个值是上一轮考虑前i-1件物品时的结果。如果从小到大遍历当更新dp[j]时dp[j - v[i]]可能已经在同一轮考虑第i件物品时被更新过了这就相当于第i件物品被重复考虑变成了“完全背包”的逻辑。从大到小遍历保证了在更新dp[j]时dp[j - v[i]]还是“干净”的、未被当前物品污染过的值。实操心得一维优化是必须掌握的技巧它不仅节省空间而且代码更简洁。务必牢记“01背包倒序完全背包正序”这个口诀。在笔试或竞赛中除非状态转移非常复杂否则优先写一维版本。3.3 完全背包与多重背包物品无限与有限理解了01背包完全背包就很容易了。完全背包中每种物品有无限件。状态定义可以和01背包一样。状态转移方程变为dp[i][j] max(dp[i-1][j], dp[i][j - v[i]] w[i]) (当 j v[i])区别在于“拿”的情况当我们选择拿第i件物品时因为物品无限拿完之后背包容量减少但我们仍然可以继续考虑第i件物品。所以依赖的是dp[i][j - v[i]]而不是dp[i-1][j - v[i]]。一维优化下的代码差异更明显只需将内层循环的容量 j 改为从小到大遍历。# 一维dp数组实现完全背包 dp [0] * (V 1) for i in range(1, N 1): for j in range(v[i], V 1): # 从小到大遍历 dp[j] max(dp[j], dp[j - v[i]] w[i])从小到大遍历使得在计算dp[j]时dp[j - v[i]]可能已经包含了当前物品i从而实现了物品的无限次选取。多重背包则介于两者之间第i件物品最多有s[i]件。最朴素的思路是将其转化为01背包把每件物品拆分成s[i]个独立物品但这样效率低。优化方法有二进制拆分和单调队列优化。二进制拆分是重点将数量s拆分成 1, 2, 4, ..., 2^k, c其中 c s - (2^{k1}-1)这样几个“物品包”每个包视为一个独立的、体积和价值为原物品对应倍数的“新物品”。用这些新物品做01背包可以组合出0到s之间的任意件数且物品总数从O(∑s)降到了O(∑log s)。4. 动态规划的经典模型与应用扩展4.1 序列型动态规划最长公共子序列与编辑距离序列问题通常涉及两个字符串或数组的比较。状态定义往往与位置相关。最长公共子序列LCS给定两个字符串text1和text2返回它们的最长公共子序列的长度。定义dp[i][j]为text1[0:i]和text2[0:j]的LCS长度。状态转移方程分两种情况如果text1[i-1] text2[j-1]那么这个字符一定在LCS中dp[i][j] dp[i-1][j-1] 1。如果不等那么LCS要么来自text1[0:i-1]和text2[0:j]要么来自text1[0:i]和text2[0:j-1]取最大值dp[i][j] max(dp[i-1][j], dp[i][j-1])。编辑距离给你两个单词word1和word2计算将word1转换成word2所使用的最少操作数插入、删除、替换一个字符。定义dp[i][j]为将word1[0:i]转换为word2[0:j]的最小编辑距离。如果word1[i-1] word2[j-1]无需操作dp[i][j] dp[i-1][j-1]。如果不等我们有三种选择取最小删除word1[i-1]:dp[i-1][j] 1插入word2[j-1](相当于在word1后添加):dp[i][j-1] 1替换word1[i-1]为word2[j-1]:dp[i-1][j-1] 1这类问题的初始化通常dp[i][0] i(删除i次)dp[0][j] j(插入j次)。4.2 路径规划与状态机模型路径规划是动态规划的另一大类应用例如在一个网格中从左上角到右下角每次只能向右或向下走求有多少种不同路径或者求路径上的最大/最小和。状态dp[i][j]通常表示到达坐标(i, j)的路径数或最优值转移方程来自上方和左方dp[i][j] dp[i-1][j] dp[i][j-1]或dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1])。更复杂一点的是带有障碍物或状态限制的路径问题。例如“买卖股票”系列问题其核心是引入了“状态机”的思想。以“买卖股票的最佳时机 IV最多完成k笔交易”为例我们需要定义的状态不再是简单的二维坐标而是三维dp[i][k][0 or 1]表示在第 i 天结束时最多进行了 k 笔交易且手上不持有(0)或持有(1)股票时的最大利润。状态转移就像在一个状态机持有/不持有之间切换决策是买入、卖出或休息。理解并熟练运用状态机模型是解决复杂动态规划问题的关键。4.3 动态规划在数学建模中的实战定位在数学建模竞赛中动态规划并非总是以裸算法题的形式出现它更多是作为一种强大的建模思想和求解工具嵌入到问题中。识别一个赛题是否能用动态规划可以问自己以下几个问题问题是否可以分解为多个阶段例如时间序列上的决策每年的投资、生产计划、空间上的递进沿着路径的资源分配、任务的处理顺序等。每个阶段是否有若干种状态例如当前的库存量、剩余的资金、已使用的资源、设备的工作模式等。当前阶段的决策是否只依赖于当前状态并能影响下一阶段的状态即“无后效性”。过去的决策只通过当前状态影响未来与过去的状态和决策路径无关。如果以上问题的答案是肯定的那么动态规划很可能是一个有效的建模工具。例如在2016年国赛A题“系泊系统的设计”中对于给定重物重量求各节钢桶和钢管的倾斜角度、锚链形态等虽然主要用力学方程但也可以将系统从下往上或从上往下看作多个阶段每一节状态是角度和受力用递推本质是动态规划思想求解。在资源调度、生产计划、投资组合优化等问题中动态规划更是直接的核心模型。在论文中如何呈现动态规划模型明确定义阶段、状态和决策变量。这是模型表述的核心务必清晰。可以用符号表列出。给出状态转移方程。这是模型的数学核心。要解释清楚方程每一项的含义。说明边界条件初始化和目标函数。初始状态是什么最终要优化的是哪个状态的值讨论算法复杂度。说明状态数阶段数*每个阶段的状态数和转移代价这是评价模型可行性的重要依据。可以提及优化方法。如果状态空间太大可以说明使用了滚动数组、记忆化搜索、或是利用问题特性进行了状态压缩。5. 从理论到实践解题框架与调试技巧5.1 动态规划解题的标准化四步法经过大量练习我总结了一个通用的四步解题框架能帮你系统性地分析和解决大部分动态规划问题。第一步定义状态Define这是最重要的一步。问自己需要几个维度来描述一个子问题常见的维度有序列/字符串的位置i、背包的容量j、交易的次数k、某种资源的使用量、以及一些辅助状态如是否持有股票。状态定义要保证“无后效性”和包含足够的信息。一个技巧是先尝试定义dp[i]如果发现无法转移就增加维度比如dp[i][j]。第二步推导状态转移方程Transition找出状态之间的关系。思考如何从已知的、更小的子问题的解推导出当前问题的解通常我们需要考虑在最后一个阶段或最后一个元素做出的决策。对于dp[i]看看它和dp[i-1]dp[i-2]... 有什么关系。对于dp[i][j]看看在面临第i个物品、第i个字符或第i天时有哪些选择每个选择会带来什么状态变化和价值收益。把这个关系用数学方程写出来。第三步确定初始化和边界条件Initialize状态转移方程决定了如何从“已知”推“未知”那么最初的“已知”是什么这就是初始化。通常规模最小、不可再分的子问题的解是已知的需要手动设置。例如dp[0]或dp[0][j]dp[i][0]。同时要注意转移方程中数组下标的有效性对于可能越界的访问如j - v[i] 0要在循环中判断或通过初始化、状态定义来规避。第四步确定计算顺序与输出答案Order Answer根据状态之间的依赖关系决定计算顺序。绝大多数情况是从小到大遍历自底向上。确保在计算dp[i][j]时它所依赖的所有状态如dp[i-1][j]dp[i][j-1]都已经被计算出来。最后根据问题要求从最终的dp数组中找出答案它可能是dp[N][M]也可能是max(dp[N][...])或min(dp[N][...])。5.2 记忆化搜索另一种清晰的实现范式对于某些状态转移不那么直观或者依赖关系不是简单的顺序遍历的问题自顶向下的记忆化搜索递归缓存往往写起来更直观。它完全对应了“分治记忆化”的思想。以“斐波那契数列”为例from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n-1) fib(n-2)lru_cache是Python的装饰器自动为我们做了缓存。如果没有这个装饰器我们需要自己维护一个memo字典。记忆化搜索的步骤是1) 写出暴力的递归函数2) 在递归函数开头检查当前参数是否在缓存中是则直接返回3) 递归计算4) 将计算结果存入缓存后返回。记忆化搜索的优点是与思维过程高度一致尤其适合树形DP、区间DP等场景。缺点是递归有栈开销对于深度很大的问题可能栈溢出。通常能写记忆化搜索就能改写成递推两者是等价的。在竞赛中如果对递推顺序没把握先写记忆化搜索确保逻辑正确再尝试优化成递推是一个稳妥的策略。5.3 调试与验证如何确保你的DP是正确的动态规划的代码一旦出错调试起来可能比普通程序更麻烦因为中间状态多逻辑关系复杂。以下是我常用的调试技巧打印DP表这是最直接有效的方法。在代码关键位置如每轮外层循环结束将整个dp数组或矩阵打印出来。对照着手算或逻辑推导的几行几列数据一眼就能看出哪里出了问题。对于二维DP格式化打印成矩阵形式观看。小数据测试不要一上来就用复杂的大样例。构造最小的、有代表性的测试用例比如N1V0这种边界情况手动算出答案看程序输出是否一致。对比暴力解法对于数据范围小的问题比如N20可以写一个暴力枚举或DFS搜索所有可能性的程序作为“标答”生成器来验证你的DP程序是否正确。这是验证算法正确性的黄金标准。关注初始化与边界很多错误出在初始化和数组越界上。仔细检查dp[0]、dp[...][0]的设置是否符合定义。检查循环的起止范围特别是当状态转移涉及i-1j-v[i]时确保索引不小于0。状态转移逻辑复查对着你写出的方程用自然语言复述一遍“要得到dp[i][j]如果我不选第i个物品那么值就是dp[i-1][j]如果我选前提是j够大那么值就是dp[i-1][j-v[i]] w[i]然后取大的那个。”确保这个复述和问题描述百分百吻合。6. 数学建模中的动态规划实战案例分析为了让大家更具体地感受动态规划在数学建模中如何运用我们抛开经典的算法题看一个简化的资源分配问题它非常接近国赛或美赛的优化类题目。问题简化描述某公司有m个研发项目可供选择初始资金为C万元。每个项目i需要投资a[i]万元预计完成后可获得收益b[i]万元。但项目之间存在依赖关系例如项目3必须在项目1完成后才能启动。公司希望选择一组项目进行投资在满足资金和依赖关系的前提下最大化总收益。请问该如何选择分析这是一个带有依赖关系的树形背包问题。每个项目可以看作一个节点依赖关系构成一座森林或一棵树如果有一个虚拟根节点。我们必须先完成父节点项目才能考虑其子节点项目。建模与求解状态定义对于以节点u为根的子树定义dp[u][j]表示在子树u中投入总资金不超过 j 万元所能获得的最大收益。这里“子树u”包含了必须选择u因为要选子节点必须先选父节点之后在其子树上进行决策。状态转移树形DP这是一个分组背包模型。节点u有若干个儿子节点每个儿子节点v对应一组决策在分配给子树v的资金k下能获得的最大收益是dp[v][k]。我们需要为每个儿子节点分配资金使得总资金不超过 j注意还要预留项目u本身的投资a[u]。首先初始化如果投资j连项目u本身都完成不了j a[u]那么dp[u][j] 0。否则我们先强制选择项目u那么剩余可用资金为j - a[u]基础收益为b[u]。然后我们面临的问题就是如何将这j - a[u]的资金分配给u的各个儿子子树使得儿子们带来的总收益最大。这正是一个分组背包问题每个儿子是一“组”每组内有多种“物品”即分配不同资金k给该儿子收益为dp[v][k]每组内最多选一个“物品”因为给一个儿子的资金分配方案是唯一的。我们需要在总资金j - a[u]的限制下从每组选一个物品最大化总收益。因此转移过程需要先遍历u的所有儿子v对于每个儿子v再枚举分配给它的资金k从0到j - a[u]用dp[v][k]去更新一个临时状态数组。这个过程类似于01背包但因为每组只能选一个所以需要小心更新顺序。计算顺序采用后序遍历DFS。先递归计算所有儿子节点的dp[v][...]再利用儿子节点的信息更新父节点u的dp[u][...]。答案最终对于所有根节点或虚拟根节点的儿子将它们的dp[root][C]进行合并又是一个背包问题或者直接建立一个虚拟总根答案就是dp[virtual_root][C]。这个例子展示了动态规划如何与图论结合解决具有复杂约束的优化问题。在数学建模论文中你需要清晰地阐述将项目依赖转化为树形结构的过程定义dp[u][j]状态并描述树形背包的转移过程。虽然实际代码实现需要递归和精细的背包循环但模型本身是清晰且具有说服力的。7. 避坑指南与高阶优化思路7.1 新手常犯的五个错误状态定义模糊或错误这是万恶之源。比如在背包问题中混淆“恰好装满”和“不超过容量”的定义导致初始化错误。务必用一句话精确描述dp[i][j]的含义。混淆遍历顺序一维优化时01背包必须倒序完全背包必须正序。搞反了结果全错。在二维DP中也要确保循环顺序能让依赖的状态先被计算。初始化不当特别是求“最小值”问题时经常需要将dp数组初始化为一个很大的数如inf但dp[0][0]要初始化为0。求“方案数”时dp[0][0]通常初始化为1。数组下标越界在转移方程中访问dp[i-1][j - v[i]]时没有判断j - v[i]是否大于等于0。要么在循环条件中控制j从v[i]开始要么在转移前加if判断。追求一步到位写一维优化对于复杂的状态转移强行写一维容易出错。建议先写出正确、清晰的二维版本验证无误后再考虑空间优化。二维版本的逻辑更直观便于调试。7.2 状态压缩当状态维度爆炸时有些问题的状态如果直接定义维度会很高导致空间和时间无法承受。例如旅行商问题TSP的经典状态定义是dp[S][i]表示访问过城市集合SS是一个二进制掩码最后停留在城市i的最小花费。这里S是一个集合如果我们用二进制数的每一位表示一个城市是否被访问那么一个整数就能表示一个集合。这就是状态压缩。通常用于表示小规模n 20的集合选与不选。另一个常见的压缩是滚动数组如前所述只保留两行数据。更进一步的如果状态转移只依赖于上一行的有限几个值甚至可以用几个变量来替代数组。7.3 动态规划的优化斜率优化与四边形不等式对于某些特定形式的动态规划方程存在更高效的优化方法这通常是算法竞赛中的高阶内容但在数学建模中遇到超大规模问题也可能用到。单调队列优化适用于状态转移方程形如dp[i] max/min{ f(j) } g(i)其中f(j)是一个只与j有关的函数且j的取值范围是一个滑动窗口。我们可以用单调队列在O(1)时间内获取窗口内的最值从而将O(n^2)的复杂度降为O(n)。多重背包的优化就用了这个思想。斜率优化适用于状态转移方程能整理成dp[i] min{ dp[j] f(i, j) }且f(i, j)可以拆分成(dp[j] A(j)) - B(j)*C(i)的形式。通过将每个决策j看作二维平面上一个点将问题转化为维护一个凸包在凸包上寻找最优决策点。这需要一定的数学变形能力。四边形不等式适用于区间DP问题用于证明决策单调性从而将O(n^3)的复杂度优化到O(n^2)。对于数学建模而言除非问题规模极大且模型恰好符合这些优化条件否则更现实的做法是1) 简化模型减少状态数2) 利用启发式算法如遗传算法、模拟退火求近似解3) 使用专业的优化求解器如CPLEX Gurobi。在论文中证明你模型的正确性和阐述清晰的思想比追求极致的算法优化更重要。学习动态规划就像学习一门内功心法。初期会觉得招式状态方程繁复但一旦打通任督二脉理解最优子结构和无后效性再看很多问题都会有一种“一览众山小”的通透感。这套课程的目的就是陪你走通这段路。剩下的就是在大量的练习和实战中将这种思维模式化为本能。在数学建模的赛场上当你面对一个复杂的优化决策问题能敏锐地察觉到“这似乎可以分阶段考虑”并尝试构建状态和转移方程时你就已经比别人领先了一个身位。