一、前言

The future is independent of the past given the present
未来独立于过去，只基于当下。

马尔可夫链，即状态空间中经过从一个状态到另一个状态的转换的随机过程。

0

在开始之前请认真理解下面这段话：
决策类求最优解问题，本质上是在状态空间中寻找一个可达的最佳状态。传统的搜索方法是通过遍历每个点来寻找答案，而动态规划则是对状态空间进行变形，将其转化为从初始状态到目标状态的最短路问题。
若问题的结论涉及多个决策，那么从初始状态（即边界条件）到最终解的决策流程，可以视为在决策状态空间中的一条转移路径。这要求状态描述必须完整且唯一地覆盖状态空间中的所有有效点，同时转移路径需包含所有可能的路径。这恰好契合了动态规划的两大核心条件：无后效性和最优子结构。
无后效性意味着状态间的转移与到达该状态的路径无关，若存在关联，则表明状态描述未能完整且唯一地涵盖每个状态。此时，只需将引起后效性的参数纳入状态描述中，即可消除后效性。而最优子结构则确保转移路径涵盖了所有可能的路径，若缺失，则意味着有部分情况在转移中未得到充分体现，此时需增加转移的描述。
最终，所有的搜索问题都可归结为状态空间内的状态转移方程。尽管状态数量可能呈指数级增长，导致计算需求巨大，但动态规划通过将问题转化为状态空间内由大量可行状态点和有效转移构成的图，从而找到从初始状态到最终状态的最短路。因此，动态规划的本质可视为图论中的最短路问题。此外，阶段划分并非动态规划的必需，因为并非所有问题都有明确的阶段划分。

1

动态规划是一种针对特定类型问题的解决方法，关键在于理解问题的阶段和状态，以及状态间的转移方式。它并不局限于递推或递归，也不仅仅是空间换时间的策略。要掌握动态规划，首先需要明确哪些问题不适合用此方法解决，从而更清晰地认识其适用范围。
动态规划与递推、贪心和搜索等方法有所关联，但也有显著区别。递推通常用于状态转移直接且明确的问题；贪心则适用于每一步选择都基于当前最优解的情况；而搜索则用于状态空间复杂，需要遍历所有可能性的场景。
动态规划适用于那些可以划分为多个阶段，且每个阶段有多个状态，状态间存在明确转移关系的问题。其核心在于识别问题的最优子结构和无后效性。最优子结构意味着问题的最优解可以由其子问题的最优解直接得到；无后效性则表明当前状态的选择不受之前状态选择路径的影响。
为了理解动态规划，我们可以从计算机的状态机本质出发。计算机通过存储当前状态，并利用这些状态计算下一个状态来解决问题。空间复杂度衡量了解决问题所需存储的状态数量，而时间复杂度则反映了从初始状态到达最终状态所需的步骤数。
以斐波那契数列为例，每个数都是问题的一个状态，计算新数只需前两个状态。这种直接的状态转移方式称为递推。然而，当问题涉及多个阶段和状态组合时，情况就变得复杂了。例如，在围棋棋盘上移动，每一步都可能导致多个可能的状态。此时，我们需要考虑如何有效地存储和计算这些状态。
在某些情况下，我们不需要计算所有可能的状态。例如，在求解从棋盘左上角到右下角的最短路径时，我们只需记录每一步的最优解即可。这种策略称为贪心算法。然而，当问题的最优解依赖于之前所有状态的选择时，贪心算法就失效了。这时，我们需要使用动态规划来记录每个阶段的最优解，并根据这些解来计算下一个阶段的最优解。
以最长上升子序列（LIS）为例，我们可以使用动态规划来求解。我们定义一个数组来记录以每个元素结尾的LIS长度，并根据这个数组来计算下一个元素的最优解。这种方法的关键在于识别问题的最优子结构和无后效性，从而避免不必要的状态计算。
总之，选择递推、贪心、搜索还是动态规划来解决问题，取决于问题本身阶段间状态的转移方式。动态规划特别适用于那些具有最优子结构和无后效性的问题。在解决问题时，我们需要根据问题的特性来选择合适的方法，并设计相应的算法来实现。

2

动态规划的核心在于对问题状态及其状态转移方程的定义。它通过将复杂问题分解为简单子问题，并利用这些子问题之间的关系（即状态转移方程），以递推方式求解。以下是对这一过程的详细阐述：

状态的定义：

• 状态是对问题当前情况的数学化描述，用于表示子问题的解。
• 以最长递增子序列（LIS）问题为例，可以定义状态$F_k$为以数列中第k项结尾的最长递增子序列的长度。
• 状态的定义不是唯一的，可以从不同角度进行描述，如定义$F_{i,k}$为在前i项中长度为k的递增子序列中最后一位的最小值。

状态转移方程：

• 状态转移方程描述了状态之间的关系，即如何利用已知子问题的解来求解当前问题。
• 对于LIS问题，状态转移方程可以是$F_1=1$(根据状态定义导出边界情况)$F_k=max(F_i+1|A_k>A_i,i\in (\mathrm{1..}k-1))$（基于第一种状态定义）;若$A_i>F_{i-1,k-1}$则$F_{i,k}=min(A_i,F_{i-1,k})否则：$ $F_{i,k}=F_{i-1,k}$（基于第二种状态定义）
• 状态转移方程实质上是带有条件的递推式，定义了问题和子问题之间的关系。

动态规划的本质：

• 动态规划的核心在于找到符合“最优子结构”的状态和状态转移方程的定义。
• “最优子结构”意味着问题的最优解可以由其子问题的最优解组合而成。
• 在定义状态和状态转移方程时，满足“最优子结构”是一个隐含条件。
• 动态规划并非仅仅关注“缓存”、“重叠子问题”或“记忆化”等求解技巧，而是寻找一种对问题的观察角度，使得问题能够以递推方式解决。

误解与澄清：

• “递归”是递推式求解的一种方法，但不是动态规划的本质。
• “无后效性”和“最优子结构”是动态规划问题的重要特征，但并非所有状态定义都满足这些条件。一个问题的不同状态定义可能具有后效性，但这并不意味着该问题不适用动态规划。
• 动态规划不仅仅是“记忆化地求解递推式”，更重要的是找到符合“最优子结构”的状态和状态转移方程的定义。

综上所述，动态规划的本质在于对问题状态和状态转移方程的精确定义，以及寻找符合“最优子结构”的求解路径。

3

动态规划是一种解决问题的方法，其本质在于将问题定义为“原问题的解如何由子问题的解组合而成”的形式，并据此构建状态转移方程。这种定义方式并非对所有问题都显而易见，需要变化看待问题的角度。一旦成功定义，动态规划问题通常可以通过两种成熟的实现方式解决：自顶向下的递归（可能结合缓存以提升效率）和自低向上的迭代。递归只是实现动态规划的一种方式，并非其本质；同样，缓存也只是提升计算效率的手段。选择自顶向下还是自低向上的方法，取决于问题的具体特点和个人偏好，但自顶向下通常更直观且易于得到递归公式，而自低向上则可能在空间复杂度上更具优势。总之，动态规划的核心在于正确定义问题和子问题的关系，并以此为基础构建解决方案。

4

动态规划(dynamic programming)与分治方法相似,都是通过组合子问题的解来求解原问题(在这里,“programming”指的是一种表格法,并非编写计算机程序)。分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了这种不必要的计算工作。
动态规划方法通常用来求解最优化问题(optimization problem)。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解(an optimal solution),而不是最优解(the optimal solution),因为可能有多个解都达到最优值。
我们通常按如下4个步骤来设计一个动态规划算法:
1.刻画一个最优解的结构特征。
2.递归地定义最优解的值。
3.计算最优解的值,通常采用自底向上的方法。
4.利用计算出的信息构造一个最优解。
步骤1~3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值,而非解本身,可以忽略步骤4。如果确实要做步骤4,有时就需要在执行步骤3的过程中维护一些额外信息,以便用来构造一个最优解。

5

算法导论是作者认为对动态规划讲解最好的，下面的大部分例子将来自于算法导论与力扣，并在其中夹杂着作者自己的理解与注释。

二、钢条切割

