以第二个为例，即A1*A2*A3*A4的乘法数等于，（A1*A2）的乘法数加上(A3*A4)的乘法数，再加上最后一步的乘法数，即将A1*A2的结果与A3*A4的结果相乘发生的乘法数。q0q2q3分别为A1的行数（-1是因为它的行数为前一个矩阵的列数，为了同一就将q定义为列了），A2的列数，A4的列数。

推广到n即为m[1,n]=m[1,k]+m[k+1,n]+p1p2p3，分别代表A1的行数，Ak的列数，An的列数。

4.判断是否能用动态规划来解决问题

1.判断是否具有优化子结构

这里还是用4个矩阵来举例：

我们要寻找的是m[1,4]的优化解子结构，也就是判断当m[1,4]达到最小值的时候，最后添加的括号前的内容和括号后的内容是否能同时达到最小值，即

如果是(a)的情况使m[1,4]最小的话，那么就要证明m[1,1]与m[2,4]也是最小的；

如果是(b)的情况使m[1,4]最小的话，那么就要证明m[1,2]与m[3,4]也是最小的；

如果是(c)的情况使m[1,4]最小的话，那么就要证明m[1,3]与m[4]也是最小的；

推广到n即为当m[1,n]最小的话，设最后划分位置为k，此时m[1,k]与m[k+1,n]最小，下面来证明。

假设当m[1,n]最小时，m[1,k]不是最小的

由于m[1,n]=m[1,k]+m[k+1]+q1q2q3，q1q2q3对于同一个k来说是定值，那么m[1,n]就不是最小的，与假设矛盾，所以m[1,k]与m[k+1,n]的划分方式得到的值一定是最小的。

因此具有优化子结构。

2.判断子问题重叠性

这个是动态规划的关键所在，我们还是拿四个矩阵举例，得到下图：

黄色的部分和蓝色的部分说明有的子问题被重复进行了计算，所以满足子问题的重叠性。

5. 找到最初值并画图

假设求解5个矩阵，那么我们的目标就是求m[1,5]的最小值。

m[1,5]的子问题有m[1,1],m[1,2],m[1,3],m[1,4]

? ? ? ? ? ? ? ? ? ? ? ? ? m[5,5],m[4,5],m[3,5],m[2,5]

那么我们就可以画图（有两个子问题通常画成三角形，将最终问题放在右上角）：

?6.求解

自底向上运算，显然m[1,1],m[2,2],m[3,3],m[4,4],m[5,5]是为0的，可以直接记录。

m[1,2]=m[1,1]+m[2,2]+p1p2p3只有这一种情况即为最优解了，同理m[2,3],m[3,4],m[4,5]等也只有一种情况，即也为最小值，直接记录即可。

?m[1,3]有两种情况，即为m[1,3]=m[1,2]+m[3,3]+q1q2q3? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? m[1,3]=m[1,1]+m[2,3]+q1p2q3

其中q1为A1的行，q2为A2的列，q3为A3的列，p2为A1的列（这个根据矩阵的知识是可以看出来的）。

我们在表格中记录的是m[1,3]的两种情况的最小值，直到计算到m[1,5]，就得到了m[1,5]的最小代价，也就是最小乘法数。

我们的计算顺序是这样的，自下向上计算：

?那我们是怎样画的括号呢？

?我们在计算m[i][j]的最小值后，需要将在哪个地方划分的来填入表格中，比如m[2][5]就是在3处划分的时候得到的值是最小的，那么就在表格中填上3。

根据上面表格，m[1,6]的值是3，所以是在3处划分即

(A1*A2*A3)*(A4*A5*A6)此时我们再寻找m[1,3]与m[4,6]的值，分别为1,5那么就是在1和5处划分的即：(A1*(A2*A3))*((A4*A5*)A6)这样即为最小代价。

7.伪代码实现

input:每个矩阵的行和列
output:最优解和记录位置的s矩阵

Matrix-Chain-Order(p)
FOR  i=1  TO  n  DO     
         m[i, i]=0;//将最底层的m[1,1]m[2,2]等置为0
FOR  l=2  TO  n  DO
        FOR  i=1  TO  n-l+1  DO  
               j=i+l-1;
              m[i, j]=∞; 将第l层的元素初始化为无穷大
          FOR  k<--i  To  j-1  DO 通过k找到每种情况子问题的位置 
             q = m[i, k]+m[k+1, j]+pi-1pkpj //计算大小
             IF q<m[i, j] THEN m[i,j]=q，s[i,j]=k;//找到最小值并记录下来，s数组记录位置
