动态规划之查找最大公共子序列

动态规划

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
动态规划算法主要包括两种。备忘录法和自底向上法
最大公共子序列：公共子序列通俗的说就是两个序列中都有的子序列最大意味最长。举个例子有一个字符串ABCBDAB它的子序列可能为ABA，AB，AC等。再到两个字符串BDCABA这两个字符串的子序列有哪些呢，比如BCAB。这个子序列不唯一但最大的长度是可以确定的长度为4。
这里我们有两种方法求解最大公共子序列
1.枚举法
就是一个一个的找出字符串的公共子序列。这种方法最好想，但过程过于复杂代码复杂度高运行速度慢不建议使用
2.动态规划自底向上法
首先第一步：求出最大公共子序列的长度
第二步：用回溯法找到最大公共子系列
两个序列：
X[1…m] = {A, B, C, B, D, A, B}
Y[1…n] = {B, D, C, A, B, A}
实现第一步求长度主要思路为

如果xm = yn，则Ck = xm = yn 且 Ck-1是Xm-1和Yn-1的一个LCS
如果xm != yn 且 Ck != xm，则C是Xm-1和Y的一个LCS
如果xm != yn 且 Ck != yn，则C是X和Yn-1的一个LCS
这里ij表示两个序列的元素的索引如果两个索引对应的元素相等则为索引-1元素的长度+1
附上代码`

public class 自底向上法 {
	public static int max(int a,int b) {
		return a>b?a:b;
	}
	public static int lcs(char[]a,char[]b,int i,int j,int[][] bak) {
		for(int ii=0;ii<=i;ii++) {
			for(int jj=0;jj<=j;jj++) {
				if(ii==0||jj==0) bak[ii][jj]=0;
				else if(a[ii]==b[jj]){
					bak[ii][jj]=bak[ii-1][jj-1]+1;
				}else {
					bak[ii][jj]=max(bak[ii-1][jj],bak[ii][jj-1]);
				}
			}
		}
		return bak[i][j];
	}

	public static void main(String[] args) {
		String s1="ABCBDAB";
		char[] c1=new char[s1.length()+1]; //添加一个带0号字符的字符数组。0号字符是空字符。
		char[] t1=s1.toCharArray();
		c1[0]=(char)0;
		for(int i=0;i<t1.length;i++) {
			c1[i+1]=t1[i];
		}
		String s2="BDCABA";
		char[] c2=new char[s2.length()+1];
		char[] t2=s2.toCharArray();
		c2[0]=(char)0;
		for(int i=0;i<t2.length;i++) {
			c2[i+1]=t2[i];
		}
		int[] []bak=new int[c1.length][c2.length];
		System.out.println(lcs(c1, c2, c1.length-1, c2.length-1,bak));
	}

图片来源：https://blog.csdn.net/qq_43416226/article/details/90247519