算法第七章动态规划整理复习
ppt为其他班的ppt
自己总结
1.动态规划大概的思路，跟递归（分治）有点像，在递归的基础上进行改进。
（1）首先满足，原问题的最优解中包含了子问题的最优解（即满足最优子化原理）【一般所求的最优答案很直观，一般是最大最小最短最长等】。将原问题化为子问题求解。
（2）根据子问题的最优解的求法，写出递归表达式。
（3）在递归的基础上改进，因为单纯用递归，重复计算很多次子答案。所以改进，自底向上for循环求出答案。
分治、动态规划、贪心算法的区别
三者都是将问题划分为规模更小的子问题
1.分治：各个子问题是独立的，不依赖子问题的解，不依赖已经求出答案的解。
递归求出各个子问题的解后，自下而上合并子问题的解。
2.动态规划：每一步的最优解包含局部最优解，但不是一定包含上一步最优解，用动态规划。（这样不用重复的解公共子问题）
动态规划一般是在子问题中选择最优的解，再+局部子问题的解。（允许子问题包含公共的子问题）
自底向上求解（不一定从n开始循环，要从所求递归式入手，看是往上求还是往下求）（都是从递归式的最子开始qi）
3.贪心算法：每一步的最优解一定依赖于上一步的最优解。
一动态规划的基本模式
引言
1.比如fibonacci数列，正常递归算法，子问题的求解有大量的重复，时间复杂度为 O(1.68^n)
用动态规划时间复杂度为 O(n) ，空间复杂度为O（1）
2.求二项式系数 Cnk, 【动态规划求解，用帕斯卡三角形，自底向上，两个for循环】
for(i = 1; i <= n; i++) //状态转移方程
{
for(j = 1; j < i; j++)
{
bc[i][j] = bc[i-1][j-1]+bc[i-1][j];
}
}
return bc[n][m];
}
完整解决方法链接
https://blog.csdn.net/u011240016/article/details/53008760
3.求盒子放球的问题
（一）最长公共子序列问题【子序列不是连着的】
1.设字符串A=a1a2...an ， 字符串B=b1b2...bn 。 想找最长公共子序列， 用动态规划。
设 L（i, j）表示A=a1a1...ai 和 B=b1b2...bj的最长公共子序列。其中i为A的子序列最后一个序号，j同理。 此时用动态规划来看，求解一个问题，去寻求他的子问题的解。 【i, j 到时候用For循环来实现，从 0循环到 n,从0 循环到 m，即可找到最长子序列】
L（i, 0）=0； 如果B的最后一个***为0 ，相当于B没有序列，所以子序列为0.
L（0，j）=0；
if ai=bj L(i ,j )=L (i-1, j-1) +1 。 如果A和B的序列的最后一个元素相等，那么不看这个元素，长度加1，看去掉这个元素之后的两个元素。
if ai != bj L（i, j）=max{ L（i, j-1），L（i-1, j ）} 如果A和B序列的最后一个元素不相等，那么A和B分别去掉一个元素，看剩下子序列最长为多少。
实际上用一个（n+1）(m+1)的表（填写L【i，j】）来计算就可以了，表格中的值可以通过比较 ai ,bj是否相等 + 表格中已填好的其他值 来填写。
算法LCS中描述了这种方法：【初始化，L（i,0）和 L（0, j） 再i,j从0开始循环嵌套，从0到n /m 最后返回L[n,m】
并且得到下面的定理：
最长公共子序列问题的最优解能够在 O(n*m)时间和 O( min {m,n})空间内得到
【因为表格的大小为 n*m ,每个单元格的填写为 O（1）,所以时间复杂度，空间复杂度是上面那些】
表格的填写：
（1）表格规格为（n+1)(m+1)，n,m分别为两个子序列的长度。先把第一行第一列初始化为0，即L【i,0】=0;L【0,j】=0
（2）填充剩下的表格，按每一行填写，如果当前位置的两个字符相等，即直接找对角线上一个元素+1。如果不等，取对角线上面旁边两个的最大值填写
（3）填完表格后如何找最长的公共子序列？在填写表格时做上记号，相等的元素+1后得到的表格值，做标记，到时候方便寻找
举个例子
（二）矩阵链乘 【n个矩阵相乘，最少相乘总次数问题。】
矩阵因为有维数，所以相乘的顺序有点重要，决定了相乘的总次数。
基础知识
A矩阵*B矩阵 【A矩阵为a行b列】【B矩阵为b行c列】矩阵相乘必须第一个矩阵的列=第二个矩阵的行才行
相乘后的矩阵C为a行c列，C矩阵的每一个元素都是由A，B矩阵相乘b次得来，所以A矩阵*B矩阵一共有a*b*c次元素相乘。
假设 Mi矩阵为 行为i ,列为i+1的矩阵。Mi , j 为 Mi*（Mi+1）*（Mi+2）...Mj 的矩阵 【Mi 矩阵的列数 = Mi+1 矩阵的行数，即i+1】 将Mi*...Mj用一个索引K分割开。矩阵连乘的次数=Mi, k-1 的次数 + M k,j的次数 + Mi, k *M k ,j+1两大矩阵相乘的次数 。Mi的行数用ri表示。（ri可以自己设定值）
算法：
//先把对角线0填充上0
for i<-1 to n {填充对角线d0}
C[i,i]=0
end for
//for循环嵌套，第一个循环每一次都执行下一条对角线
第二个循环在一条对角线里按顺序计算C[【i,j】
for d<- 1 to n-1 {填充对角线d1到dn-1}
for i<-1 to n-d {填充对角线di的项目}
j<-i+d //每一条对角线上的i确定 j由此得来
comment:下列三行计算C【i,j】
C【i,j】<-无穷 //初始化C【i,j】的值
for k<- i+1 to j //索引K的值大于i小于K
C【i,j】=min{C【i,j】,C【i,k-1】+C【k,j】+r【i】*r【k】*r【j+1】} //随着K值的取值，每次都会得出一个C【i,j】，如果后来的k值计算出的C【i,j】比较小，则取代，不然还是原来的C【i,j】。用Min函数。
end for
end for
end for
return C【1,n】
时间复杂度：定理7.2 由N个矩阵组成的链相乘，所需要的数量乘法的最小次数可以在O（n^3）的时间 和O（n^2）的空间中找出。
矩阵的手工
最长公共子序列和矩阵的 手工见动态规划的习题pdf
（三）所有点对的最短路径问题 所有结点对之间的最短距离（一个单源结点到所有其他结点的最短路径问题）
手工：d0(i,j)=边的权值 为D0矩阵，其他矩阵都是按公式计算得来，包含最后一个结点的矩阵所列出来的就是最短路径。详情见书上。
算法
输入：n*n维矩阵 记录有向图的边权值。输出：矩阵D【i,j】
D <- l {将输入矩阵l复制到D}
for k<- 1 to n //从经历第一个结点开始计算最短路径
for i <- 1 to n
for j<- 1 to n //从i,到j开始计算到每个结点的最短路径
D【i,j】=min{D【i,j】,D【i,k】+D【k,j】}
end for
end for
end for
时间复杂度：O（n^3）空间复杂度：O（n^2）
（四）0-1背包问题
1.书包容量为C,有n个物品。求V【n,C】即表示从n个物品中取出装入体积为C的物品的最大价值
用i,j两个变量来求 V【i,j】从i个物品中取出来装入体积为J的书包里的最大价值。
V【i.j】的计算：动态规划，装不装i物品。
如果i物品的体积大于j，那不装，V【i,j】=V【i-1,j】
如果i物品的体积小于j，那考虑装不装，用min函数比较
算法：
for i <- 0 to n
V【i,0】<-0
end for
for j<- 0 to n
V【0，j】<- 0
end for //初始化V【i,0】 V【0.j】
for i<- 1 to n
for j<- 1 to n
V【i,j】=V【i-1,j】 //先不装，也计算了si>j的情况
if si<=j then V【i,j】=max{V【i,j】,V【i-1,j-si】+vi}
end for
end for
return V【n,c】
时间复杂度：O（nC）空间复杂度：O（C）