动态规划：【1】.矩阵乘法链，最小乘法次数。

一、问题描述给定一个矩阵序列<A1,A2,…,An>，计算乘积A1A2…An。

要求找出一个加全部括号的方式，使得标量乘法的次数最小。

对于任意两个矩阵AiAi+1相乘，其乘法次数为pi-1pi pi+1，不同的加全部括号，所需要的乘法次数可能相差很大。

假设现在有三个矩阵A1A2A3相乘，维数分别为：10×100，100×5，5×50。

1、如果我们采用如下方式加全部括号：(（A1A2）A3)则首先计算（A1A2），乘法次数为p0p1 p2，得到新矩阵的维数为p0×p2计算(（A1A2）A3)，乘法次数为p0p2 p3，总的计算次数为p0p1 p2+ p0p2 p3=10×100×5+10×5×50=75002、如果我们采用如下方式加全部括号：(A1（A2 A3）)则首先计算（A2 A3），乘法次数为p1 p2 p3，得到新矩阵的维数为p1×p3计算(A1（A2 A3）)，乘法次数为p0p1 p3，总的计算次数为p1 p2 p3+ p0p1 p3=100×5×50+10×100×50=75000第二种方式需要的次数是第二次的10倍！二、问题分析：由前面可知，一个序列如果只有一个矩阵，则只有一种方式加全部括号，如果有两个或两个以上的矩阵，则必然可以看做两个子序列的乘积，且这两个子序列也是加全部括号。

我们用cost(i,j)表示序列Ai…Aj在最优加全部括号时的标量乘积次数，则其中p(i-1)p(k) p(j)为子序列Ai…Ak与Ak+1…Aj相乘时的标量相乘次数。

顺序连城可以把最后一个单个的看成单独加括号。

三、问题求解每一对满足1≤i≤j≤n的i和j都对应原问题的一个子问题，子问题个数为动态规划（二）：矩阵链乘法，其中第一项表示i<j时的子问题个数，后一项表示i=j 时的子问题个数。

如果采用递归方法求解，则每个子问题都会被求解多次，可以保留中间结果。

另外我们也采用自底向上的动态规划方式求解。

首先定义一个二维矩阵value，value[i][j]存放子序列Ai…Aj在最优加全部括号时的标量乘积次数，我们只使用j>=i的部分，且value[i][i]=0。

动态规划的实现步骤如下：步骤一：令step=0；步骤二：对于所有i=0，…，n，计算并保存value[i][i+step]；步骤三：若step=n-1，则结束，否则step=step+1，返回步骤二。

矩阵维数A130×35A235×15A315×5A45×10A510×20A620×25//实现思想：1.令step不同，即（j-i）不同；2.从i到j选择不同的分割点k。

i =< k < j；求出极大值。

记录分割的位置。

三重循环，从底层开始；首先分析：step=1，得到组合(1,2)、(2,3)、（3,4）、（4,5）、（5,6）；step=2，得到组合(1,3)、(2,4)、（3,5）、（4,6）；而其中，step=2，要用到不同的k了。

（1,2）3或者1（2,3）；同理step=3，得到组合(1,4)、(2,5)、（3,6）；要用到不同的k了。

1（2,3,4）或者（1,2）（3，4）或者（1,2,3）4；这些都是step 为小的时候得到的。

最终得到的step=5，得到组合（1,6）。

才是我们需要的。

【2】.装配线调度问题。

现有两条装配线，Sij表示第i条上完成第j道工序的装配站。

汽车完成组装需要依次完成1~n工序。

请找出完成装配并离开装配线的最快路线。

符号说明：ei：汽车进入装配线i的时间，i=1,2xi：汽车离开装配线i的时间aij：在装配站Sij完成装配需要的时间tij：在装配站Sij完成后离开第i条装配线，进入另一条装配线需要的转移时间注意，如果完成工序后，下一个工序还在同一条装配线上，则不需要转移时间。

问题求解：用Fij表示在第i条装配线上完成第j道工序的最快时间，用F表示完成汽车装配并离开装配线的时间，如果知道F1n和F2n，则有：要求出F1n和F2n，需要知道F1n-1和F2n-1，则有故得到递推公式：2、动态规划如果我们不是从上到下求解，而是从下到上求解，求解结果在某个地方保存起来，则可以大大改善求解速度。

这里的动态min只有两个部分，只有一个存在递归的形式，而上面哪一个却又两个递归的部分。

// 同理递增也是一样的，动态规划，甚至更简单写，由于只是自身的记录。

而公共的则是两个。

原理都是动态规划的。

【3】.最长公共子序列问题和编辑距离问题。

longest common subsequence。

子序列是不要求连续相等的字符序列。

这个问题也是算法导论上提过的问题。

注意这个问题是Subsequence不是Substring。

substring的话就是子串，子串的要求的连续相等的字符序列，而subsequence不要求连续。

比如说ABCD和ABD。

他们的longest common subsequence就是ABD。

而Longest common substring就是AB。

这个问题和Edit Distance是同样的一类问题。