我们第一个应用动态规划的例子是求解一个如何切割钢条的简单问题。Serling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长度为i英寸的钢条的价格为pi(i=1,2,…,单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。

图15-1 钢条价格表样例。每段长度为i英寸的钢条为公司带来p;美元的收益

钢条切割问题是这样的:给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n),求切割钢条方案,使得销售收益r,最大。注意,如果长度为n英寸的钢条的价格p,足够大,最优解可能就是完全不需要切割。考虑n=4的情况。图15-2给出了4英寸钢条所有可能的切割方案,包括根本不切割的方案。
我们发现,将一段长度为4英寸的钢条切割为两段各长2英寸的钢条,将产生$p_2+p_2=5+5=10$的收益,为最优解。

图15-2 4英寸钢条的8种切割方案。根据图15-1中的价格表,在每段钢条之上标记了它的价格。最优策略为方案©——将钢条切割为两段长度均为2英寸的钢条——总价值为10

长度为n英寸的钢条在最小切割长度为1英寸的情况下共有$2^{n-1}$种不同的切割方案，因为在距离钢条左端i（i=1，2，……，n-1）英寸处，我们总是可以选择切割或者不切割（如果要求按照长度非递减的顺序切割小段钢条，可能的切割方案会少很多。例如图15-2中的d、f、g的切割方式分别为递减、不规律、递减，我们只需要考虑5种切割方案，切割方案的数量可由划分函数给出，此函数近似等于$e^{\pi \sqrt{2n/3}}/4n\sqrt{3}$，此值虽然小于$2^{n-1}$，但是远远大于任何n的多项式，因此我们选择$2^{n-1}$作为表达式）我们用加号表示切割方案，即7=2+2+3表示将长度为7英寸的钢条切割为三段——两段长度为2英寸、一段长度为3英寸。
现在假设一个最优解将钢条切割为k段（$1⩽k⩽n$）,那么最优切割方案表达式如下：
$n=i_1+i_2+\cdots +i_k$
将钢条切割成长度分别为$n=i_1+i_2+\cdots +i_k$的小段（上面的最优切割方案），得到最大收益表达式如下：
$r_n=p_{i_1}+p_{i_2}+\cdots +p_{i_k}$
对照上述价格表样例，可以知道所有最优收益值$r_i(i=1,2,\cdots ,10)$以及对应的最优切割方案如下：
$r_1=1$,切割方案 1=1(无切割)
$r_2=5$,切割方案 2=2(无切割)
$r_3=8$,切割方案 3=3(无切割)
$r_4=10$,切割方案4=2+2
$r_5=13$,切割方案5=2+3
$r_8=22$,切割方案 8=2+6
$r_6=17$,切割方案 6=6(无切割)
$r_7=18$,切割方案7=1+6或7=2+2+3
$r_9=25$,切割方案 9=3+6
$r_{10}=30$,切割方案 10=10(无切割)
由此我们可以总结出一个通用表达式，即对于$r_n(n⩾1)$,有如下的最优切割收益：
$$r_n=\max (p_n,r_1+r_{n-1},r_2+r_{n-2},\cdots ,r_{n-1}+r_1)$$
(15.1)
第一个参数$p_n$对应不切割，直接出售长度为$n$英寸的钢条的方案。其他$n-1$个参数对应另外$n-1$种方案：对每个$i=1,2,...,n-1$,首先将钢条切割为长度为$i$和$n-i$的两段，接着求解这两段的最优切割收益 $r_i$ 和$r_{\pi -i}($每种方案的最优收益为两段的最优收益之和)。由于无法预知哪种方案会获得最优收益，我们必须考察所有可能的$i$,选取其中收益最大者。如果直接出售原钢条会获得最大收益，我们当然可以选择不做任何切割。（注：首先切割成两段，如果某一段的最优切割方案有且仅有可切割一种，那么则可以对该段继续切割，以此类推，直至最优切割方案为无切割。对于$r_7=18$时的切割方案7=2+2+3我们可以看成$r_4$（可继续分割）+$r_3$（无切割）或者$r_2$（无切割）+$r_5$（可继续分割））
注意到，为了求解规模为$n$的原问题，我们先求解形式完全一样，但规模更小的子问题。即当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例，通过组合两个相关子问题的最优解，在所有方案中选取收益最大者，将其作为原问题的最优解。我们称这种情况满足最优子结构性质：问题的最优解由相关子问题的最优解组合而成，并且这些子问题可以独立求解。
除了上述求解方法外，钢条切割问题还存在一种相似的但更为简单的递归求解方法：我们将钢条从左边切割下长度为$i$的一段，只对右边剩下的长度为$n$一 $i$的一段继续进行切割(递归求解), 对左边的一段则不再进行切割。即问题分解的方式为：将长度为$n$的钢条分解为左边开始一段， 以及剩余部分继续分解的结果。这样，不做任何切割的方案就可以描述为：第一段的长度为$n$,收益为$p_n$,剩余部分长度为 0,对应的收益为$r_0=0$。于是我们可以扩展得到公式(15.1)的简化版本：
$$r_n=\underset{1⩽i⩽n}{\max }(p_i+r_{n-i})$$
(15.2)
在此公式中，原问题的最优解只包含一个相关子问题(右端剩余部分)的解，而不是两个。

自顶向下递归实现
下面的过程实现了公式(15.2)的计算，它采用的是一种直接的自顶向下的递归方法。

$CUT-ROD(p,n)$
1 if$n=0$
2 return 0
3 $q=-\infty$
4 for $i=1$to$n$
5 $q=\max (q,p[i]+$CUT-ROD$(p,n-i))$
6 return $q$

过程 CUT-ROD 以价格数组 p[1…n]和整数$n$为输人，返回长度为$n$的钢条的最大收益。若$n=0$,不可能有任何收益，所以CUT-ROD的第2行返回0。第3行将最大收益$q$初始化为$-\infty$, 以便第 4~5 行的 for 循环能正确计算$q={\max }_{1⩽i⩽n}(p_i+$CUT-ROD( $p,n-i))$ ,第 6 行返回计算结果。利用简单的归纳法，可以证明此结果与公式(15.2)计算出的最大收益$r_n$是相等的。
如果你用熟悉的编程语言实现 CUT-ROD,并在你的计算机上运行它，你会发现，一旦输人规模稍微变大，程序运行时间会变得相当长。例如，对$n=40$,程序至少运行好几分钟，很可能超过一小时。实际上，你会发现，每当将$n$增大 1,程序运行时间差不多就会增加 1倍。
为什么 CUT-ROD 的效率这么差？原因在于，CUT-ROD 反复地用相同的参数值对自身进行递归调用，即它反复求解相同的子问题。图 15-3 显示了$n=4$时的调用过程：CUT-ROD(p,n) 对$i=1,2,\cdots ,n$调用 CUT-ROD($p,n-i)$,等价于对 $j=0,1,\cdot \cdot \cdot ,n-1\text{ 调用 CUT- ROD( }p$, $j$)。当这个过程递归展开时，它所做的工作量(用$n$ 的 函 数 的 形 式 描 述 ) 会爆炸性地增长 。

为了分析 CUR-ROD 的运行时间，令$T(n)$表示第二个参数值为$n$时 CUT-ROD 的调用次数。此值等于递归调用树中根为$n$的子树中的结点总数，注意，此值包含了根结点对应的最初的一次调用。因此$T(0)=1$,且
$$T(n)=1+\sum _{j=0}^{n-1}T(j)$$
(15.3)
第一项“1”表示函数的第一次调用(递归调用树的根结点),$T(j)$为调用 CUT-ROD($p,n-i)$所产
生的所有调用(包括递归调用)的次数，此处$j=n-i$。练习 15.1-1 要求证明：
$$T(n)=2^n$$
(15.4)
即 CUT-ROD 的运行时间为$n$的指数函数。
回过头看，CUT-ROD 的指数运行时间并不令人惊讶。对于长度为$n$的钢条，CUT-ROD 显然考察了所有 $2^{n-1}$种可能的切割方案。递归调用树中共有 $2^{n-1}$个叶结点，每个叶结点对应一种可能的钢条切割方案。对每条从根到叶的路径，路径上的标号给出了每次切割前右边剩余部分的长度(子问题的规模)。也就是说，标号给出了对应的切割点(从钢条右端测量)。

