算法导论学习笔记（六）：动态规划
2017-04-17 本文已影响73人
yoshino
转载请注明原作者 @yoshino，强烈要求简书支持TOC目录和数学公式的输入！
更新不及时，有空慢慢写吧，原文是写在Bear上粘贴来简书的，可能格式有点乱。
具体的工程在我的github上。
动态规划（dynamic programming,DP），与分治策略相似，通过求解子问题来求解原问题，不同于分治策略的事DP的子问题是相互重叠的，DP通常是用来求解最优化问题，设计一个动态规划算法步骤：
- 刻画一个最优解的结构特征
- 递归地定义最优解的值
- 计算最优解的值，通常采用自底向上的方法
- 利用计算出的信息构造一个最优解
钢条切割
钢条切割问题描述
求解思路
对于一根程度为l的钢条，有两种不同的切割法：
- 不切割：此时的收益为rl=pl
- 切割成长度i和l-i两部分：此时收益用递归表示：rl=ri+l-i
最大收益可以写成：p=max(pl,ri+l-i,…,r1+l-1)
即取其中最大的
两种动态规划算法：
- 带备忘的自顶向下算法：按照自然递归的形式编写过程，过程中保留之前子问题的解，其中会检查是否已经保过此解，如果已经保存了就直接返回保存的值，从而节省了计算的时间。
public int memoizedCutRodAux(int price[], int r[], int l) {//带备忘的自顶向下法
if (r[l] > 0) {
return r[l];//r[l]用来存储当长度为l时的最优解,price用来存储题目给出的收益值
} else {
int profit = 0;
for (int i = 1; i <= l; i++) {
profit=Math.max(profit,price[i]+memoizedCutRodAux(price,r,l-i));
}
r[l]=profit;//保存最优解
return profit;
}
}
- 自底向上法：任何子问题的求解都依赖于更小子问题的求解，把子问题按照规模大小进行排序，按从大到小的顺序进行求解，这样求解时保证每个求解的问题的前提子问题都已经求解过了
public int bottomUpCutRod(int price[], int r[], int l) {
for (int i = 1; i <= l; i++) {
int profit = 0;
for (int j = 1; j <= i; j++) {
profit = Math.max(profit, price[j] + r[i - j]);
}
r[i] = profit;
}
return r[l];
}
最长公共子序列（longest-common-subsequence,LCS）
问题描述
给定两个公共子序列X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>，求X Y的长度最长的公共子序列，子序列不要求要连续，但是顺序要相同
问题分析
-
刻画LCS特征，定义前缀对：
前缀对
从定理15.1可以得出，两个序列的LCS包含两个序列的前缀的LCS。
- 得出一个递归解
从定理15.1可以知道：
- 若xm=yn，则求解Xm-1和Yn-1的LCS，将xm=yn至于后面即可
- 若xm不等于yn，则求解Xm-1和Yn的LCS和Xm和Yn-1的LCS，取其中较长的作为LCS
之所以能做这样的假设，是因为最优解必然出现在X和Y中。
LCS递归公式
- 计算LCS的长度
- 建立一个矩阵c[0...m,0...n]用来保存c[i,j]的值
- 建立一个表b[1...m,1...n]用来保存最优解，即b[i,j]保存c[i,j]的子问题最优解
- java代码实现
private int[][] LCSLength(String[] X, String[] Y) {
ArrayList<ArrayList> result = new ArrayList<ArrayList>();
int m = X.length;
int n = Y.length;
int[][] c = new int[m + 1][n + 1];
int[][] b = new int[m + 1][n + 1];
for (int i = 1; i < m; i++)
for (int j = 0; j < n + 1; j++) {
c[i][j] = 0;
}
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1]) {//为了照顾c的序号，所以所有的X,Y均-1了
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;//代表左上箭头
} else if (c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
b[i][j] = 2;//代表向上箭头
} else {
c[i][j] = c[i][j - 1];
b[i][j] = 3;//代表向左箭头
}
}
return b;
}
- 构造LCS
从第三步我们得到的b[i,j]，我们得到了构造LCS的方向，递归回溯打印LCS即可
private void printLCS(int[][] b, String[] X, int i, int j) {
if (i != 0 && j != 0) {
if (b[i][j] == 1) {
printLCS(b, X, i - 1, j - 1);
System.out.print(X[i-1]);
} else if (b[i][j] == 2) {
printLCS(b, X, i - 1, j);
} else {
printLCS(b, X, i, j - 1);
}
}
}
最优二叉搜索树
问题描述
给定一个n个不同关键字的已排序的序列K=<k1,k2,...,kn>(递增序列)，对于每个关键字ki,都有一个概率pi表示其搜索频率。当然有些搜索的值可能不在K中，所以我们给出n+1个伪关键字“d0,d1,…,dn”,其中d0表示所有小于k1的值，dn表示所有大于kn的值，对于每个di，也有相应的概率pi