Return m and s

?8.算法复杂性计算

时间复杂性：共有三层循环，所以为O(n^3)，而通过枚举法计算的复杂度是指数的，数学好的可以计算一下，反正我是不会。。。。

空间复杂性：使用了二维数组所以为O(n^2)

4.最长公共子序列问题

1.问题的定义

1.子序列

X=(A,B,C,B,D,B)

Z=(B,C,D,B)是X的子序列。

W=(B,D,A)不是X的子序列。

2.公共子序列

Z是序列X与Y的公共子序列，即如果Z是X的公共子序列，那么也是Y的公共子序列。

输入：X=(x1,x2,x3,x4……xn),Y=(y1,y2,y3,……ym)。

输出：Z=X与Y的最长公共子序列的长度。

2.根据问题建立问题数组

我们要求X与Y的最长子序列，就可以建立一个数组C把它的值定义为子序列的长度，把它的值定义为它的下标一定和X序列与Y序列有关的，我们可以Xi定义为X序列的前i个元素的序列，Yj定义为Y的前j个元素的序列，那么C[i,j]表示的就是Xi与Yj的最长公共子序列的长度（以后都用LCS表示），那么我们要求的整个问题就是C[n,m]的最大值。

3.寻找原问题与子问题的关系（根据原问题的最后一步判断一个问题有多少个子问题）

我们求最大公共子序列的最后一步一定是判断xn与ym是否相等，我们就可以根据这一点来划分子问题：

当xn与ym相等时，C[n,m]=C[n-1,m-1]+1

当xn与ym不相等时，C[n,m]=C[n-1,m]

? ? ? ? ? ? ? ? ? ? ? 或者? ? ?C[n,m]=C[n,m-1]

4.判断是否能用动态规划来解决问题

1.判断优化子结构

显然，C[n,m]与它的子问题都是线性关系，当C[n,m]达到最大值的时候，它的子问题一定达到了最大值。

2.判断子问题的重叠性

当我们计算C[n,m]时，出现了三个子问题，当我们计算C[n-1,m]子问题时，出现了C[n,m]中的子问题C[n-1,m-1]所以子问题具有重叠性。

5.找到最初值并画图

显然最初值为含有0的，不能由其他数加一得到的，假设X的长度为3,Y的长度为4，那么初值就有C[0,0],C[1,0],C[2,0],C[3,0],C[0,1],C[0,2],C[0,3],C[0,4]。这些值都是0。

?C[3,4]就是我们要求的值。

6.求解

举一个例子呀：假如计算的是C[2,3]首先得判断x2与x3是否相等，如果相等那么C[2,3]就等于C[1,2]+1,如果不相等C[2,3]就是C[1,3]与C[2,2]中的最大值。

那么最大子序列是什么呢？

箭头的意思是，这个值是根据它周围的哪一个数字得到的，每出现一次斜上方的箭头就表示出现了一次字符相等，我们从C[8,10]的箭头出发，沿着箭头方向走：

?经过的斜向上箭头的位置就是最长子序列的位置。画出的顺序一定是从上向下和从左向右的，因为子序列是有顺序的。

7.伪代码实现

 LCS-length(X, Y)
 m<--length(X)；n<--length(Y)；
      For   i<--0   To   m   Do   C[i,0]<--0;
      For   j<--0   To   n    Do   C[0,j]<--0;//将初值都赋值为0
      For   i<--1   To   m   Do
           For   j<--1   To   n   Do
               If  xi = yj //判断两字符是否相等
               Then C[i,j]<--C[i-1,j-1]+1；B[i,j]<--“↖”;若相等C[i,j]为C[i-1,j-1]+1 
               Else If C[i-1,j]<--C[i,j-1]
                       Then C[i,j]<--C[i-1,j]; B[i,j]<--“↑”;
                       Else C[i,j]<--C[i,j-1]; B[i,j]<--“←”; //若不等取最大的
   Return C and B. 



