上一篇中，Kadane算法用O(n)的时间干净利落地解决了最大子数组问题。回顾它的核心递推式dp[i]=max(dp[i-1]+A[i], A[i])，我们会发现一个更深层的结构：原问题的最优解，可以通过子问题的最优解构造出来。这正是动态规划的理论基石。
动态规划不是某一种具体的算法，而是一类求解最优化的数学方法。它的英文名“Dynamic Programming”中，“Programming”取的是“规划”而非“编程”的语义，源于上世纪五十年代Bellman在兰德公司从事运筹学研究时的命名。要准确使用这套方法，必须首先理解使它成立的两个前提条件。
一、最优子结构
定义：如果一个问题的最优解包含其子问题的最优解，则称该问题具有最优子结构性质。
这个定义值得逐字拆解。它不是说“子问题的解可以组合成原问题的解”——这是分治的前提。它说的是：原问题的最优解，必然由子问题的最优解构成。因此，在寻找全局最优时，我们无需考虑子问题的次优解，因为它们不可能参与构造全局最优。
检验最优子结构的一个通用方法是“剪贴法”：假设原问题的最优解中某个子问题的解不是最优的，那么将该子问题的解替换为更优的那个，理应得到一个更优的原问题解。若这个替换与前提矛盾，则最优子结构成立。
不是所有问题都具备最优子结构。寻找图中的最长简单路径就不具备这一性质——最长路径的子路径未必是子图的最长路径，因为最长路径的局部最优与全局最优之间存在冲突。在动态规划建模前，这一步的检验绝非可有可无。
二、重叠子问题
定义：若递归算法在求解过程中反复求解相同的子问题，而非不断产生全新的子问题，则称该问题具有重叠子问题性质。
分治算法中，子问题通常彼此独立，每个子问题只被求解一次。动态规划恰恰相反：同一个子问题可能从不同的父问题出发被多次遇到。若不刻意避免，递归树中会出现指数规模的重复计算。
斐波那契数列的递归求解是重叠子问题的经典反面教材：F(n)=F(n-1)+F(n-2)，没有存储中间结果的朴素递归将导致重复计算呈指数增长。动态规划的精髓，正是通过有组织的记忆化，将每种子问题只计算一次，将指数时间压缩到多项式。
三、无后效性与状态设计
与最优子结构紧密相关的还有一个关键概念——无后效性：子问题的解一旦确定，就不再受后续更大问题决策的影响，即“未来不改变过去”。
这一性质直接指导着状态定义这个建模核心环节。状态的定义必须足够丰富，使得从该状态出发的未来决策，只依赖当前状态的信息，而不需要回溯已走过的路径。倘若状态遗漏了必要的上下文，未来决策就无法正确做出；倘若包含了冗余信息，状态空间将不必要地膨胀。状态定义的精确与简约，是动态规划建模中最考验功力的地方。
四、两种实现范式：自顶向下与自底向上
动态规划有两种对偶的实现策略。
自顶向下（备忘录法）：保持递归调用的结构，但用一个数组或哈希表缓存每个子问题的解。每次进入递归前先查表，若已有结果则直接返回，否则计算并存储。优点是保留了原问题的自然递归结构，易于编写和理解，仅计算实际用到的子问题。
自底向上（表格法）：显式定义子问题的求解顺序，从最小规模的子问题开始，逐步填充表格，直至得到原问题的解。优点是不需要递归调用的栈开销，求解顺序明确，便于分析复杂度。
两种实现在时间复杂度上通常一致，选择取决于问题的自然结构和个人偏好。但自底向上的方法对确定求解顺序的要求更高，在子问题依赖关系比较复杂时，需要额外进行拓扑排序。
五、实例展开：矩阵链乘法
给定n个矩阵的序列A₁,A₂,...,Aₙ，目标是找到一种加括号的方式，使得计算连乘积所需的标量乘法次数最少。矩阵乘法满足结合律但不同的括号方案开销差异巨大——一个10×100的矩阵乘100×5的矩阵需5000次乘法，再乘5×50需2500次，总计7500；但若先算后两个，开销截然不同。
状态定义：令m[i][j]为计算Aᵢ...Aⱼ所需的最小标量乘法次数。设矩阵Aᵢ的维度为pᵢ₋₁×pᵢ。
最优子结构：在Aᵢ...Aⱼ的最优加括号方案中，必然存在一个最外层划分点k（i≤k<j），使得先算左侧Aᵢ...Aₖ，再算右侧Aₖ₊₁...Aⱼ，最后将两个结果相乘。两侧子链的计算必须自身最优——这正是最优子结构的体现。由此导出状态转移方程：
m[i][j]=mini≤k<j{m[i][k]+m[k+1][j]+pi−1⋅pk⋅pj}m[i][j]=i≤k<jmin{m[i][k]+m[k+1][j]+pi−1⋅pk⋅pj}
求解顺序：矩阵链长度由2增长到n，对每个长度枚举起止位置和划分点。三重循环，时间复杂度Θ(n³)，空间Θ(n²)。
这个结构是动态规划的经典范式：定义状态、找出转移方程、确定填表顺序。矩阵链乘法看似是纯粹的数学问题，但在编译器设计中的寄存器分配、图像处理中的色彩空间转换等场景都有其影子。
从下一篇开始，我们将进入动态规划最具代表性的实例——01背包问题，以及它如何通过精巧的空间优化，将一个看似必须二维填表的过程压缩到一维滚动数组。
