动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
特点
分析是从大到小，写代码是从小到大计算过程中会把结果都记录下，最终结果在记录中找到。
最长公共子序列(Longest Common Subsequence,lcs)
最长公共子序列先明白子序列的概念,
子序列：一个序列A任意删除若干个字符得到新序列B，则A叫做B的子序列.那么最长公共的子序列呢
最长公共子序列：指两个序列中公共子序列长度最长的称为最长公共子序列：
例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。
那么如何用代码如何实现这个算法呢， 解决的办法有两种 1，穷举法2，动态规划
1.穷举法 主要是把两个序列每个元素一一进行比较， 这里不做解释，
2、动态规划： 用动态规划解决 LCS算法，
LCS的符号表示：
字符串X,长度m,从1开始计数
字符串Y,长度n,从1开始计数
Xi=<x1,x2,...,xi>表示X序列的前i个字符(1<=i<=m)
Yj=<y1,y2,...,yj>表示Y序列的前j个字符(1<=j<=n)
LCS(X,Y)为字符串X和Y的最长公共子序列,其中的一个 解为Z=<z1,z2,....zk>
上面的x,y子序列，有两种情况， 1、Xn!=Ym 2、Xn=Ym
如图：
上图中两个序列，从最后位开始比较， 拿出X的A与Y的B比较是否相同，得出两种结果
1、Xm！=Yn
Xm和Yn（m表示X序列的元素， n表示Y序列元素）序列中 ， m位上的元素与n位上元素不相同，则杨浦两种情况： 如图
2、Xm=Yn
Xm和Yn（m表示X序列的元素， n表示Y序列元素）序列中 ， m位上的元素与n位上元素相同则：
通过上面的方式从后往前推知道有一个没有元素时， 就找出最长公共子序列了。
那么公共子序列的数学方程式为：
上面的方式在代码编程解决的思路， 其实就是做一个表， 表里存放两个序列比较规则的变化数字，
如图
上图的表是存放X和Y序列的变化规则， 以Xm与Yn相同者加1,不同者取上或左中最大值。通过上图表中推出最长子序列， 假如从表中4开始往上推，那么得到是BCAB和BDAB， 就是X和Y的最长公共子序列
如图：
代码如下：
public static void getLCS(String x,String y){
char[] s1=x.toCharArray();
char[] s2=y.toCharArray();
int[][] array=new int[x.length()+1][y.length()+1];
//先把第一行和第一列填上零
for (int i = 0; i < array[0].length; i++) {
array[0][i]=0;
}
for (int i = 0; i < array.length; i++) {
array[i][0]=0;
}
//使用动态规划的方式填入数据
for (int i = 1; i < array.length; i++) {
for (int j = 1; j < array[i].length; j++) {
if(s1[i-1]==s2[j-1]){//如果相等，左上角加1填入
array[i][j]=array[i-1][j-1]+1;
}else{
array[i][j]=max(array[i-1][j],array[i][j-1]);
}
}
}
//打印
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j]+" ");
}
System.out.println();
}
//从后往前找到结果
Stack result=new Stack();
int i=x.length()-1;
int j=y.length()-1;
while((i>=0) && (j>=0)){
if(s1[i]==s2[j]){
result.push(s1[i]);
i--;
j--;
}else{//注意数组和String中的位置有一位差
if(array[i+1][j+1-1]>array[i+1-1][j+1]){
j--;
}else{
i--;
}
}
}
System.out.println("-----");
while(!result.isEmpty()){
System.out.println(result.pop()+" ");
}
}
网友评论