使用动态规划方法求解钢条最优切割问题
我们现在展示如何将CUT-ROD转换为一个更高效的动态规划算法。
动态规划方法的思想如下所述：
我们已经看到，朴素递归算法之所以效率很低，是因为它反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算时间，是典型的时空权衡(time-memory trade-off)的例子。而时间上的节省可能是非常巨大的：可能将一个指数时间的解转化为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数，而我们可以在多项式时间内求解出每个子问题，那么动态规划方法的总运行时间就是多项式阶的。
动态规划有两种等价的实现方法，下面以钢条切割问题为例展示这两种方法。
第一种方法称为带备忘的自顶向下法(top-down with memoization)${}^{\ominus }$。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的(memoized), 因为它“记住”了之前已经计算出的结果。
第二种方法称为自底向上法(bottom-up method)。这种方法一般需要恰当定义子问题“规模” 的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它(也是第一次遇到它)时，它的所有前提子问题都已求解完成。
两种方法得到的算法具有相同的渐近运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。
下面给出的是自顶向下 CUT-ROD 过程的伪代码，加人了备忘机制：

MEMOIZED-CUT-ROD(p,n)
1 let $r[0\dots n]$be a new array
2 for $i=0$ to $n$
3 $r[i]=-\infty$
4 $\text{return MEMOIZED- CUT- ROD- AUX}(p,n,r)$

MEMOIZED-CUT-ROD-AUX( $p,n,r)$
1 if $r[n]⩾0$
2 return $r[n]$
3 if$n=0$
4 $q=0$
5 else $q=-\infty$
6 $\text{for }i=1$ to $n$
7 $q=\max (q,p[i]+$MEMOIZED-CUT-ROD-AUX( $p,n-i,r))$
8 $r[n]=q$
9 return $q$

这里，主过程 MEMOIZED-CUT-ROD 将辅助数组 $r[\mathrm{0..}n]$的元素均初始化为一$\infty$,这是一种常见的表示“未知值”的方法(已知的收益总是非负值)。然后它会调用辅助过程 MEMOIZED CUT- ROD- AUX。
过程 MEMOIZED-CUT-ROD-AUX 是最初的 CUT-ROD引人备忘机制的版本。它首先检查所需值是否已知(第 1 行),如果是，则第 2 行直接返回保存的值；否则，第 3~7 行用通常方法计算所需值$q$,第8行将$q$存人$r[n]$,第 9 行将其返回。
自底向上版本更为简单：

BOTTOM-UP-CUT-ROD( $p,n)$
1 let $r[\mathrm{0..}n]$be a new array
2 $r[0]=0$
3 $\text{for }j=1$ to $n$
4 $q=-\infty$
5 for $i=1$ to $j$
6 $q=\max (q,p[i]+r[j-i])$
7 $r[j]=q$
8 return $r[n]$

自底向上版本 BOTTOM-UP-CUT-ROD 采用子问题的自然顺序：若$i<j$,则规模为$i$的子问题比规模为$j$的子问题“更小”。因此，过程依次求解规模为$j=0,1,...,n$的子问题。过程 BOTTOM-UP-CUT-ROD 的第 1 行创建一个新数组 $r[0\dots n]$来保存子问题的解，第 2 行将 r[0]初始化为 0,因为长度为 0 的钢条没有收益。第 3~6 行对$j=1,2,...,n$按升序求解每个规模为$j$的子问题。求解规模为$j$的子问题的方法与 CUT-ROD 所采用的方法相同，只是现在直接访问数组元素$r[j-i]$来获得规模为$j-i$的子问题的解(第 6 行),而不必进行递归调用。第7 行将规模为$j$的子问题的解存人$r[j]$。最后，第8 行返回$r[n]$,即最优解$r_n$。
自底向上算法和自顶向下算法具有相同的渐近运行时间。过程 BOTTOM-UP-CUT-ROD 的主体是嵌套的双重循环，内层 for 循环(第 5~6 行)的迭代次数构成一个等差数列，不难分析过程的运行时间为$\Theta (n^2)$。自顶向下的 MEMOIZED-CUT-ROD 的运行时间也是$\Theta (n^2)$,其分析略难一些：当求解一个之前已计算出结果的子问题时，递归调用会立即返回，即 MEMOIZEDCUT-ROD 对每个子问题只求解一次，而它求解了规模为 0,1,…,n 的子问题；为求解规模为$n$的子问题，第 6~7 行的循环会迭代$n$次；因此，MEMOIZED-CUT-ROD 进行的所有递归调用执行此 for 循环的迭代次数也是一个等差数列，其和也是$\Theta (n^2)$,与 BOTTOM-UP-CUT-ROD 内层for循环的迭代总次数一样（我们在这里实际用到了某种形式的聚合分析）

子问题图
当思考一个动态规划问题时，我们应该弄清所涉及的子问题以及子问题之间的依赖挂你性能。
问题的子问题图准确的表达了这些信息。图15-4显示了n=4时钢条切割问题的子问题图。

注：可以看出图15-4是对图15-3进行了剪枝与优化操作，剪掉了重复的计算部分，使树形结构简化成了线性结构，这也对应了我们在最开始说的，“传统的搜索方法是通过遍历每个点来寻找答案，而动态规划则是对状态空间进行变形，将其转化为从初始状态到目标状态的最短路问题”。
它是一个有向图,每个顶点唯一地对应一个子问题。若求子问题x的最优解时需要直接用到子问题y的最优解,那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。例如,如果自顶向下过程在求解x时需要直接递归调用自身来求解y,那么子问题图就包含从x到y的一条有向边。我们可以将子问题图看做自顶向下递归调用树的“简化版”或“收缩版”,因为树中所有对应相同子问题的结点合并为图中的单一顶点,相关的所有边都从父结点指向子结点。
自底向上的动态规划方法处理子问题图中顶点的顺序为:对于一个给定的子问题x,在求解它之前求解邻接至它的子问题y(回忆B.4节,邻接关系不一定是对称的)。自底向上动态规划算法是按“逆拓扑序”(reverse topological sort)或“反序的拓扑序”(topological sort of the transpose)来处理子问题图中的顶点。换句话说，对于任何子问题，直至它依赖的所有子问题均已求解完成，才会求解它。类似地，我们可以用深度优先搜索”( depth-first search)来描述(带备忘机制的)自顶向下动态规划算法处理子问题图的顺序。
子问题图 $G=(V,E)$的规模可以帮助我们确定动态规划算法的运行时间。由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。通常，一个子问题的求解时间与子问题图中对应顶点的度(出射边的数目)成正比，而子问题的数目等于子问题图的顶点数。因此，通常情况下，动态规划算法的运行时间与顶点和边的数量呈线性关系。

重构解
前文给出的钢条切割问题的动态规划算法返回最优解的收益值，但并未返回解本身(一个长度列表，给出切割后每段钢条的长度)。我们可以扩展动态规划算法，使之对每个子问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，我们就能输出最优解。
下面给出的是 BOTTOM-UP-CUT-ROD 的扩展版本，它对长度为$j$的钢条不仅计算最大收益值$r_j$,还保存最优解对应的第一段钢条的切割长度 $s_j:$

EXTENDED-BOTTOM-UP-CUT-ROD( $p,n)$
1 let $r[\mathrm{0..}n]$and s$[\mathrm{0..}n]$be new arrays
2 $r[0]=0$
3 for$j=1$to$n$
4 $q=-\infty$
5 for$i=1\text{to}j$
6 if $q<p[i]+r[j-i]$
7 $q=p[i]+r[j-i]$
8 $s[j]=i$
9 $r[j]=q$
10 return $r$ and s

此过程与 BOTTOM-UP-CUT-ROD 很相似，差别只是在第 1 行创建了数组 s,并在求解规模为$j$的子问题时将第一段钢条的最优切割长度$i$ 保存在 s[j]中(第 8 行)。
下面的过程接受两个参数：价格表$p$和钢条长度$n$,然后调用 EXTENDED-BOTTOM-UPCUT-ROD 来计算切割下来的每段钢条的长度 s[1…n],最后输出长度为$n$的钢条的完整的最优切割方案：

PRINT- CUT- ROD- SOLUTION$(p,n)$
1 $(r,s)=$EXTENDED-BOTTOM-UP-CUT-ROD( $p,n)$
2 while $n>0$
3 print s$[n]$ 4 $n=n-s[n]$
对于前文给出的钢条切割的实例，EXTENDED-BOTTOM-UP-CUT-ROD(p,10)会返回下面的数组：

