动态规划
算法总体思想？
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而提高计算效率。
基本步骤（重要）
- 找出最优解的性质，并刻划其结构特征。
- 递归地定义最优值。
- 以自底向上的方式计算出最优值。
- 根据计算最优值时得到的信息，构造最优解。
矩阵连乘问题
有四个矩阵A，B，C，D，为了计算乘积ABCD，共有多少种不同的乘法顺序？
若阶数分别为：A: 50*10，B: 10*40，C: 40*30，D: 30*5。哪种乘法顺序效率最高？
答：5种。
| 序号 | 乘法顺序 | 乘法次数 |
|---|---|---|
| 1 | (((AB)C)D) | 87500 |
| 2 | ((AB)(CD)) | 36000 |
| 3 | ((A(BC))D) | 34500 |
| 4 | (A((BC)D)) | 16000 |
| 5 | (A(B(CD))) | 10500 |
矩阵连乘问题定义：
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
一、找出最优解的性质，并刻划其结构特征。
特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
若先不想动态规划，使用前面前面的分治法，可得递归定义式：
利用该递归定义式可以直接写出递归函数来计算m[i:j]
static int recuMatrixChain (int i, int j)
{
if (i == j) return 0;
int u = recuMatrixChain (i+1,j) + p[i-1]p[i]p[j];
for (int k = i+1; k < j; k++) {
int t = recuMatrixChain (i,k) + recuMatrixChain (k+1,j) + p[i-1]p[k]p[j];
if (t < u) {
u = t;
}
}
return u;
}
但是该算法的复杂度如何呢？
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次（子问题的重叠性质）。
二、递归地定义最优值。
设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]
当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n
当i<j时，有
可以递归定义m[i,j]：
和上面是一样的。
三、以自底向上的方式计算出最优值。
public static void matrixChain(int [] p, int [][] m )
{
int n=p.length-1;
for (int i = 1; i <= n; i++) m[i][i] = 0;
for (int r = 2; r <= n; r++){
for (int i = 1; i <= n - r+1; i++) {
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) {
m[i][j] = t;
}
}
}
}
}
四、根据计算最优值时得到的信息，构造最优解。
public static void matrixChain(int [] p, int [][] m )
{
int n=p.length-1;
for (int i = 1; i <= n; i++) m[i][i] = 0;
for (int r = 2; r <= n; r++){
for (int i = 1; i <= n - r+1; i++) {
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
动态规划算法的基本要素
一、最优子结构
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
二、重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
三、备忘录方法
备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
m<-0
private static int lookupChain(int i, int j)
{
if (m[i][j] > 0) return m[i][j];
if (i == j) return 0;
else{
int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
if (t < u) {
u = t;
s[i][j] = k;
}
m[i][j] = u;
return u;
}
}
最长单调递增子序列
设计一个O(n^2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
设序列为a[0:n-1]，记b[i]：以a[i]为结尾元素的最长递增子序列的长度。
则序列a的最长递增子序列长度为
如何求b[i]？
最长公共子序列
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则
1)若xm=yn，
则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。
2)若xm≠yn，
则Z是
Xm-1和Y的最长公共子序列，X和Yn-1的最长公共子序列，
中较长的序列。
子问题的递归结构
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：
计算最优值、最优解
凸多边形最优三角剖分
表示具有n条边的凸多边形:用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}。
若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。
多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。
给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。
最优子结构性质
事实上，若凸(n+1)边形的最优三角剖分T包含三角形，1≤k≤n-1，则T的权为3个部分权的和：三角形的权，子多边形和的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。
因为若有或的更小权的三角剖分将导致T不是最优三角剖分的矛盾。
多边形游戏问题
多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。
随后n-1步按以下方式操作：
(1)选择一条边E以及由E连接着的2个顶点V1和V2；
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题：对于给定的多边形，计算最高得分。
