动态规划——Dynamic programming,可以说是本人一直没有啃下的骨头，这次我就得好好来学学Dynamic programming.

OK,出发！

动态规划通常是分治算法的一种特殊情况，它一般用于最优化问题，如果这些问题能够：

1.能够分解为规模更小的子问题

2.递归的子问题具有最优子结构性质。也就是说，原问题的最优化解能够通过子问题的解计算得到。

动态规划的一个核心的步骤就是定义一个合适的问题形式，动态规划与分治算法不一样，动态规划算法通常需要枚举所有的可能的切分策略，这是因为需要得到最优解；除此之外，动态规划通过“记录已计算子问题的解”来避免重复计算。

为了使用动态规划的方法，那么我们首先得先看问题能够使用分治的方法来解决。给定一个问题，我们需要先看看他的核心输入数据结构是否可以分解。如果发现输入的核心数据结构为：

数组矩阵集合树图

那么这些输入是很容易分解的。

我们再看，子问题的输出能够构成原问题的输出。

如果上面两个条件都满足，那么这个问题当然是可以使用分治法来解决的。

下面，我们通过几个经典的问题来看看如何由分治过渡到动态规划。

矩阵连乘问题

INPUT:

给定：A1,A2,…,AnA_{1},A_{2},\dots,A_{n}A1​,A2​,…,An​n个矩阵，矩阵AiA_{i}Ai​的形状为pi−1×pip_{i-1}\times p_{i}pi−1​×pi​

OUTPUT:

给出一个A1,A2,…,AnA_{1},A_{2},\dots,A_{n}A1​,A2​,…,An​的运算顺序，使得乘法的次数最少。

先看看为啥不同运算顺序，会造成乘法的次数不一样呢？

假设有三个矩阵：

A1的形状为1×2,A2的形状为2×3,A3形状为3×4A_{1}的形状为1 \times 2,A_{2}的形状为2\times 3,A_{3}形状为3 \times 4A1​的形状为1×2,A2​的形状为2×3,A3​形状为3×4

那么第一种运算顺序：(A1A2)A3(A_{1}A_{2})A_{3}(A1​A2​)A3​，需要的乘法次数为：1x2x3+1x3x4=18

第二种运算顺序：A1(A2A3)A_{1}(A_{2}A_{3})A1​(A2​A3​)，需要的乘法次数为2x3x4+1x2x4=32。

那么第一种运算次数更少，因此第一种运算顺序更好。

当直接给n个矩阵的时候，我们是不好下手的，也没有啥头绪。那我们就想，

我们就先看n=1,2,3,4的时候嘛。

当n=1的时候，不要乘了。

当只有2个矩阵相乘的时候，没有什么最优的，就只有一种运算顺序，我们看到会做的；

当只有3个矩阵相乘的时候，我们也会做的，就是只要像上面的例子一样去比较就是了的。

当有四个矩阵的时候呢？能不能划为先三个矩阵相乘再两个矩阵相乘？或者左边两个矩阵，右边两个矩阵，两个中间结果再乘起来？因为，我们会做2个和3个矩阵相乘了。

当有5个矩阵呢？

我们看到，当n很小的时候，我们是会做的。那么给定一个很大的n,我们能不能把它转换为规模更小的n呢？

假设我们把这个问题看做一个多阶段决策问题，每次的决策就是选一个位置加一个括号。

OK,假设我们已经得到最优的解了。那么这个最优解的最后一次乘法，一定可以看成是两个部分的乘积。也就是说从：

A1A2…AkAk+1…AnA_{1}A_{2} \dots A_{k} A_{k+1} \dots A_{n}A1​A2​…Ak​Ak+1​…An​

选择一个k,使得最终的结果是从:

(A1A2…Ak)(Ak+1…An)(A_{1}A_{2} \dots A_{k})( A_{k+1} \dots A_{n})(A1​A2​…Ak​)(Ak+1​…An​)

两部分乘积得到。

这下子好了，左边的连乘就是A1A2…AkA_{1}A_{2} \dots A_{k}A1​A2​…Ak​,这个问题和原问题很像啊，就是规模改了一下，内容不一样而已。右边也是类似的。

然后，我们先解决A1A2…AkA_{1}A_{2} \dots A_{k}A1​A2​…Ak​,显然这个问题，也可以看成最后由两个矩阵乘积得到，也就是要选择一个j使得：(A1A2…Aj)(Aj+1…Ak)(A_{1}A_{2} \dots A_{j})( A_{j+1}\dots A_{k})(A1​A2​…Aj​)(Aj+1​…Ak​)

等等···

经过若干次的分析以后，我们就开始看到我们所要解决问题的通用形式了：寻找某个运行顺序，使得AiAi+1…AjA_{i}A_{i+1} \dots A_{j}Ai​Ai+1​…Aj​的乘法次数最少。定义OPT(i,j)OPT(i,j)OPT(i,j)表示AiAi+1…AjA_{i}A_{i+1} \dots A_{j}Ai​Ai+1​…Aj​所需的最少的乘法次数。原问题其实就是在求OPT(1,n)OPT(1,n)OPT(1,n)