解决这类的问题都是从一个优化的子结构开始得到递推式，从而给出一个一般的全局优化结构的过程。

在这里，我们假定两个字符串分别是S1和S2。

他们的长度是m和n。

我们用M[i,j]来表示一个长度为i的S1和长度为j的S2的最优方案。

我们要找的就是当M[m,n]是的方案。

问题的关键就是要找到M[i,j]和之前的那些诸如M[1..i, 1..j]之间的关系。

// m*n；我们把问题分成两种情况来讨论：1. 如果S1[i] == S2[j]。

就是i,j对应位置上的字符相等。

那么可以得出M[i,j] = M[i-1,j-1]+1;为什么呢？可以想象的。

如果M[i-1,j-1]也是一个最后方案，在这个最优方案上我们同时增加一个字符。

而这两个字符又相等。

那么我们只需要在这个M[i-1,j-1]的最优方案上++就可以了。

2. 如果S1[i] != S2[j]。

那么就拿M[i-1,j]和M[i,j-1]来比较。

M[i,j]的值就是M[i-1,j]和M[i,j-1]中大的值。

这好比原来的字符串是S1[1...i-1]是ABC，S2[1...j-1]是ABE。

那S1[1..i]是ABCE，S2[1..j]是ABEC。

可以看出来这个时候M[i,j]不是由M[i-1,j-1]决定的，而是由ABCE和ABE或者ABC和ABEC来决定的，也就是M[i-1,j]和M[i,j-1]。

所以我们可以把这个问题的递归式写成：【4】.编辑距离。

问题抽象归类：（编辑距离问题）设A和B是2个字符串。

要用最少的字符操作将字符串A转换为字符串B。

这里所说的字符操作包括:(1)删除一个字符;(2)插入一个字符；(3)将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。

试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。

这个问题是动态规划中非常基础的一个问题，这个问题其实和另一个前面提到的问题很类似。

就是Edit Distance的问题。

编辑距离问题：Edit Distance问题又被成为Levenshtein distance问题。

这里的问题描述的就是两个字符串经过若干次修改（添加字符，删除字符，替换字符）变为两个完全相等字符串。

这里的distance就是指最少的修改次数。

其实这个也就是《编程之美》中的那个字符串相似度的问题。

相似的，我们还是定义一个M[i,j]的二维模型。

这时候一样还是分析M[i,j]的递归式。

这里的结果还是比较相近的。

如果S1[i] == S2[j]。

那么M[i,j]就等于M[i-1,j-1]，就是说在S1[i]==S2[j]的情况下M[i,j]不会发生变化，显然不需要做什么改动。

edit(i, j) = edit(i-1, j-1);如果S1[i] != S2[j]的时候，那么就是M[i-1,j-1],M[i-1,j]和M[i,j-1]来做比较，我们取最小的那个值+1就可以了。

这里的M[i-1,j-1],M[i-1,j]和M[i,j-1]对应了添加、删除、替换这些操作。

M[i-1,j-1]可以替换最后一个S1[i]和S[j]来完成，而M[i-1,j]可以通过添加S1[i]来完成匹配。

edit(i, j) = min{edit(i-1, j)+1, edit(i, j-1)+1, edit(i-1, j-1)+1}对应添加，删除和替换这三个操作。

【5】.最长递增子序列（longest increase subsequence）既然已经说到了最长公共子序列，就把这个递增子序列也说了。

同样的，这里subsequence表明了这样的子序列不要求是连续的。

比如说有子序列{1, 9, 3, 8, 11,4, 5, 6, 4, 19, 7, 1, 7 }这样一个字符串的的最长递增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。

其实这个问题和前面的最长公共子序列问题还是有一定的关联的。

假设我们的初始的序列S1。

那我们从小到大先排序一下。

得到了S1'。

这样我们再求S1和S1'的最长公共子序列就可以知道答案了：）是不是有点巧妙啊。

这个过程还是比较直观的。

但是这个不是这次要说的重点，这个问题有比较传统的做法的：我们定义L(j)是一个优化的子结构,也就是最长递增子序列.那么L(j)和L(1..j-1)的关系可以描述成：L(j) = max{1; L(i)+1, (Ai<Aj)}; 所有的i<j;也就是说L(j)等于之前所有的L(i)中最大的的L(i)加一.这样的L(i)需要满足的条件就是Ai<Aj.这个推断还是比较容易理解的.就是选择j之前所有的满足小于当前数组的最大值.这里说满足无后效性。

即是前一阶段按照一定的次序排列好之后，对于某个给定阶段的状态来说，它以前各阶段的状态无法直接影响它未来的决策，只能间接地通过当前状态来影响。

比如一次为例如果有1，-1,2，-3,4，-5,6，-7.当i=3时。

前面有两个递增序列为（1,2）和（-1,2），长度都为2，这里2前面是1还是-1对求后面的递增序列没有直接的影响。

无后效。

上式子的意思即是，如果对所有的Aj>Ai,那么第i个元素可以直接接在L(i)子序列之后构成一个更长的子序列。