动态规划总结
经典问题介绍
装配线调度问题（Assembly-Line Scheduling）
矩阵链乘法问题（Matrix-Chain Multiplication）
钢条切割问题（Rod Cutting）
最长公共子序列问题（Longest Common Subsequence）
动态规划思想及其步骤
思想
1.Works bottom-up rather then top-down.
2.Useful for optimization problems.
3.A design technique, like divide-and-conquer.
动态规划（dynamic programming）是通过组合子问题的解而解决整个问题的。
步骤
Characterize the structure of the optimal solution.
刻画一个最优解的结构特征
Recursively define the value of the optimal solution.
递归地定义最优值的解
Compute the value of the solution in a bottom-up fashion.
计算最优值的解，通常采用自底向上的方法
Construct the optimal solution using the computed information.
利用计算出的信息构造一个最优解
总结
（1）描述最优解的结构。
（2）递归定义最优解的值。
（3）按自底向上的方式计算最优解的值。
（4）由计算出的结果构造一个最优解。
Rod Cutting
给定一段长度为n英寸的钢条和一个价格表pi求钢条的切割方案，使得销售收益最大。
递推式子：
长度为i钢条的价值 = max（一个长度为i的最大价值+长度 n-i 的最大价值）
rn = max（ pi + r（n-i） ）
递归法：自顶向下
//int cutRobMe(int p[], int n) {
// if (n == 0) {
// return 0;
// }
// int maxPrice = 0;
// for (int i = 1; i <= n; i++) {
// //相当于遍历一遍所有情况寻找最大价值。
// maxPrice = max(maxPrice, p[i] + cutRobMe(p, n - i));
// }
// return maxPrice;
//}dp法
//int cut_rod(int v[], int n)//对长度为n的钢条切割，能获得的最大价值
//{
// int r[100] = {0};
// int s[100] = {0};
// r[0] = 0;
// for (int i = 1; i <= n; i++)//从最小子问题开始
// {
// int q = 0;
// for (int j = 1; j <= i; j++) {
// if (q < v[j] + r[i - j]) {
// q = v[j] + r[i - j];
// s[i] = j; //在求解问题规模为i的子问题时将第一段的最优切割长度j保存在s[i]中
// }
// }
// r[i] = q; //自底向上求解每个子问题，从长度为1的问题开始 ,并记录子问题的解
// }
// return r[n];
//}matrix-chain multiplication
O（n2）个子问题 每个最多有n-1选择
算法复杂度O(n3)
步骤
第一步
Characterize the structure of an optimal solution
数学定义：Ai..jAi..j : 矩阵乘—–AiAi+1··AjAiAi+1··Aj
存在k 使得i≤k<ji≤k<j
把Ai··jAi··j 划分为 Ai··kAi··k 和A(k+1)··jA(k+1)··j
假设此时的k正好为最优划分，使得Ai··jAi··j矩阵相乘的规模最小
反证： 如果此时k对原来矩阵序列的划分不是最优的，则肯定存在另一个k，使得划分为最优：与假设矛盾。
第二步
Recursively define the value of an optimal solution
现在我们定义递归求解这个子问题：Ai··jAi··j 为： 矩阵AiAi+1··AjAiAi+1··Aj (1≤i≤j≤n)(1≤i≤j≤n)
数学定义：M[i,j]M[i,j] = Ai··jAi··j 的最小矩阵乘规模
定义数组P，使得矩阵AiAi的纬度为 = p[i−1]∗p[i]p[i−1]∗p[i]。p[i−1]p[i−1]代表矩阵的行， p[i]代表矩阵的列)
最优子结构定义如下
C语言实现
//
// Created by 安炳旭 on 2019-05-26.
//
#include <cstdio>
#include <vector>
#define MAX 100000 //定义最大值
#define SIZE 100 //SIZE为最多支持矩阵乘法的数量 + 1
int m[SIZE][SIZE], s[SIZE][SIZE];//用于存储中间过程的数组m 以及用于存储分割点的数组s
//初始化
void init(int n) {
for (int i = 1; i <= n; ++i) {
m[i][i] = 0;
}
}
//函数功能 计算一个矩阵链乘乘法的最小乘法次数并返回 以及把最优的分割方法存储在m数组中
int matrixChainMult(int array[], int numbersOfMatrix) {
//array待进行矩阵链乘的数组(数组下标从1开始) numbersOfMatrix代表矩阵元素的个数
//第一层循环 ：区间长度
for (int partLength = 1; partLength <= numbersOfMatrix - 1; ++partLength) {
//第二层 ：区间起点
for (int partStart = 1; partStart <= numbersOfMatrix - partLength; ++partStart) {
//第三层： 区间的终点 = 起点+长度
int partEnd = partStart + partLength;
m[partStart][partEnd] = MAX;
for (int k = partStart; k <= partEnd; ++k) {
//k为区间划分点
int temp = m[partStart][k] + m[k + 1][partEnd] + array[partStart] * array[partEnd + 1] * array[k + 1];
if (temp < m[partStart][partEnd]) {
//更新m 和s
m[partStart][partEnd] = temp;
s[partStart][partEnd] = k;
}
}
}
}
return m[1][numbersOfMatrix];
}
//打印一个数组的最终分法
void printResult(int i, int j) {
//i j 代表左右边界
if (i == j) {
printf("\tA%d\t",i);
} else {
printf("(");
printResult(i, s[i][j]);
printResult(s[i][j] + 1, j);
printf(")");
}
}
int main() {
//p和n为待输入的内容
// int p[SIZE+1] = {0,3, 5, 2, 1, 10};
int p[SIZE+1] = {0,10, 3, 15, 12, 7,2};
int n = 5; //n为矩阵的个数 也就说==p实际长度-1
init(SIZE+1);
int h = matrixChainMult(p, n);
printResult(1,n);
printf("h:%d",h);
}LCS
递推式
手动绘画c【i，j】步骤
1.先写出两个字符串 上边和左边留出一行一列
2.把除了字母外的第一行第一列初始化为0
3.根据递推式从第一个字母 一行一行的算
4.从右下角开始走路线 斜着的箭头位置就是匹配的子序列，值代表长度。
Max Sum
递归法求解O(n^2)
简单
分治法O（n*lgn）
待完善
动态规划O(n)
//
// Created by 安炳旭 on 2019-05-29.
//
#include <cstdio>
int DPMaxSum(int n, int *a, int *besti, int *bestj) {
int sum = 0, b = 0, tempi, tempj;//tempi, tempj用于记录起点终点下标
//b是临时变量用于计算最大值，而sum存储最终结果
for (int i = 0; i < n; ++i) {
if (b > 0) {
b += a[i];
tempj = i;
} else {
b = a[i];
tempi = i;
tempj = i;
}
if (b > sum) {
sum = b;
*besti = tempi;
*bestj = tempj;
}
}
return sum;
}
int main() {
int i,j = 0;
int a[6] = {-2, 11, -4, 13, -5, -2};
int sum = DPMaxSum(6,a,&i,&j);
printf("i=%d j=%d sum=%d",i,j,sum);
return 0;
}01背包动态规划
0-1 knapsack problem can be solved in time O(n*w) using dynamic programming.
递归求解
//
// Created by 安炳旭 on 2019-05-30.
//
#include <cstdio>
#define max(x, y) ( x>y?x:y )
#define M 101 // 背包容量
#define N 6 //物品数量
int B[N][M] = {0};//用于存储1-n物品 剩余空间m的最大价值中间数组 N代表已经考虑过1-N， M代表剩余背包的容量
int w[N] = {0, 10, 20, 30, 40, 50}; //物品重量
int v[N] = {0, 20, 30, 65, 40, 60}; //物品价值
int knapSack(int i,int j){
//递归的出口
if(i == 0){
return 0;
}
if(w[i] > j){//装不下所以不装
return knapSack(i-1,j);
} else{//装的下 试试装上之后能不能更大
return max(knapSack(i-1,j),knapSack(i-1,j-w[i])+v[i]);
}
}
int main(){
int res = knapSack(5,100);
printf("%d",res);
}动态规划
//
// Created by 安炳旭 on 2019-05-23.
//
#include <cstdio>
#define max(x, y) ( x>y?x:y )
#define M 101 // 背包容量
#define N 6 //物品数量
int B[N][M] = {0};//用于存储1-n物品 剩余空间m的最大价值中间数组 N代表已经考虑过1-N， M代表剩余背包的容量
int w[N] = {0, 10, 20, 30, 40, 50}; //物品重量
int v[N] = {0, 20, 30, 65, 40, 60}; //物品价值
int Knapsack() {
for (int i = 1; i < N; ++i) {
//i代表第i个物品
for (int j = 1; j < M; ++j) {
//j代表当前背包的容量
if (w[i] > j) {//如果装不下
// 跟不考虑第i个物品一直
B[i][j] = B[i - 1][j];
} else {//如果装的下
//B[i][j]为装或不装中那个大的！
B[i][j] = max(B[i - 1][j - w[i]] + v[i], B[i - 1][j]);
}
}
}
return B[5][100];
}
int main() {
printf("%d", Knapsack());
return 0;
}