对此例调用PRINT-CUT-ROD-SOLUTION(p,10)只会输出10,但对n=7,会输出最优方案$r_7$切割出的两段钢条的长度1和6。

三、矩阵链乘法

下一个例子是求解矩阵链相乘问题的动态规划算法。给定一个$n$个矩阵的序列(矩阵链)
$⟨A_1,A_2,\cdots ,A_n⟩$,我们希望计算它们的乘积
$$A_1{A}_2\cdot \cdot \cdot A_n$$
(15.5)
为了计算表达式(15.5),我们可以先用括号明确计算次序，然后利用标准的矩阵相乘算法进行计算。由于矩阵乘法满足结合律，因此任何加括号的方法都会得到相同的计算结果。我们称有如下性质的矩阵乘积链为完全括号化的(fully parenthesized):它是单一矩阵，或者是两个完全括号化的矩阵乘积链的积，且已外加括号。例如，如果矩阵链为$⟨A_1,A_2,A_3,A_4⟩$,则共有5种完全括号化的矩阵乘积链：
$$\begin{gathered} (A_1(A_2(A_3{A}_4))) \\ (A_1((A_2{A}_3)A_4)) \\ ((A_1{A}_2)(A_3{A}_4)) \\ ((A_1(A_2{A}_3))A_4) \\ (((A_1{A}_2)A_3)A_4) \end{gathered}$$
对矩阵链加括号的方式会对乘积运算的代价产生巨大影响。我们先来分析两个矩阵相乘的代价。下面的伪代码给出了两个矩阵相乘的标准算法，它是 4.2 节 SQUARE-MATRIX-MULTIPLY 过程的推广。属性 rows 和 columns 是矩阵的行数和列数。

MATRIX-MULTIPLY(A,B)
1 if A. columns$\ne B.rows$
2 error“incompatible dimensions"
3 else let C be a new A. rows $\times B.\text{columns matrix}$
4 $\text{for }i=1\text{ to A. rous}$
5 $\text{for }j=1\text{to }B.columns$
6 $c_{ij}=0$
7 for $k=1\text{to A},columns$
8 $c_{ij}=c_{ij}+a_{ik}\cdot b_{kj}$
9 return C

两个矩阵$A$和$B$只有相容(compatible),即$A$的列数等于$B$的行数时，才能相乘。如果$A$ 是$p\times q$的矩阵，$B$是$q\times r$的矩阵，那么乘积$C$是$p\times r$的矩阵。计算$C$所需时间由第8 行的标量乘法的次数决定，即pqr。下文中我们将用标量乘法的次数来表示计算代价。
我们以矩阵链$⟨A_1,A_2,A_3⟩$相乘为例，来说明不同的加括号方式会导致不同的计算代价。假设三个矩阵的规模分别为$10\times 100$、100×5 和 5×50。如果按(($A_1{A}_2)A_3$)的顺序计算，为计算$A_1{A}_2$(规模 10×5),需要做$10\cdot 100\cdot 5=5$ 000 次标量乘法，再与$A_3$相乘又需要做 10$\bullet 5\bullet 50=$ 2 500 次标量乘法，共需 7 500 次标量乘法。如果按($A_1(A_2{A}_3))$的顺序，计算 $A_2{A}_3$(规模 100× 50),需$100\bullet 5\bullet 50=25$ 000 次标量乘法，$A_1$再与之相乘又需$10\bullet 100\bullet 50=50$ 000 次标量乘法， 共需 75 000 次标量乘法。因此，按第一种顺序计算矩阵链乘积要比第二种顺序快 10 倍。
矩阵链乘法问题(matrix-chain multiplication problem)可描述如下：给定$n$个矩阵的链{}$⟨A_1$, $A_2,\cdots ,A_n⟩$,矩阵$A_i$的规模为$p_i-1\times p_i(1⩽i⩽n)$,求完全括号化方案，使得计算乘积$A_1{A}_2\cdots A_n$ 所需标量乘法次数最少。
注意，求解矩阵链乘法问题并不是要真正进行矩阵相乘运算，我们的目标只是确定代价最低的计算顺序。确定最优计算顺序所花费的时间通常要比随后真正进行矩阵相乘所节省的时间(例如仅进行 7 500 次标量乘法而不是 75 000 次)要少。