Print-LCS(B, X, i, j)//这是打印字符串的函数
IF  i=0  or  j=0  THEN  Return;
IF  B[i, j]=“↖”  //如果是斜上方箭头则直接打印
THEN  Print-LCS(B, X, i-1, j-1);  Print xi; 
ELSE   If   B[i, j]=“↑”  
             THEN   Print-LCS(B, X, i-1, j);//如果是上方箭头则向上走一步再递归调用
             ELSE   Print-LCS(B, X, i, j-1).//如果是左侧箭头则向左走一步再递归调用

?8.算法复杂度

时间复杂度：代码中有两层循环，所以为O(mn)

空间复杂度：建立了二维数组，所以为O(mn)

5.01背包问题

1.问题定义

设给n个物品和一个背包，物品i的重量是wi，价值是vi，背包容量为C，问如何选择装入背包的物品，使装入背包的价值最大。

输入：C，wi，vi

输出：(x1,x2,x3……xn){x=0,1}满足，当Σwixi<C时，Σvixi最大。

2.根据问题建立问题数组

通过分析题干，建立问题数组m()表示在1~n个物品中怎样选择是最大的，但我们同时需要将背包容量考虑进去，所以一定有一个变量的位置是给背包容量的另一个变量是给物品的，那我们不妨定义m(i,j)，表示可选i~n这些物品，背包容量为j，此时vixi的值。我们要求的原问题就可以用m(1,C)来表示。它的子问题就是m(2,C),m(1,C-w1)等等。

3.寻找原问题与子问题的关系（根据原问题的最后一步判断一个问题有多少个子问题）

要求m(1,C)，最后一步一定是将一个物品装入背包（判断能不能装入），根据我们对c(i,j)的定义，最后一件物品一定是第一件物品。

我们可以根据最后一件物品是否要装划分子问题：

m(1,C)=m(2,C)当第一件物品不装入时。

m(1,C)=m(2,C-w1)+v1，当装入第一件物品时，由于总容量是C不能改变，所以需要减去第一件物品的质量，最后再加上第一件物品的价值。

推广到第i个元素

m(i,j)=m(i+1,j) 当不装入第i个元素时

m(i,j)=m(i+1,j-wi)+vi当装入第i个元素时

4.判断是否可以用动态规划解决问题

1.判断优化子结构

由于问题与子问题之间都是线性关系，且对于一个问题来说vi的值是固定的，所以m(i,j)达到最大值时，它的子问题一定也达到了最大值，所以具有优化子结构。

2.子问题的重叠性

对于m(1,C)=m(2,C-w1)+v1当求解m(1,C-w1)时，也需要计算m(1,C-w1)，所以具有子问题的重叠性。

5.找到最初值并画图

假设要计算01背包问题，给定价值数组v={7,3,6,10,8}，给定质量数组w={5,2,2,6,4}求解如何放入得到的总价值最大。

m(i,j)表示容量为j，在i~5中选择放入。

我们可以找到i与j的取值，根据取值画出表格。

初值：当j小于整个物品质量的最小值的时候为0 ，当只放一个物品时，小于这个物品质量的背包放0，大于该容量的放该物品的价值。

其实就是给第一列和最后一行进行赋值。

计算顺序为自下向上计算，直到计算出m(1,10)的值。

6.求解

在计算求得m(1,10)=19后，我们就要考虑它是经过哪几步来得到的，首先将1变成2，看下一行中是否有与之想等的数，若有相等的则这一行表示的元素就不存在，找到下一行中这个值的位置，如果有m(i,j)=j-wi那么就包含这一行的值。

如图：首先找到第一行m(1,10)=19的位置，查找下一行，发现m(2,10)是19，那么说明最优解不包含第一个元素，查找第三行10-2=8的位置，恰好是19-3=16所以包含第2个元素，然后查找第四行8-2=6的位置，发现是16-6=10，所以包含第三个元素，查找6-6=0的位置，发现是10-10=0，所以包含第四个元素，且背包已满。

综上包含2,3,4。

7.伪代码求解

For   j=0   To    min(wn-1, C)   Do
    m[n, j] = 0;//当背包容量装不下最后一个元素时，赋值为0
For   j=wn   To   C    Do
    m[n, j] = vn;//当可以装下时，赋值为n的价值vn
For   i=n-1   To   1   Do
        For   j=0   To   min(wi -1, C)    Do
              m[i, j] = m[i+1, j];//当装不下第i个元素时
        For   j=wi    To   C     Do
              m[i, j]=max{m[i+1, j], m[i+1, j-wi]+vi};//当装入第i个元素时，取两者的最小值
