这里用矩阵链的乘法问题来说明动态规划算法的设计要素。
(A_1,A_2,..,A_n)表示(n)个矩阵的序列，其中(A_i)为(P_{i-1} imes P_i)阶矩阵，(i=1,2,...,n)。
向量(P=<P_0,P_1,P_2..P_i>)表示矩阵链的输入，其中(P_0)是(A_1)的行数，(P_1)是(A_1)的列数，(P_1)是(A_2)的行数，以此类推。
计算这个矩阵需要做(n-1)次两个矩阵的相乘运算，可以用(n-1)对括号表示运算次序。
因为矩阵乘法满足结合律，所以无论采用那种顺序，最后结果都一样，但是采用不同的顺序计算的工作量不同。如何定义两个矩阵相乘的工作量呢？
所以假设(A_1)有(i)行(k)列，(A_2)有(k)行(j)列。所以(A_1)(A_2)相乘后的矩阵有(i)行(j)列，含(ij)个元素。
以元素相乘作为基本运算，乘积中每个元素的计算都需要做j次乘法，于是计算(A_1A_2)总共需要(ijk)次乘法。
1.1具体实例
假设输入的是(P=<10,100,5,50>),说明有(3)个矩阵相乘。其中，
(A_1:10 imes 100)
(A_2:100 imes 50)
(A_3:5 imes50)
有两种乘法次序：
((A_1A_2)A_3)
(A_1(A_2A_3))
执行第一种运算的基本运算次序：(10 imes 100 imes5 + 10 imes 5 imes 50=7500)
执行第二种运算的基本运算次序：(10 imes 100 imes50 + 100 imes 5 imes 50=75000)
工作量相差达10倍！
所以我们的问题是：给定向量P，确定一种乘法次序，使得基本运算的总次数最少。
蛮力算法时间复杂度太大，这里先不讨论。
我们尝试用动态规划算法，从子问题的划分，递归方程的确定，递归和迭代的实现方法，复杂度分析等方面介绍动态规划算法。
1.2子问题的划分和递推方程
我们的优化目标是：基本运算次数的最小化。
如何界定子问题的边界？ 令(A_i..n)表示输入的矩阵链。
如果从前向后划分，得(A_{1..i})，i=1,2,...,n，得到的子问题只有后边界。但是在计算子问题(A_{1..j})，j>i时，我们不仅需要知道子问题(A_{1..i})，也得知道(A_{i+1..j})的信息。
这说明子问题的划分需要前后两个边界。
用(A_i..j)定义矩阵链(A_i,A_{i+1},..,A_j)相乘的子问题，(m[i,j])表示得到乘积(A_{i..j})所用到的最小基本运算次数。
假定最后一次乘积发生在矩阵链(A_{i..k})和(A_k+1..j)之间，即
(A_iA_{i+1}..A_j=(A_iA_{i+1}..A_k)(A_{k+1}A_{k+2}..A_j))
(k=i,i+1,...,j-1)
所以子问题(A_i..j)的计算依赖于子问题(A_i..A_k)和(A_{k+1}..A_j)的计算结果。
即(m[i,j])依赖于(m[i,k])和(m[k+1,j])的值。
k代表子问题的划分问题，考虑所有可能的划分，(i<=k<=j)，从中比较出最小的值。
(P_{i-1}P_kP_j)是最后把两个子矩阵链(A_{i..k})和(A_{k+1}..j)的结果矩阵相乘所做的基本运算次数。
当(i=j)时，矩阵链只有一个矩阵(A_i)，这时乘法次数是(0)，对应了递推式的初值。
所以这个问题是满足优化原则的。因为当(m[i,j])达到最小值时，子问题的优化函数值(m[i,k])和(m[k+1,j])也是最小的。
2.动态规划算法的递归实现
为了确定每次相乘时加括号的位置，需要设计表(s[i,j])记录(m[i,j])达到最小值时k的划分位置。
算法RecurMatrixChain(P,i,j)
输入：矩阵链(A_i..j)的输入为向量(P=<P_0,P_1,P_2..P_i>)，其中(i<=k<=j)
输出：计算(A_{i..j})的所需最小乘法次数(m[i,j])和最后一次运算的位置(s[i,j])
if i=j
then m[i,j] <- 0 ; s[i,j] <- i ; return m[i,j]
m[i,j] <- 无穷
s[i,j] <- i
for k <- i to j-1 do //考虑所有可能的划分位置
q <- RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + Pi-1PkPj
if q < m[i,j]
then m[i,j] <- q
s[i,j] <- k
return m[i,j]
求解n个矩阵相乘，只需代入i=1，j=n。
下面考虑时间复杂度
算法在行5执行for循环，k从1到n-1。
每次进入循环体都在行6进行两个子问题的递归求解，其余工作量都是常数时间。
化简得：
现在介绍一个定理：当(n>1)时，
证明：(n=2，T(2)>=C=C_12^{n-1}，C_1=C/2)为某个正数
假设对于任何小于n大于等于2的k，(T(k)>=C_12^{k-1})，则存在某个常数C’，使得
可以看到，通过使用了动态规划的设计思想，相比于蛮力算法，时间复杂度有所改善，但是并没有得到多项式时间的高效算法。为什么？
以矩阵链(A_{1..5})为例：
时间复杂度高的原因：在递归调用中同一个子问题被多次重复计算。
在整个递归计算中总计产生了(1+8+24+32+16=81)个子问题。
规模为1的子问题有5个，以此类推，得到不同的子问题个数只有(5+4+3+2+1=15)个
说明算法计算的81个子问题中有许多是重复的。
3.动态规划算法的迭代实现
迭代计算的关键
- 每个子问题只计算一遍
- 迭代过程
- 从最小子问题开始
- 考虑计算顺序，以保证后面用到的值前面已经计算好
- 存储结构保存计算结果--备忘录（存储子问题的优化函数值和划分边界）
- 解的追踪
- 设计标记函数标记每步的决策
- 考虑根据标记函数追踪解的算法
(r)为链长
算法MatrixChain(P,n)
输入：矩阵链(A_{1..n})的输入向量(P=<P_0,P_1,P_2..P_i>)
输出：计算(A_{i..j})的所需最小乘法次数(m[i,j])和最后一次运算的位置(s[i,j])
令所有的m[i,j]得初值为0
for r<-2 to n do //r为链长（子问题规模）
for i<-1 to n-r+1 //左边界i，n-r+1是最后一个r链的前边界
j<-i+r-1 //右边界
m[i,j] <- m[i+1,j] + Pi-1PiPj
s[i,j] <- i
for k<-i+1 to j-1 do
t<-m[i,k]+m[k+1,j]+Pi-1PiPj
if t<m[i,j]
then m[i,j]<-t
s[i,j]<-k
时间复杂度：
行2,3,7都是(O(n))，嵌套循环执行(O(n^3))次，内部为(O(1))，(W(n)=O(n^3))
解的追踪：
(S[1,5]=3 => (A_1A_2A_3)(A_4A_5))
(S[1,3]=1 => A_1(A_2A_3))
输出：
计算顺序：((A_1(A_2A_3))(A_4A_5))
最少的乘法次序：(m[1,5]=11875)
两种比较的实现：
递归实现：时间复杂度高，空间少
迭代实现：时间复杂度低，空间消耗多
原因：递归实现子问题多次重复计算，子问题计算次数呈指数增长。迭代实现每个子问题只计算一遍。
动态规划时间复杂度：
备忘录各项计算量之和+追踪解的工作量
通常追踪解的工作量不超过计算工作量，是问题规模的多项式函数