计算括号化方案的数量
在用动态规划方法求解矩阵链乘法问题之前，我们先来说服自己——穷举所有可能的括号化方案不会产生一个高效的算法。对一个$n$个矩阵的链，令$P(n)$表示可供选择的括号化方案的数量。当$n=1$时，由于只有一个矩阵，因此只有一种完全括号化方案。当$n⩾2$时，完全括号化的矩阵乘积可描述为两个完全括号化的部分积相乘的形式，而两个部分积的划分点在第反个矩阵和第$k+1$ 个矩阵之间，$k$为1，2,…,$n-1$ 中的任意一个值。因此，我们可以得到如下递归公式：
$$P(n)=\{\begin{array}{ll}1& \text{如果 }n=1\\ {\sum }_{k=1}^{n-1}P(k)P(n-k)& \text{如果 }n⩾2\end{array}$$
(15.6)
思考题 12-4 要求证明一个相似的递归公式产生的序列为卡塔兰数(Catalan numbers),这个序列的增长速度为$\Omega (4^n/n^{3/2})$。练习 15.2-3 要求证明递归公式(15.6)的结果为$\Omega (2^n)$。因此，括号化方案的数量与$n$呈指数关系，通过暴力搜索穷尽所有可能的括号化方案来寻找最优方案，是一个糟糕的策略。

应用动态规划方法
下面用动态规划方法来求解矩阵链的最优括号化方案，我们还是按照本章开头提出的 4个步骤进行：
1.刻画一个最优解的结构特征。
2.递归地定义最优解的值。
3.计算最优解的值，通常采用自底向上的方法。
4.利用计算出的信息构造一个最优解。
我们按顺序进行这几个步骤，清楚地展示针对本问题每个步骤应如何做。

步骤 1: 最优括号化方案的结构特征
动态规划方法的第一步是寻找最优子结构，然后就可以利用这种子结构从子问题的最优解构造出原问题的最优解。在矩阵链乘法问题中，此步骤的做法如下所述。为方便起见，我们用符号$A_{i..j}(i⩽j)$表示 $A_i{A}_{i+1}...A_j$ 乘积的结果矩阵。可以看出，如果问题是非平凡的，即 $i<j,那么$ 为了对$A_i{A}_{i+1}\cdots A_j$进行括号化，我们就必须在某个$A_k$和$A_{k+1}$之间将矩阵链划分开($k$为$i⩽k<j$ 间的整数)。也就是说，对某个整数$k$,我们首先计算矩阵$A_{i..k}$和$A_{k+\mathrm{1..}j}$,然后再计算它们的乘积得到最终结果$A_{i..j}$。此方案的计算代价等于矩阵 $A_{i..k}$的计算代价，加上矩阵 $A_k+\mathrm{1..}j$的计算代价， 再加上两者相乘的计算代价。
下面我们给出本问题的最优子结构。假设$A_i{A}_{i+1}\cdot \cdot \cdot A_j$的最优括号化方案的分割点在$A_k$和
$A_{k+1}$之间。那么，继续对“前缀”子链 $A_i{A}_{i+1}\cdots A_k$ 进行括号化时，我们应该直接采用独立求解它时所得的最优方案。这样做的原因是什么呢？如果不采用独立求解$A_i{A}_{i+1}\cdot \cdot \cdot A_k$所得的最优方案来对它进行括号化，那么可以将此最优解代人$A_i{A}_{i+1}\cdot \cdot \cdot A_j$的最优解中，代替原来对子链$A_i{A}_{i+1}\cdots A_k$进行括号化的方案(比 $A_i{A}_{i+1}\cdots A_k$ 最优解的代价更高),显然，这样得到的解比$A_i{A}_{i+1}\cdots A_j$原来的“最优解”代价更低：产生矛盾。对子链 $A_k+1A_{k+2}\cdots A_j$,我们有相似的结论： 在原问题$A_i{A}_{i+1}\cdot \cdot \cdot A_j$的最优括号化方案中，对子链$A_{k+1}{A}_{k+2}\cdot \cdot \cdot A_j$进行括号化的方法，就是它自身的最优括号化方案。
现在我们展示如何利用最优子结构性质从子问题的最优解构造原问题的最优解。我们已经看到，一个非平凡的矩阵链乘法问题实例的任何解都需要划分链，而任何最优解都是由子问题实例的最优解构成的。因此，为了构造一个矩阵链乘法问题实例的最优解，我们可以将问题划分为两个子问题($A_i{A}_{i+1}\cdots A_k$ 和$A_{k+1}{A}_{k+2}\cdots A_j$ 的最优括号化问题),求出子问题实例的最优解，然后将子问题的最优解组合起来。我们必须保证在确定分割点时，已经考察了所有可能的划分点， 这样就可以保证不会遗漏最优解。

步骤2：一个递归求解方案
下面用子问题的最优解来递归地定义原问题最优解的代价。对矩阵链乘法问题，我们可以将对所有$1⩽i⩽j⩽n$确定$A_i{A}_{i+1}\cdot \cdot \cdot A_j$的最小代价括号化方案作为子问题。令$m[i,j]$表示计算矩阵 $A_{i..j}$所需标量乘法次数的最小值，那么，原问题的最优解——计算 $A_{\mathrm{1..}n}$所需的最低代价就是$m[1,n]$。
我们可以递归定义 $m[i,j]$如下。对于 $i=j$ 时的平凡问题，矩阵链只包含唯一的矩阵$A_i..i=$ $A_i$,因此不需要做任何标量乘法运算。所以，对所有 $i=1,2,\cdot \cdot \cdot ,n,m[i,i]=0$。若$i<j$,我们利用步骤1 中得到的最优子结构来计算$m[i,j]$。我们假设$A_i{A}_{i+1}\cdot \cdot \cdot A_j$的最优括号化方案的分割点在矩阵 $A_k$ 和$A_k+1$之间，其中 $i⩽k<j$。那么，$m[i,j]$就等于计算 $A_i.k$ 和$A_k+\mathrm{1..}$,的代价加上两者相乘的代价的最小值。由于矩阵 $A_i$ 的大小为$p_{i-1}\times p_i$,易知$A_{i\dots k}$与$A_{k+1\dots j}$相乘的代价为$p_i-1$ $p_k{p}_j$次标量乘法运算。因此，我们得到
$$m[i,j]=m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j$$
此递归公式假定最优分割点$k$是已知的，但实际上我们是不知道的。不过，$k$只有$j-i$种可能的取值，即$k=i,i+1,...,j-1$。由于最优分割点必在其中，我们只需检查所有可能情况， 找到最优者即可。因此，$A_i{A}_{i+1}\cdot \cdot \cdot A_j$最小代价括号化方案的递归求解公式变为：
m [ i , j ] = { 0 如果  i = j min ⁡ i ≤ k < j { m [ i , k ] + m [ k + 1 , j ] + p i − 1 p k p j } 如果  i < j m[i,j]=\left\{\begin{matrix}{0}&{\text{如果 }i=j}\\{\min_{i\leq k<j}\{m[i,k]+m[k+1,j]+p_{i-1}p_{k}p_{j}\}}&{\text{如果 }i<j}\\\end{matrix}\right. m[i,j]={0mini≤k<j​{m[i,k]+m[k+1,j]+pi−1​pk​pj​}​如果 i=j如果 i<j​
(15.7)
$m[i,j]$的值给出了子问题最优解的代价，但它并未提供足够的信息来构造最优解。为此， 我们用 s[$i,j]$保存 A$A_i{A}_{i+1}\cdot \cdot \cdot A_j$ 最优括号化方案的分割点位置$k$,即使得 $m[i,j]=m[i,k]+$ $m[k+1,j]+p_{i-1}{p}_k{p}_j$ 成立的$k$ 值。

步骤 3: 计算最优代价
现在，我们可以很容易地基于递归公式(15.7)写出一个递归算法，来计算$A_1{A}_2\cdot \cdot \cdot A_n$相乘的
最小代价$m[1,n]$。像我们在钢条切割问题一节中所看到的，以及即将在 15.3 节中看到的那样，此递归算法是指数时间的，并不比检查所有括号化方案的暴力搜索方法更好。
注意到，我们需要求解的不同子问题的数目是相对较少的：每对满足 1$⩽i⩽j⩽n$的$i$和$j$ 时应一个唯一的子问题，共有$\left(\genfrac{}{}{0ex}{}{n}{2}\right)+n=\Theta (n^2)$个。递归算法会在递归调用树的不同分支中多次遇到同一个子问题。这种子问题重叠的性质是应用动态规划的另一个标识(第一个标识是最优子结构)。
我们采用自底向上表格法代替基于公式(15.7)的递归算法来计算最优代价(我们将在 15. 3 节中给出对应的带备忘的自顶向下方法)。下面给出的过程 MATRIX-CHAIN-ORDER 实现了自底向上表格法。此过程假定矩阵${\mathcal{A}}_i$的规模为$p_{i-1}\times p_i(i=1,2,\cdots ,n)$。它的输人是一个序列$p=⟨p_0,p_1,\dots ,p_n⟩$,其长度为$p.length=n+1$。过程用一个辅助表$m\lfloor \mathrm{1..}n,\mathrm{1..}n\rfloor$来保存代价$m[i,j]$,用另一个辅助表 s[1…n-1,2…n]记录最优值 $m[i,j]$对应的分割点 $k$。我们就可以利用表 s 构造最优解。
为了实现自底向上方法，我们必须确定计算 $m[i,j]$时需要访问哪些其他表项。公式(15.7) 显示，$j-i+1$个矩阵链相乘的最优计算代价$m[i,j]$只依赖于那些少于$j-i+1$个矩阵链相乘的最优计算代价。也就是说，对 $k=i,i+1,...,j-1$, 矩阵 $A_{i..k}$是$k-i+1<j-i+1$ 个矩阵的积，矩阵 $A_{k+\mathrm{1..}j}$是$j-k<j-i+1$ 个矩阵的积。因此，算法应该按长度递增的顺序求解矩阵链括号化问题，并按对应的顺序填写表$m$。对矩阵链$A_i{A}_{i+1}\cdots A_j$最优括号化的子问题，我们认为其规模为链的长度$j-i+1$。

MATRIX-CHAIN-ORDER( $p)$
1 $n=p.length-1$
2 let $m[\mathrm{1..}n,\mathrm{1...}n]$and s$[\mathrm{1...}n-1,\mathrm{2..}n]$
//be new tables
3 $\text{for}i=1$to$n$
4 $m[i,i]=0$
5 for $l=2$ to $n$
// l is the chain length
6 for $i=1$ to $n-l+1$
7 $j=i+l-1$
8 $m[i,j]=\infty$
9 for $k=i\text{ to }j-1$
10 $q=m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j$
11 if $q<m[i,j]$
12 $m[i,j]=q$
13 $s[i,j]=k$
14 return $m$ and s

算法首先在第 3~4 行对所有$i=1,2,\cdots ,n$计算$m[i,i]=0$(长度为 1 的链的最小计算代价)。接着在第 5~13 行 for 循环的第一个循环步中，利用递归公式(15.7)对所有$i=1,2,\cdots$, $n-1$计算 $m[i,i+1]$(长度 $l=2$ 的链的最小计算代价)。在第二个循环步中，算法对所有$i=1$, 2,…,n-2 计算$m[i,i+2]$(长度$l=3$的链的最小计算代价),依此类推。在每个循环步中，第$1013$ 行计算代价 $m[i,j]$时仅依赖于已经计算出的表项 $m[i,k]$和 $m[k+1,j]$。
图 15-5 展示了对一个长度为 6 的矩阵链执行此算法的过程。由于我们定义 $m\lceil i,i\rceil$仅在 $i⩽j$ 时有意义，因此表$m$只使用主对角线之上的部分。图中的表是经过旋转的，主对角线已经旋转到了水平方向。矩阵链的规模列在了图的下方。在这种布局中，我们可以看到子矩阵链$A_i{A}_{i+1}..$ $A_j$ 相乘的代价$m[i,j]$恰好位于始于 $A_i$ 的东北至西南方向的直线与始于$A_j$ 的西北至东南方向的直线的交点上。表中同一行中的表项都对应长度相同的矩阵链。MATRIX-CHAIN-ORDER 按自下而上、自左至右的顺序计算所有行。当计算表项 $m[i,j]$时，会用到乘积 $p_{i-1}{p}_k{p}_j(k=i,i+$ $1,\cdots ,j-1)$,以及$m[i,j]$西南方向和东南方向上的所有表项。


我们将两个表进行了旋转，使得主对角线方向变为水平方向。表$m$只使用主对角线和上三角部分，表 s 只使用上三角部分。6 个矩阵相乘所需的最少标量乘法运算次数为$m[1,6]=15125$。表中有些表项被标记了深色阴影，相同的阴影表示过程在第 10 行中计算 $m[2,5]$时同时访问了这些表项：
$$m[2,5]=\min \{\begin{array}{llc}m[2,2]+m[3,5]+p_1{p}_2{p}_5=0+2500+35\bullet 15\bullet 20& =13000& \\ m[2,3]+m[4,5]+p_1{p}_3{p}_5& =2625+1000+35\bullet 5\bullet 20& =7125\\ m[2,4]+m[5,5]+p_1{p}_4{p}_5& =4375+0+35\bullet 10\bullet 20& =11375\end{array}$$
$$=7125$$
简单分析 MATRIX-CHAIN-ORDER 的嵌套循环结构，可以看到算法的运行时间为$O(n^3)$。循环嵌套的深度为三层，每层的循环变量($l$、$i$和$k$)最多取$n-1$个值。练习 15.2-5 要求证明此算法的运行时间实际上是$\Omega (n^3)$。算法还需要$\Theta (n^2)$的内存空间来保存表$m$和 s。因此， MATRIX-CHAIN-ORDER 比起穷举所有可能的括号化方案来寻找最优解的指数阶算法要高效得多。
步骤4：构造最优解

虽然 MATRIX-CHAIN-ORDER 求出了计算矩阵链乘积所需的最少标量乘法运算次数，但它并未直接指出如何进行这种最优代价的矩阵链乘法计算。表 s[1…n-1,2…n]记录了构造最优解所需的信息。每个表项 s[i,j]记录了一个$k$值，指出 $A_i{A}_{i+1}\cdot \cdot \cdot A_j$ 的最优括号化方案的分割点应在$A_k$ 和$A_{k+1}$之间。因此，我们知道 $A_{\mathrm{1...}n}$的最优计算方案中最后一次矩阵乘法运算应该是$A_{1\dots [1,n]}{A}_{[1,n]+1\dots n}$我们可以用相同的方法递归地求出更早的矩阵乘法的具体计算过程，因为 $s[1,s[1,n]]$指出了计算 A 1 … { 1 , n ] A_{1\ldots\{1,n]} A1…{1,n]​时应进行的最后一次矩阵乘法运算；s[s[1,n]+1,n]!指出了计算 A { 1 , n ] + 1 … n A_{\{1,n]+1\ldots n} A{1,n]+1…n​时应进行的最后一次矩阵乘法运算。下面给出的递归过程可以输出$⟨A_i,A_{i+1},\cdots$, $A_{\mathrm{j}}⟩$的最优括号化方案，其输人为 MATRIX-CHAIN-ORDER 得到的表 s 及下标$i$和$j$。调用PRINT-OPTIMAL-PARENS(s,1,n)即可输出$⟨A_1,A_2,...,A_n⟩$的最优括号化方案。

PRINT-OPTIMAL-PARENS(s,i,j)
1 if $i=j$
2 $print“A”$
3 else print“("
4 PRINT-OPTIMAL-PARENS(s,i,s[i,j]).
5 PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)
6 $print“)”$

对图 15-5 中的例子，调用 PRINT-OPTIMAL-PARENS(s,1,6)输出括号化方案
$$((A_1(A_2{A}_3))((A_4{A}_5)A_6))$$

四、动态规划原理

虽然我们已经用动态规划方法解决了两个问题,但你可能还是弄不清应该在何时使用动态规划。从工程角度看,在什么情况下应该寻求用动态规划方法求解问题呢?在本节中,我们关注适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。我们还会再次讨论备忘方法,更深入地讨论在自顶向下方法中如何借助备忘机制来充分利用子问题重叠特性。

最优子结构
用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如前文所述，如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个好线索(当然，具有最优子结构性质也可能意味着适合应用贪心策略)。使用动态规划方法时，我们用子问题的最优解来构造原问题的最优解。因此，我们必须小心确保考察了最优解中用到的所有子问题。
本章到目前为止介绍的两个问题都具有最优子结构性质。在前面，我们知道，长度为$n$的钢条的最优切割方案是由第一次切割后(如果最优切割方案需要进行切割)得到的两段钢条的最优切割方案组成的。在前面，我们看到$A_i{A}_{i+1}\cdot \cdot \cdot A_j$的最优括号化方案首先在$A_k$和$A_{k+1}$之间进行划分，然后对 $A_{:}{A}_{i+1}\cdot \cdot \cdot A_k$ 和$A_{k+1}{A}_{k+2}\cdot \cdot \cdot A_j$ 继续进行最优括号化。
你会发现，在发掘最优子结构性质的过程中，实际上遵循了如下的通用模式：
1.证明问题最优解的第一个组成部分是做出一个选择，例如，选择钢条第一次切割位置，选择矩阵链的划分位置等。做出这次选择会产生一个或多个待解的子问题。
2.对于一个给定问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。
3. 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。
4. 利用“剪切一粘贴”(cut-and-paste)技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。证明这一点是利用反证法：假定子问题的解不是其自身的最优解，那么我们就可以从原问题的解中“剪切”掉这些非最优解，将最优解“粘贴”进去，从而得到原
问题一个更优的解，这与最初的解是原问题最优解的前提假设矛盾。如果原问题的最优解包含多个子问题，通常它们都很相似，我们可以将针对一个子问题的“剪切一粘贴”论证方法稍加修改，用于其他子问题。
一个刻画子问题空间的好经验是：保持子问题空间尽可能简单，只在必要时才扩展它。例如，我们在求解钢条切割问题时，子问题空间中包含的问题为：对每个$i$值，长度为$i$ 的钢条的最优切割问题。这个子问题空间很有效，因此我们不必尝试更一般性(从而也更大)的子问题空间。
与之相对的，假定我们试图限制矩阵链$A_1{A}_2\cdot \cdot \cdot A_j$乘法问题的子问题空间。如前所述，最优括号化方案必然在某个位置 $k(1⩽k<j)$处，即 $A_k$ 和$A_{k+1}$之间对矩阵链进行划分。除非我们能保证$k$永远等于$j-1$,否则我们会发现得到两个形如$A_1{A}_2\cdot \cdot \cdot A_k$和$A_{k+1}{A}_{k+2}\cdot \cdot \cdot A_j$的子问题，而后者的形式与$A_1{A}_2\cdots A_j$是不同的。因此，对矩阵链乘法问题，我们必须允许子问题在“两端”都可以变化，即允许子问题 $A_i{A}_{i+1}\cdots A_j$ 中$i$ 和$j$ 都可变。
对于不同问题领域，最优子结构的不同体现在两个方面：
1.原问题的最优解中涉及多少个子问题。
2.在确定最优解使用哪些子问题时，我们需要考察多少种选择。
在钢条切割问题中，长度为$n$的钢条的最优切割方案仅仅使用一个子问题(长度为$n-i$的钢条的最优切割),但我们必须考察$i$ 的$n$ 种不同取值，来确定哪一个会产生最优解。$A_i{A}_{i+1}\cdots A_j$ 的矩阵链乘法问题中，最优解使用两个子问题，我们需要考察$j-i$种情况。对于给定的矩阵链划分而且两个子问题都必须求解最优方案。一旦我们确定了子问题的最优解，就可以在$j-i$个候选的$k$ 中选取最优者。
我们可以用子问题的总数和每个子问题需要考察多少种选择这两个因素的乘积来粗略分析动态规划算法的运行时间。对于钢条切割问题，共有 $\Theta (n)$个子问题，每个子问题最多需要考察$n$种选择，因此运行时间为$O(n^2)$。矩阵链乘法问题共有$\Theta (n^2)$个子问题，每个子问题最多需要考察$n-1$种选择，因此运行时间为$O(n^3)$。
子问题图也可用来做同样的分析。图中每个顶点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。回忆一下，钢条切割问题的子问题图有$n$个顶点，每个顶点最多$n$条边，因此运行时间为$O(n^2)$。对于矩阵链乘法问题，子问题图会有 $\Theta (n^2)$个顶点，而每个顶点最多有$n-1$条边，因此共有$O(n^3)$个顶点和边。
在动态规划方法中，我们通常自底向上地使用最优子结构。也就是说，首先求得子问题的最优解，然后求原问题的最优解。在求解原问题过程中，我们需要在涉及的子问题中做出选择，选出能得到原问题最优解的子问题。原问题最优解的代价通常就是子问题最优解的代价再加上由此次选择直接产生的代价。例如，对于钢条切割问题，我们首先求解子问题，确定长度为$i=0$, $1,\dots ,n-1$的钢条的最优切割方案，然后利用公式(15.2)确定哪个子问题的解构成长度为$n$的钢条的最优切割方案。此次选择本身所产生的代价就是公式(15.2)中的$p_{\mathrm{i}}$。在矩阵链乘法问题中，我们先确定子矩阵链$A_i{A}_{i+1}\cdots A_j$的最优括号化方案，然后选择划分位置$A_k$,选择本身所产生的代价就是$p_{i-1}{p}_k{p}_j$。
“贪心算法”,它与动态规划有很多相似之处。特别是，能够应用贪心算法的问题也必须具有最优子结构性质。贪心算法和动态规划最大的不同在于，它并不是首先寻找子问题的最优解，然后在其中进行选择，而是首先做出一次“贪心”选择——在当时(局部)看来最优的选择——然后求解选出的子问题，从而不必费心求解所有可能相关的子问题。令人惊讶的是，在某些情况下这一策略也能得到最优解！

一些微妙之处
在尝试使用动态规划方法时要小心，要注意问题是否具有最优子结构性质。考虑下面两个问题，其中都是给定一个有向图G=(V,E)和两个顶点$u,v\in V$。
无权(unweighted)最短路径${}^{\mathrm{\Theta }}$:找到一条从$u$ 到$v$ 的边数最少的路径。这条路径必然是简单路径，因为如果路径中包含环，将环去掉显然会减少边的数量。
无权最长路径：找到一条从$u$到$v$的边数最多的简单路径。这里必须加上简单路径的要求，\因为我们可以不停地沿着环走，从而得到任意长的路径。
下面我们证明无权最短路径问题具有最优子结构性质。假设$u\ne v$,则问题是非平凡的。这样，从$u$ 到$v$ 的任意路径 $p$ 都必须包含一个中间顶点，比如 $w($注意，$w$可能是$u$ 或$v)$。因此， 我们可以将路径u->$v$ 分解为两条子路径$u$ ->$w$ ->$w$ ->$v$。显然，$p$ 的边数等于$p_1$ 的边数加上 $p_2$ 的边数。于是，我们断言：如果$p$是从$u$到$\upsilon$的最优(即最短)路径，那么$p_1$必须是从$u$到$w$的最短路径。为什么呢？我们可以用“剪切一粘贴”方法来证明：如果存在另一条从$u$ 到$w$ 的路径 $p_1^{\prime }$, 其边数比$p_1$少，那么可以剪切掉$p_1$,将$p_1^{\prime }$粘贴上，构造出一条比$p$边数更少的路径$u$ ,如$w$ $v$ 与$p$最优的假设矛盾。对称地，$p_2$必须是从$w$到$v$的最短路径。因此，我们可以通过考察所有中间顶点$w$来求$u$到$v$的最短路径，对每个中间顶点$w$,求$u$到$w$和$w$到$\upsilon$的最短路径，然后选择两条路径之和最短的顶点$w$。
你可能已经倾向于假设无权最长简单路径问题也具有最优子结构性质。毕竟，如果我们将最长简单路径u->$v$ 分解为两条子路径$u$ ->$w$ ->$w$ ->$v$，难道$p_1$不应该是从u到w的最长简单路径，$p_2$不应该是从w到u的最长简单路径吗？答案是否定的！图15-6给出了一个例子。思考路径$q\to r\to t$，它是从q到t的最长简单路径。$q\to r$是从q到r的最长简单路径吗? 不是的$q\to s\to t\to r$是一条更长的简单路径。$r\to t$是从r到t的最长简单路径吗?同样不是,$r\to q\to s\to t$比它更长。这个例子说明,最长简单路径问题不仅缺乏最优子结构性质,由子问题的解组合出的甚至都不是原问题的“合法”解。如果我们组合最长简单路径$q\to s\to t\to r$和$r\to q\to s\to t$,得到的是路径$q\to s\to t\to r\to q\to s\to t$,并不是简单路径。

的确，无权最长简单路径问题看起来不像有任何形式的最优子结构。对此问题尚未找到有效的动态规划算法。实际上，此问题是 NP完全的，这意味着我们不太可能找到多项式时间的求解方法。
为什么最长简单路径问题的子结构与最短路径有这么大的差别？原因在于，虽然最长路径问题和最短路径问题的解都用到了两个子问题，但两个最长简单路径子问题是相关的，而两个最短路径于问题是无关的(independent)。这里，于问题尢关的含义是，同一个原问题的一个子问题的解不影响另一个子问题的解。对图 15-6 中的例子，求$q$到$t$的最长简单路径可以分解为两个子问题：求$q$到$r$的最长简单路径和$r$到$t$的最长简单路径。对于前者，我们选择路径$q\to$ $s\to t\to r$,其中用到了顶点 s 和$t$。由于两个子问题的解的组合必须产生一条简单路径，因此我们在求解第二个子问题时就不能再用这两个顶点了。但如果在求解第二个子问题时不允许使用顶点 $t$,就根本尤法进行卜去了，因为$t$ 是原问题解的路径终点，是必须用到的，还不像子问题解的“接合”顶点$r$那样可以不用。这样，由于一个子问题的解使用了顶点 s和$t$,在另一个子问题的解中就不能再使用它们，但其中至少一个顶点在求解第二个子问题时又必须用到，而获得最优解则两个都要用到。因此，我们说两个子问题是相关的。换个角度来看，我们所面临的困境就是：求解一个子问题时用到了某些资源(在本例中是顶点),导致这些资源在求解其他子问题时不可用。

前面两节讨论的两个问题都具有子问题无关性质。在矩阵链乘法问题中，子问题为子链$A_i{A}_{i+1}\cdots A_k$和$A_{k+1}{A}_{k+2}\cdots A_j$的乘法问题。子链是互不相交的，因此任何矩阵都不会同时包含在两条子链中。在钢条切割问题中，为了确定长度为$n$的钢条的最优切割方案，我们考察所有长度为$i(i=0,1,...,n-1)$的钢条的最优切割方案。由于长度为$n$的问题的最优解只包含一个子问题的解(我们切掉了第一段),子问题无关性显然是可以保证的。

重叠子问题
适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够“小”,即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。一般来讲，不同子问题的总数是输入规模的多项式函数为好。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题(overlapping subproblems)性质${}^{\ominus }$（一个问题是否适合用动态规划求解同时依赖于子问题的无关性和重叠性，这看起来很奇怪。虽然这两个要求听起来似乎是矛盾的，但它们描述的是不同的概念，而不是同一个坐标轴上的两个点。两个子问题如果不共享资源，它们就是独立的。而重叠是指两个子问题实际上是同一个子问题，只是作为不同问题的子问题出现而已）。与之相对的，适合用分治方法求解的问题通常在递归的每一步都生成全新的子问题。动态规划算法通常这样利用重叠子问题性质： 对每个子问题求解一次，将解存人一个表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。
在前面，我们简单分析了钢条切割问题的递归算法是如何通过指数次的递归调用来求解小的子问题。而我们的动态规划算法将运行时间从递归算法的指数阶降为平方阶。
为了详细说明重叠子问题性质，我们重新考察矩阵链乘法问题。我们再看图 15-5,发现MATRIX-CHAIN-ORDER 在求解高层的子问题时，会反复查找低层上子问题的解。例如，算法会访问表项 $m[3,4]$ 次：分别在计算 $m[2,4]$、$m[1,4]$、$m[3,5]$和 $m[3,6]$时。如果我们每次都重新计算$m[3,4]$,而不是简单地查表，那么运行时间会急剧上升。为了更好地理解，请看下面的递归过程，它计算矩阵链乘法$A_{i.j}=A_i{A}_{i+1}\cdot \cdot \cdot A_j$所需最少标量乘法运算次数$m[i,j]$,而计算过程是低效的。这个过程直接基于递归式(15.7)。

RECURSIVE-MATRIX-CHAIN(p,i,j)
1 if $i=j$
2 return 0
3 $m[i,j]=\infty$
4 for $k=i$ to $j-1$
5 $q=$RECURSIVE-MATRIX-CHAIN$(p,i,k)$
+RECURSIVE-MATRIX-CHAIN(p,k+1,j).
$+p_{i-1}{p}_k{p}_j$
6 $\text{if }q<m[i,j]$
7$m[i,j]=q$
8 return $m[i,j]$

图 15-7 显示了调用 RECURSIVE-MATRIX-CHAIN(p,1,4)所产生的递归调用树。每个结点都标记出了参数$i$和$j$。可以看到，某些$i$、$j$值对出现了许多次。

实际上,我们可以证明此过程计算m[1,n]的时间至少是n的指数函数。令T(n)表示RECURSIVE-MATRIX-CHAIN计算n个矩阵的矩阵链的最优括号化方案所花费的时间。由于第$1\sim 2$行和第 6~7 行至少各花费单位时间，第 5 行的加法运算也是如此，因此我们得到如下递归式：
$$\begin{array}{rl}& T(1)⩾1\\ & T(n)⩾1+\sum _{k=1}^{n-1}\left(T(k)+T(n-k)+1\right),n>1\end{array}$$
注意，对 $i=1,2,...,n-1$,每一项 $T(i)$在公式中以 $T(k)$的形式出现了一次，还以 $T(n-$ $k)$的形式出现了一次，而求和项中累加了$n-1\dot{\text{个}1\text{,在求和项之前还加了}1}$,因此公式可改写为：
$$T(n)⩾2\sum _{i=1}^{n-1}T(i)+n$$
(15.8)
下面用代人法证明 $T(n)=\Omega (2^n$ )。特别地，我们将证明，对所有 $n⩾1,T(n)⩾2^{n-1}$都成立。基本情况很简单，因为$T(1)⩾1=2^{\circ }$,利用数学归纳法，对$n⩾2$,我们有
$(由公式(A.5))$
$$T(n)⩾2\sum _{i=1}^{n-1}{2}^{i-1}+n=2\sum _{i=0}^{n-2}{2}^i+n=2(2^{n-1}-1)+n$$
$$=2^n-2+n⩾2^{n-1}$$
因此，调用 RECURSIVE-MATRIX-CHAIN( $p,1,n$)所做的总工作量至少是$n$的指数函数。
将此自顶向下的递归算法(无备忘)与自底向上的动态规划算法进行比较，后者要高效得多， 因为它利用了重叠子问题性质。矩阵链乘法问题只有 $\Theta (n^2)$个不同的子问题，动态规划算法对每个子问题只求解一次。而递归算法则相反，对每个子问题，每当在递归树中(递归调用时)遇到它，都要重新计算一次。凡是一个问题的自然递归算法的递归调用树中反复出现相同的子问题， 而不同子问题的总数很少时，动态规划方法都能提高(有时还是极大地提高)效率。

重构最优解
从实际考虑，我们通常将每个子问题所做的选择存在一个表中，这样就不必根据代价值来重构这些信息。
对矩阵链乘法问题，利用表 s$\lfloor i,j\rfloor$,我们重构最优解时可以节省很多时间。假定我们没有维护 s[$i$,j]表，只是在表$m[i,j]$中记录了子问题的最优代价。当我们确定$A_i{A}_{i+1}\cdots A_j$的最优括号化方案用到了哪些子问题时，就需要检查所有$j-i$种 可 能 , 而 $j-i$并不是一个常数。因此， 对一个给定问题的最优解，重构它用到了哪些子问题就需花费 $\Theta (j-i)=\omega (1)$的时间。而通过在$s[i,j]$中保存 $A_i{A}_{i+1}\cdots A_j$ 的划分位置，我们重构每次选择只需 $O(1)$时间。

备忘
如我们在 15.1 节钢条切割问题中所见，我们可以保持自顶向下策略，同时达到与自底向上动态规划方法相似的效率。思路就是对自然但低效的递归算法加入备忘机制。与自底向上方法一样，我们维护一个表记录子问题的解，但仍保持递归算法的控制流程。
带备忘的递归算法为每个子问题维护一个表项来保存它的解。每个表项的初值设为一个特殊值，表示尚未填人子问题的解。当递归调用过程中第一次遇到子问题时，计算其解，并存人对应表项。随后每次遇到同一个子问题，只是简单地查表，返回其解${}^{\ominus }$。
下面给出的是带备忘的 RECURSIVE-MATRIX-CHAIN 版本。注意它与带备忘的自顶向下钢条切割算法的相似之处。

MEMOIZED-MATRIX-CHAIN§
1 $n=p.length-1$
2 let $m[1\dots n,1\dots n]$be a new table
3 for$i=1$to$n$
4 $\mathrm{for}j=i$ to $n$
5 $m[i,j]=\infty$
6 return LOOKUP-CHAIN(m,p,1,n)

LOOKUP-CHAIN($m,p,i,j)$
1 $\text{if }m[i,j]<\infty$
2 return $m[i,j]$
3 $\text{if }i==j$
4 $m[i,j]=0$
5 else for $k=i\text{to }j-1$
6 $q=$LOOKUP-CHAIN($m,p,i,k)$

• LOOKUP-CHAIN($m,p,k+1,j)+p_i-1p_{k}p$,

7 if $q<m[i,j]$
8 $m[i,j]=q$
9 return $m[i,j]$
MEMOIZED-MATRIX-CHAIN 与 MATRIX-CHAIN-ORDER 一样维护一个表$m[1\dots n$, $1\dots n$],来保存计算出的矩阵 $A_{i.j}$的最小计算代价 $m[i,j]$。每个表项被初始化为$\infty$,表示还未存人过值。调用 LOOKUP-CHAIN(m, $p,i,j$)时，如果第 1 行发现$m[i,j]<\infty$,就直接返回之前已经计算出的代价$m[i,j]$(第 2 行);否则，像 RECURSIVE-MATRIX-CHAIN 一样计算最小代价，存人$m[i,j]$,并返回。因此，虽然 LOOKUP-CHAIN($m,p,i,j)$总是返回 $m[i,j]$ 的值，但只在第一次(以特定的参数$i$和$j$ )调用时才真正计算。
图 15-7 说明了与 RECURSIVE-MATRIX-CHAIN 相比，MEMOIZED-MATRIX-CHAIN 是如何节省时间的。阴影子树表示那些直接查表获得而非重新计算的值。
与自底向上动态规划算法 MATRIX-CHAIN-ORDER 类似，MEMOIZED-MATRIX-CHAIN 的运行时间为$O(n^3)$。MEMOIZED-MATRIX-CHAIN 的第 5 行运行了 $\Theta (n^2)$次。我们可以将对LOOKUP-CHAIN 的调用分为两类：
1.调用时 $m[i,j]=\infty$, 因此第 3~9 行会执行。
2.调用时$m[i,j]<\infty$,因此 LOOKUP-CHAIN 执行第 2 行，简单返回值。
第一种调用会发生 $\Theta (n^2)$次，每个表项一次。第二种调用均为第一种调用所产生的递归调用。而无论何时一个 LOOKUP-CHAIN 的调用继续进行递归调用，都会产生 $O(n)$次递归调用。因此， 第二种调用共有 $O(n^3)$次，每次花费 O(1)时间，而第一种调用每次花费 $O(n)$时间再加上它产生的递归调用的时间。因此，算法的总时间为$O(n^3)$,备忘技术将一个 $\Omega (2^n)$时间的算法转换为一个 O(n${}^3$)时间的算法。
总之，为求解矩阵链乘法问题，我们既可以用带备忘的自顶向下动态规划算法，也可以用自底向上的动态规划算法，时间复杂性均为$O(n^3)$。两种方法都利用了重叠子问题性质。不同的子问题一共只有 $\Theta (n^2)$个，对每个子问题，两种方法都只计算一次。而没有备忘机制的自然递归算法的运行时间为指数阶，因为它会反复求解相同的子问题。
通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快(都是 $O(n^3)$时间，相差一个常量系数),因为自底向上算法没有递归调用的开销，表的维护开销也更小。而且，对于某些问题，我们可以利用表的访问模式来进一步降低时空代价。相反，如果子问题空间中的某些子问题完全不必求解，备忘方法就会体现出优势了，因为它只会求解那些绝对必要的子问题。