If  C<w1

6.最优二叉搜索树

1.问题定义

1.二叉搜索树

首先讲一下什么是二叉搜索树：

对于一棵二叉树来说：

1.左子树的所有节点小于根节点。

2.右子树的所有节点大于根节点。

3.左右子树都是二叉搜索树。

2.最优二叉搜索树

假设二叉搜索树的节点为{k1,k2,k3,……kn}

每一个节点都有一个权值{p1,p2,p3,p4……pn}

最优二叉搜索树即为所有权值与其搜索次数的乘积之和最小。即

E(T)=Σ(DEP(ki)+1)pi的最小值。

我们课件上是带有不确定叶节点d的，虽然每一个叶节点表示很多值，但究其本质还是计算概率和高度。

3.为什么要研究最优二叉搜索树

假如每一个节点代表一个英文字母，每个节点的权值表示的是该字母出现的概率，我们在查找英文字母的时候肯定是希望出现概率最多的字母更容易被查找到，搜索次数就是树高DEP(ki)+1，DEP表示的是深度，所以需要加一。因此我们需要计算E(T)的最小值。

输入：有序数组{k1,k2,k3,k4……kn}以及它们的权值{p1,p2,p3,p4……pn}

输出：一棵最优二叉搜索树的代价E(T)

2.根据问题建立问题数组

首先明确我们要求的是{k1,k2,k3……kn}所构成的最小二叉搜索树的权值，就可以定义一个函数E()表示它的权值。节点是从1到n的，而且是有序的那么就可以将参数设为1，n，我们要求的问题就变成了E(1,n)的值为多少。

它的子问题就可以写成：E(i,j)表示的是ki~kj节点构成的二叉搜索树的代价。

3.寻找原问题和子问题的关系（根据最后一步）

我们构成一棵树的最后一步是将两棵子树连接成一棵完整的树。虽然是连接成一棵树但是kr根节点是哪个我们并不清楚。

我们就可以根据这一点来探究E(1,n)与子问题的关系。

E(1,n)=E(左子树)+E(右子树)+Σpi

即E(1,n)=E(1,r-1)+E(r+1,n)+Σpi

由于r是不确定的，需要将1<r<n的都尝试一遍选择最小值。

推广到i,j

E(i,j)=E(i,r-1)+E(r+1,j)+Σpi（这里指的是从i到j的概率和）

选择i<r<j的最小值。

下面来解释一下这个式子：

我们在计算原树时E(T)=(3p1+2p2)+p3+(2p5+3p4+3p6)：()表示的是左右子树的计算。

计算左子树时E(T)=?p2+2p1? ? ? ? 右子树E(T)=2p4+p5+2p6

我们发现当左右子树合成新树时，计算E(T)时它们的节点的搜索概率都加了1。这是因为多了一层，再加上根节点的搜索概率1*p3，这些多出来的值加起来就是所有节点的搜索概率之和。

4.判断能否用动态规划解决问题

1.优化子结构

当E(1,n)达到最小值时，如果左右子树没达到最小值，那么E(1,n)就不可能是最小值。

2.子问题的重叠性

这里的右子树在另一种画法中也出现了，所以子问题具有重叠性。

?因此可以用动态规划解决问题。

5.找到最初值并画图

最初值即当子树只有一个节点的时候，E(i,i)=pi。当i<j时E(i,j)=0。

E(i,j)=E(i,r-1)+E(r+1,j)+Σpi

举个例子，要计算E(2,4)

E(2,4)=E(2,1)+E(3,4)+p2+p3+p4? ?r=2

E(2,4)=E(2,2)+E(4,4)+p2+p3+p4? ?r=3

E(2,4)=E(2,3)+E(5,4)+p2+p3+p4? ? r=4

选出计算出的最小值填入E(2,4)

以此类推，直到找到E(1,4)的最小值。

6.求解

先找到E(1,4)的根节点是哪一个，再从两个左右子树中找到根节点，以此类推直到全找完即可画出代价最小的树。

7.附加题：动态规划规整算法

1.问题描述

给定两段时间序列，长度可能不等，找到一种最优的两个序列之间节A=(A1, …, An)和B=(B1, …, Bm)点的对齐匹配方式，使得对齐后两段时间序列所有对应点的距离之和最小，表示为DTW （A1,…,n, B1, …, m)。

