引言
所谓动态规划(Dynamic Programming)，是一种分阶段求解问题的数学思想。它不止应用于编程领域，也应用于管理学、经济学等其他行业，通俗的讲，它的思想就是"大事化小,小事化了"。为了对它有初步认识，我们先举一个入门的例子，来说明它的基本思想。
走台阶组合问题
有一座10级台阶的楼梯，从下往上走，一次只能向上走1或者2个台阶，问一共有多少走法?
穷举法明显效率低下,我们不妨先这样考虑:假设就差最后一步走完台阶，这时候会出现两种情况:
1>在第8台阶上跨两台阶走完;
2>在第9台阶上跨一台阶走完.
接下来我们暂且不考虑我们怎么走到第8、9台阶，我们只需要知道它们已经求解,分别有X、Y种走法,那么此时有迭代式:
F(10) = X+Y = F(8) + F(9)
同样的思路，如何走到第8、9台阶的组合也是由第6、7和7、8台阶而来:
F(8) = F(6)+F(7)
F(9) = F(7)+F(8)
依次递推，可以将规模为10的问题进行瘦身，瘦身到什么时候呢?
当到到F(1)和F(2)时,只需要一步就可以到达第1、2台阶，所以有:
F(1) = 1, F(2)=2
这就是迭代的边界条件。因此动态规划迭代公式和边界条件为:
F(1) = F(2) = 1;
F(n) = F(n-1) + F(n-1), n>2;
这里F(n-1)和F(n-1)为最优子结构，F(n) = F(n-1) + F(n-1)为状态转移方程,F(1) = F(2) = 1为求解边界，在非递归算法中它也是迭代起点。
我们发现这是斐波那契数列，哈哈，一个递归不就解决了吗?是的，问题 是可以求解，但是这样做，产生大量重复性计算，时间复杂度为为2的n次方，效率低下。如何解决效率问题呢?迭代公式反应了自顶向下的关系，而动态规划是从底向上迭代(如果需要的话，需要将中间计算结果保存在张表中)。最终的动态规划代码实现如下:
package com.qicode.algorithmlearning.dp;
import java.util.ArrayList;
/**
* Created by chenming on 2018/6/21
* 走台阶问题,有n个台阶，每一步只能走1或者2台阶，求解走法个数和走法
* 动态规划模型:
* F(n) = F(n-1) + F(n-2)
* F(1) = 1;
* F(2) = 2;
*/
public class StepCombination {
public static void stepCombination(int n) {
int result = 0;
//保存
ArrayList<String> preWays = new ArrayList<>();//F(n-1)的结果
ArrayList<String> prepreWays = new ArrayList<>();//F(n-2)的结果
ArrayList<String> resultWays = new ArrayList<>();//F(n)的结果
if (n == 1) {
result = 1;
resultWays.add("1");
return;
}
if (n == 2) {
result = 2;
resultWays.add("11");
resultWays.add("2");
return;
}
//开始迭代
int prepre = 1;
int pre = 2;
prepreWays.add("1");
preWays.add("2");
preWays.add("11");//到达第二台阶的所有结果
for (int i = 3; i <= n; i++) {
result = pre + prepre;
prepre = pre;
pre = result;
//处理结果prepreWays的所有元素+2，preWays的所有元素+1，俩集合并入resultWays
resultWays = new ArrayList<>();//new resultWays 存放新的结果
for (int m = 0; m < prepreWays.size(); m++) {
String s = prepreWays.get(m);
StringBuilder sb = new StringBuilder(s);
sb.append("2");
s = sb.toString();
resultWays.add(s);
}
for (int m = 0; m < preWays.size(); m++) {
String s = preWays.get(m);
StringBuilder sb = new StringBuilder(s);
sb.append("1");
s = sb.toString();
resultWays.add(s);
}
//下一次迭代
prepreWays = preWays;
preWays = resultWays;
}
System.out.println("台阶步数:"+result);
System.out.println("======台阶组合====");
for(int i = 0 ; i < resultWays.size();i++){
System.out.println(resultWays.get(i));
}
}
}
打印结果:
台阶步数:8
======台阶组合====
122
212
1112
221
1121
1211
2111
11111
到此为止，一个最最简单的动态规划问题求解完毕。下面我们再继续研究今天的主题:最长公共子序列和最长公共子串。其中后者的求解是在前者的基础之上，我们先看最长公共子序列问题
最长公共子序列
例:X="GHHABDCAB"和Y=“BDCAMBAE”,最长公共子序列为:BDCAB。注意最长公共子序列不连续。如果使用穷举法，一个长度为n的序列的组合为2的n次幂，事件复杂度为指数阶,这可是唯恐天下不乱的爆炸性时间复杂度。那么这个问题可不可以采用动态规划呢？
先分析它的最优子结构.假设,已经知道Z(k)={z1, z2, z3, ... zk}为X(m) = {x1,x2....xm}和Yn={y1,y2...yn}的最大公共子序列，有以下三种结论
1>,x[m]=y[n]=z[k]，那么去除掉他们的子序列Z(k-1)是X(m-1)和Y(n-1)的最长公共子序列;
2>x[m]!=y[n], x[m]!=z[k], y[n]=z[k]:我们可以把x[m]去掉，那么Z(k)是X(m-1)和Y(n)的最长公共子序列;
3>y[n]!=x(m),y[n]1=z[k],我们可以把y[n]去掉，那么Z(k)是X(m)和Y(n-1)的最长公共子序列.
依据以上结论，最长公共子序列的递推公式:
其中C[i][j]记录最长公共子序列的长,i和j分别为XY串中的索引.
然后，在寻找边界:当i=0或者j=0,表示X或者Y中一个子串为空,C[i][j]=0;
最后，制定数据结构和算法:
1>二维数组C[m][n]记录迭代结果,b[i][j]记录最长子串的生成方向，如C[i][j] = C[i-1][j-1]+1,则b[i][j]记录为左上方向，其他同理，运算完毕，可以根据b[][]记录的方向逆向得到最长子序列;
2>从i=0,j=0开始按照迭代公式填充C[i][j]和b[i][j],初始状态i-1,j-1越界，此时默认越界的元素为0.
3>迭代完毕，C[m-1][n-1]记录了最长公共序列的长度，b[i][j]记录了最长子串迭代的"方向",逆向遍历b[][]可得到一个最长公共子序列。
package com.qicode.algorithmlearning.dp;
import stack.Stack;
/**
* Created by chenming on 2018/6/19
* 动态规划-最长公共子序列
* 递推公式
* 1.C(i, j) = C(i-1, j-1)+1 x[i] = y[j]
* 2.C(i, j) = Max(C(i-1, j),C(i, j-1)) x[i] != y[j]
* 3.C(i, j) = 0 i=0或j=0
*/
public class LCS {
private char[] s1, s2;//俩序列
private int len1, len2;
private int[][] c;//动态规划运算记录表
private int[][] b;//记录子序列生成路径,b[i][j] = 1表示情况1，来源于左上，b[i][j]=2，来源于左,b[i][j]=3来源于上
private final int TYPE_LEFT_TOP = 1;//左上
private final int TYPE_LEFT = 2;//左
private final int TYPE_TOP = 3;//上
public LCS(String s1, String s2) {
this.s1 = s1.toCharArray();
this.s2 = s2.toCharArray();
len1 = s1.length();
len2 = s2.length();
c = new int[len1][len2];
b = new int[len1][len2];
}
/**
* 最长公共子序列迭代
*/
public void getLcs() {
int i, j;//行为s1,列为s2
//开始迭代
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
if (s1[i] == s2[j]) {
c[i][j] = itemWithBoundary(i - 1, j - 1) + 1;
b[i][j] = TYPE_LEFT_TOP;
} else {
int leftItem = itemWithBoundary(i, j - 1);
int topItem = itemWithBoundary(i - 1, j);
if (leftItem >= topItem) {
c[i][j] = leftItem;
b[i][j] = TYPE_LEFT;
} else {
c[i][j] = topItem;
b[i][j] = TYPE_TOP;
}
}
}
}
dumpMatrix();
dumpLcs1();
dumpAllLcs();
}
/**
* 超出边界返回0 否则返回c[i][j]
*/
private int itemWithBoundary(int i, int j) {
if (i < 0 || j < 0 || i >= len1 || j >= len2) {
return 0;
}
return c[i][j];
}
/**
* 借助b[][],输出Lcs
*/
private void dumpLcs() {
System.out.println("=======最小公共子序列=========");
int i = len1 - 1;
int j = len2 - 1;
Stack<Character> stack = new Stack<>();
while (i >= 0 && j >= 0) {
if (b[i][j] == TYPE_LEFT_TOP) {//方向左上
stack.push(s1[i]);
i--;
j--;
} else if (b[i][j] == TYPE_LEFT) {//方向向左
j--;
} else if (b[i][j] == TYPE_TOP) {//方向向上
i--;
}
}
//输出最长子序列
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
Character pop = stack.pop();
result.append(pop);
}
System.out.println(result.toString());
}
/**
* 打印迭代矩阵
*/
private void dumpMatrix() {
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
System.out.print(c[i][j] + ", ");
}
System.out.println("");
}
}
}
说明: dumpLcs方法是借助数组b,由于C[][]记录了最长子序列的变化，因此也可以得出它的方向。优化的代码如下:
/**
* 不借助辅助数组b[][]，c[][]中隐含了LCS信息
* 1.c[i][j] 字符相等，则输出
* 2.字符不相等，则判断c[i][j-1]和c[i-1][j]的大小，向较大者方向遍历
*/
private void dumpLcs1() {
System.out.println("=======最小公共子序列=========");
int i = len1 - 1;
int j = len2 - 1;
Stack<Character> stack = new Stack<>();
while (i >= 0 && j >= 0) {
if (s1[i] == s2[j]) {
stack.push(s1[i]);
i--;
j--;
} else {
int left = itemWithBoundary(i, j - 1);
int top = itemWithBoundary(i - 1, j);
if (left >= top) {
//向左遍历
j--;
} else {
i--;
}
}
}
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
Character pop = stack.pop();
result.append(pop);
}
System.out.println(result.toString());
}
最长公共子序列可能有多个，如下图
多个最长公共子序列.png
当X[i]!=Y[j]且C[i-1][j] == C[i][j-1]时，说明C[i][j]的生成有两个方向，此时分别从C[i-1][j]和C[i][j-1]递归逆向查找。
/**
* 打印所有
*/
public void dumpAllLcs() {
System.out.println("=====所有LCS=====");
StringBuilder sb = new StringBuilder();
int i = len1 - 1;
int j = len2 - 1;
dumpLcsRes(i, j, sb);
}
/**
* 递归打印
*
* @param sb
*/
private void dumpLcsRes(int i, int j, StringBuilder sb) {
sb = new StringBuilder().append(sb.toString());//新建stringbuilder，暂时存放当前结果
while (i >= 0 && j >= 0) {
if (s1[i] == s2[j]) {
sb.append(s1[i]);
i--;
j--;
} else {
int left = itemWithBoundary(i, j - 1);
int top = itemWithBoundary(i - 1, j);
if (left > top) {
//向左遍历
j--;
} else if (left < top) {//向上遍历
i--;
} else {//c[i-1][j] == c[i][j-1],递归从[i-1][j]和[i][j-1]开始
dumpLcsRes(i - 1, j, sb);
dumpLcsRes(i, j - 1, sb);
return;
}
}
}
System.out.println(sb.toString());
}
测试代码:
/**
* 测试最长公共子序列
*/
@Test
public void testLcs(){
LCS lcs = new LCS("BDCABA", "ABCBDAB");
lcs.getLcs();
// lcs.getLcss();
}
打印如下:
0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 2, 2, 2,
0, 1, 2, 2, 2, 2, 2,
1, 1, 2, 2, 2, 3, 3,
1, 2, 2, 3, 3, 3, 4,
1, 2, 2, 3, 3, 4, 4,
=======最小公共子序列=========
BCBA
=====所有LCS=====
BADB
BACB
ABCB
最长公共子串
最长公共子串和序列不同的是，它是连续的，所以当X[i]!=Y[j]时，需要从0开始重新扫描。其它思路和步骤和最长公共子串基本相同:
/**
* 在最长公共子序列的基础上，实现最长公共字串
* <p>
* 递推公式
* 1.C(i, j) = C(i-1, j-1)+1 x[i] = y[j]
* 2.C(i, j) = 0 x[i] != y[j]
* 3.C(i, j) = 0 i=0或j=0
*/
public void getLcss() {
//初始化第一行
int i, j;//行为s1,列为s2
int maxSubLen = 0;
int maxX = 0, maxY = 0;//记录最长子串的结束位置
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
if (s1[i] == s2[j]) {
c[i][j] = itemWithBoundary(i - 1, j - 1) + 1;
} else {
c[i][j] = 0;
}
if (maxSubLen < c[i][j]) {
maxSubLen = c[i][j];
maxX = i;
maxY = j;
}
}
}
//打印迭代记录表C[][]
dumpMatrix();
System.out.println("最长公共子序列结束位置(x, y):" + maxX + ":" + maxY);
dumpMaxLenSubString(maxX, maxY);
}
/**
* 打印最长公共子串
* 从[x,y]位置开始向左上遍历直到c[i][j]越界，或者c[i][j]==0
*
* @param x
* @param y
*/
private void dumpMaxLenSubString(int x, int y) {
Stack<Character> stack = new Stack<>();
int i = x;
int j = y;
while (i >= 0 && j >= 0 && c[i][j] > 0) {
stack.push(s1[i]);//直接向左上遍历
i--;
j--;
}
//输出最长子串
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
Character pop = stack.pop();
result.append(pop);
}
System.out.println("最长公共子串为:" + result.toString());
}
由于只有当X[i]=Y[j]时才继续迭代，所以打印最长字串只要从字串的结束位置，向左上遍历知道C[i][j]=0为止。打印结果为:
0, 1, 0, 1, 0, 0, 1,
0, 0, 0, 0, 2, 0, 0,
0, 0, 1, 0, 0, 0, 0,
1, 0, 0, 0, 0, 1, 0,
0, 2, 0, 1, 0, 0, 2,
1, 0, 0, 0, 0, 1, 0,
最长公共子序列结束位置(x, y):1:4
最长公共子串为:BD
最长公共子串也可能有多个，找到最大的字串结束位置，放入集合，然后遍历集合执行dumpMaxLenSubString即可，逻辑比较简单，代码略过。
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
网友评论