而将原问题分解为两个子问题：OPT(1,k)OPT(1,k)OPT(1,k)和OPT(k,n)OPT(k,n)OPT(k,n)，那么原问题的解可以通过OPT(1,n)=OPT(1,k)+OPT(k,n)+p0×pk×pnOPT(1,n)=OPT(1,k)+OPT(k,n)+p_{0}\times p_{k} \times p_{n}OPT(1,n)=OPT(1,k)+OPT(k,n)+p0​×pk​×pn​得到。

这是因为左边A1A2…AkA_{1}A_{2} \dots A_{k}A1​A2​…Ak​得到一个p0×pkp_{0}\times p_{k}p0​×pk​的矩阵，而右边Ak+1Ak+2…AnA_{k+1}A_{k+2}\dots A_{n}Ak+1​Ak+2​…An​是一个pk×pnp_{k} \times p_{n}pk​×pn​的矩阵。左右两个矩阵相乘需要的乘法次数就是p0×pk×pnp_{0}\times p_{k} \times p_{n}p0​×pk​×pn​

到目前为止，so far so good! 然鹅！第一阶段里面的k

(A1A2…Ak)(Ak+1…An)(A_{1}A_{2} \dots A_{k})( A_{k+1} \dots A_{n})(A1​A2​…Ak​)(Ak+1​…An​)

k到底是谁啊？我们其实是不知道的，那怎么办呢？

那就没办法了，只有枚举所有的可能,即：k=1试一下，k=2试一下，k=3试一下,一共有n个可能。然后选其中使得乘法次数最少的k。

即：

OPT(1,n)=min(OPT(1,k)+OPT(k,n)+p0pkpn∣k=1,2,3,...,n)OPT(1,n)=min(OPT(1,k)+OPT(k,n)+p_{0}p_{k}p_{n}|k=1,2,3,...,n)OPT(1,n)=min(OPT(1,k)+OPT(k,n)+p0​pk​pn​∣k=1,2,3,...,n)

于是，我们很快写出这个算法的伪代码：

find_min(i,j)1. if i=j then2. return 0 //只有一个矩阵3. endif4. if i=j-1 then5. return p[i-1]p[i]p[i+1] //两个矩阵6. endif7. min=p[i-1]p[i]p[j] //随便设置一个初始的最小值8. for k=i to j do9. tmp = find_min(i,k)+find_min(k+1,j)+p[i-1] * p[k] *p[j]10. if tmp < min then11. min=tmp12. endif13. endfor14. return min

显然，这段代码是可以工作的！但是这段代码的复杂度是很高的哇！这里复杂度是O(2n)O(2^{n})O(2n)

为什么呢？这主要因为里面有很多重复计算的过程。

例如，对于A1A2A3A4A5A_{1}A_{2}A_{3}A_{4}A_{5}A1​A2​A3​A4​A5​,当我们把k分别选择为2,3的时候。

K=2的情况：

左边：A1A2A_{1}A_{2}A1​A2​,右边：A3A4A5A_{3}A_{4}A_{5}A3​A4​A5​。

假设，我们已经求解出来K=2的情况的乘法次数。

K=3的情况：

左边：A1A2A3A_{1}A_{2}A_{3}A1​A2​A3​,右边：A4A5A_{4}A_{5}A4​A5​

K=3的时候，在解决左边的子问题的时候，必然会遇到求解A1A2A_{1}A_{2}A1​A2​的问题，而我们的算法不管之前计算得到的结果，又会再计算一次。从而造成复杂度过高。如果我们能够有一个表来记录中间结果就好啦！

改进版本2：

find_min_beta(i,j)1. if table[i,j] != null then2. return table[i,j]3. if i=j then4. table[i,j]=05. return table[i,j]6. end if7. if i=j-1 then8. table[i,j]=p[i-1]p[i]p[i+1]9. return table[i,j]10. end if 11. min=p[i-1]p[i]p[j]12. for k=i to j do13. tmp = find_min_beta(i,k)+find_min_beta(k+1,j)+p[i-1]p[k]p[j]14. if tmp < min then15. min=tmp 16. endif17. endfor18. return min

这样子就可以解决重复计算的问题。

但一个原因就是，每次分解问题的规模只减少1，可以预想find_min(1,n)至少到递归n层。当n比较大的时候，函数栈就会花很多空间来维护栈结构，这也是很浪费内存的事情。为此，我们可以将递归转换为非递归。

改进版本3：

find_min_alpha(1,n)1.for i=1 to n do2.table[i,i]=03.end for4.for j=2 to n do5.for i=1 to n-j do6.min=p[i-1]p[i]p[i+1]7.for k=i to i+j do8.tmp =table[i,k]+table[k+1,i+j] +p[i-1]p[k]p[i+j]9.if tmp<min then10.min=tmp11.end if12.end for13.table[i,i+j]=min14.end for15.end for16.return table[1,n]

此时，该算法的复杂度就是O(n3)O(n^{3})O(n3)!我们可以看到，不同的实现时间复杂度会很有很大的不同！