对齐时，可以一对多，即一个序列中的一个节点可以跟另一个序列中的多个连续点相对应。

对齐时，需满足以下条件：

1）边界以及连续性：在进行对齐时，两段序列都必须从起点开始，直到终点结束，每个节点都必须参与对齐。

2）单调递增性：对齐虚线之间不能相交，即不能出现如下对齐：节点Ai和Bj对齐，As和Bk对齐，其中 i>s, 而 j<k。

你肯定没看懂，用一个例子来说明一下：

给定两段语音序列，如何识别两段语音的相似性？

我们用数字表示音调高低，例如某个单词发音的音调为1-3-2-4。现在有两个人说这个单词，一个人在前半部分拖长，其发音为1-1-3-3-2-4；另一个人在后半部分拖长，其发音为1-3-2-2-4-4。

在进行这两段语音对应时，可以一对一，也可以一对多。

?当一对一时：

距离之和 = |A(1)-B(1)| + |A(2)-B(2)| + |A(3)-B(3)| + |A(4)-B(4)| + |A(5)-B(5)| + |A(6)-B(6)| = |1-1| + |1-3| + |3-2| + |3-2| + |2-4| + |4-4| = 6

当一对多时：

距离之和 = |A(1)-B(1)| + |A(2)-B(1)| + |A(3)-B(2)| + |A(4)-B(2)| + |A(5)-B(3)| + |A(5)-B(4)| + |A(6)-B(5)| + |A(6)-B(6)| = |1-1| + |1-1| + |3-3| + |3-3| + |2-2| + |2-2| + |4-4| + |4-4| = 0

我们要求解的问题就是如何进行对应使得距离差之和是最小的。

套路是一样的：

1.根据问题建立问题数组

要求的是距离差之和是最小的，不妨设D()表示距离差，然后是参数的问题，由于有A,B两个数列，都得照顾到，所以使D(i,j)表示A的前i个节点和B的前j个节点对齐之后产生的最小距离差的和。

我们要求的就是D(n,m)的值。

2.根据最后一步寻找原问题与子问题的关系

求D(n,m)的最后一步一定是A和B的最后节点如何对齐的问题。

因此我们根据D(n,m)中i对齐的节点进行讨论，显然An一定要对齐Bm，因为所有节点都需要进行对齐。

当An对齐的是Bm-1时，D(n,m)=d(n,m)+D(n,m-1)

当An-1对齐的是Bm时，D(n,m)=d(n,m)+D(n-1,m)

当An-1对齐的是Bm-1时，D(n,m)=d(n,m)+D(n-1,m-1)

其中d()表示的是两点之间的距离。

推广到i与j：

当Ai对齐的是Bj时，D(i,j)=d(i,j)+D(i,j-1)

当Ai-1对齐的是Bj时，D(i,j)=d(i,j)+D(i-1,j)

当Ai-1对齐的是Bj-1时，D(i,j)=d(i,j)+D(i-1,j-1)

3.判断是否是动态规划问题

1.判断优化子结构

当i,j固定时，d(i,j)也是一个定值，D(i,j)与它的子问题成线性关系，所以当D(i,j)最小的时候，它的子问题一定最小，所以具有优化子结构。

2.子问题的重叠性

显然，在求解D(i,j)时需要求解D(i-1,j-1)在求解D(i-1,j)时，也要求解D(i-1,j-1)所以具有子问题的重叠性。

4.找到初值并画图分析

当i=0或者j=0时为初值，结果都是0，画图的方法和求解LCS是一样的：

?这图。。。把初值忽略了，但不影响我们做题，知道初值是0就好。

5.求解

找到了D(3,4)的值，就需要进行回溯，即D(3,4)最后一步是如何进行对应的，知道将所有对应关系分析清楚。

6.伪代码实现

DTWDistance(A: array [1..n], B: array [1..m]) { 
	DTW?= array [0..n, 0..m] 
	for i? <-- 0 to n 
               for j? <-- 0 to m 
                  DTW[i, j]?= infinity //对数组进行初始化
	for i? <-- 1 to n 
	   for j? <-- 1 to m 
	       dist = d(A[i], B[j]) 
                  D(i, j)?= dist + minimum(D(i-1, j), D(i , j-1), D(i-1, j-1))//将三者中的最小值赋给D(i,j) 
	return D
}