动态规划合集：
1.矩阵链乘法
2.投资组合问题
3.完全背包问题
4.01背包问题
5.最长公共子序列
例题1——矩阵链乘法
动态规划算法设计要素：（《算法设计与分析 屈婉玲》）
- 划分子问题，用参数表达子问题的边界，将问题求解转变为多步判断的过程。
- 确定优化函数，以函数的极大（或极小）作为判断依据，确定是否满足优化原则
- 列出关于优化函数的递推方程（或不等式）和边界条件
- 考虑是否需要设置标记函数，以记录划分位置
- 自底向上计算，以备忘录方式存储中间结果
- 根据备忘录（和标记函数）追溯给出的最优解
描述
设 为矩阵序列，
为
阶矩阵，i = 1,2,3...n.试确定矩阵的乘法顺序，使得元素相乘的总次数最少。
输入：向量其中
输出：最小的乘法次数以及矩阵链乘法加括号的位置。
样例：
input: P=<30,35,15,5,10,20> n=5
output: 11875 3,1
输出的意义表示：以
形式相乘，乘法计算次数最低为11875次
分析
对于的矩阵链，其任一划分之后，会出现两个子问题
而我们需要计算的是两个子问题。对于每个子问题 都有矩阵链的前后两个边界，对于
来说前边界是1后边界是k。我们令m[i,j]来表示矩阵链
的最优解。那么假设在i到j的任意位置划分，得到
。那么
的最优解就依赖于两个子问题。这种依赖关系写成递推方程就是：
递归方式伪码
递归伪码
迭代方式伪码
迭代伪码
实现代码过程
import java.util.ArrayList;
public class MatrixMutilpy {
public static int p[] = {30,35,15,5,10,20};
// n 是数字的长度 而实际矩阵个数为 n-1
public static int n = p.length;
public static int m[][] = new int[n][n];
public static int s[][] = new int [n][n];
// 递归形式
// 递推方程为： m[i][j] = min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]} i<= k <j
public static int recurMatrixChain(int []p,int i,int j){
if(j == i) {
m[i][j] = 0;
s[i][j] = i;
return m[i][j];
}
for (int k = i; k < j; k++) {
int q = recurMatrixChain(p,i,k)+recurMatrixChain(p,k+1,j)
+ p[i-1]*p[k]*p[j];
if (q < m[i][j]){
m[i][j] = q;
s[i][j] = k;
}
}
return m[i][j];
}
// 迭代实现
public static int IteratorMatrixChain(int p[]){
// 提前都 m[][] = 0 相当于 处理了r=1 的情况
// r 取值 为 2 3 4 5 < n=6 r 表示矩阵链规模，r=2 表示 A1*A2 A2*A3 r=3 表示 A1*A2*A3
for (int r = 2; r < n;r++){
// 以 r=2 为例 n-r+1 = 6-2+1 = 5 i取值为 1 2 3 4
// 含义就是 第几个链 r=2时： i=1 表示 A1*A2 i=2 表示A2*A3
for (int i = 1; i < n-r+1 ; i++) {
int j = i+r-1;
// 先计算一个 填到 m[k][l] 上 之后填的时候 比较大小
// 比如 r=3 i=1时j=3 A1*A2*A3 下面先计算了 A1（A2*A3）
// m[i][i] = 0 可以省去不写
m[i][j] = m[i][i] + m[i+1][j] + p[i-1]*p[i]*p[j];
s[i][j] = i;
// 上边相等于计算了 k=i的情况 下面k 从i+1开始;
// 到j-1
for (int k = i+1; k < j; k++) {
int temp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(temp < m[i][j]){
m[i][j] = temp;
s[i][j] = k;
}
}
}
}
return m[1][n-1];
}
public static ArrayList<Integer> find(){
ArrayList<Integer> result = new ArrayList<>();
int i = 1;
int j = n-1;
while(true){
int t = s[i][j];
result.add(t);
j = t;
if(i == j) break;
}
return result;
}
public static void main(String[] args) {
MatrixMutilpy test = new MatrixMutilpy();
for (int k = 0; k < n; k++) {
for (int l = 0; l < n ; l++) {
m[k][l] = Integer.MAX_VALUE;
s[k][l] = 0;
}
}
int result = test.recurMatrixChain(p,1,p.length-1);
System.out.println(result);
for (int k = 0; k < n; k++) {
for (int l = 0; l < n ; l++) {
m[k][l] = 0;
s[k][l] = k;
}
}
MatrixMutilpy test1 = new MatrixMutilpy();
int result2 = test1.IteratorMatrixChain(p);
System.out.println(result2);
ArrayList<Integer> res = find();
System.out.println(res);
}
}
