最长公共子序列
样例输入:
2 asdf adfsd 123abc abc123abc
样例输出:
3 6
这道题是一道经典的动态规划:
首先推出这个题的动态方程:
我来解释一下上面这个方程:
设arr[i][j]表示 (a1,a2,a3,.....,ai) 与 (b1,b2,b3,...,bj)子串的最长子序列的长度。
1.当 i = 0, j = 0时,两个子串都为空,那么公共子序列当然就为空。
2.当i , j>0 而且 a1 = bj 时,假如说现在比较的是(a的前i个(a1,a2,a3,...,ai)和b的前j个(b1,b2,b3,...,bj))的最长公共子序列,如果a[i]和b[j]相等 那么一目了然,这个问题就可以变成(a的前i-1个(a1,a2,a3,...,ai-1)和b的前j-1个(b1,b2,b3,...,bj-1))的最长公共子序列 + 1。
3.当 i , j>0而且 ai!=bj 时,如果不符合上面那种情况(就是 a[i]!=b[j] )那么就不可能应用 arr[i][j]=arr[i-1][j-1]+1 递推公式, 因为你+1其实就加的是 最后a[i]=a[j]这一项来更新 最长公共子序列的长度值
然后就分为两种情况( arr[i-1][j] > arr[i][j-1] 或者 arr[i-1][j] < arr[i][j-1] ):
1>.最长公共序列可以在(a1,a2,....a(n-1))和 (b1,b2,...bn)中找。
2>.最长公共序列可以在(a1,a2,....an) 和 (b1,b2,...b(n-1))中找。
那么就将arr[i][j]的值赋值为arr[i-1][j]与arr[i][j-1]中的最大值即可。
最后取arr[a.length()][b.length()]对应的值即是答案。
代码如下:
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args){
- Scanner in = new Scanner(System.in);
- int time = 0;
- time = in.nextInt();
- String a = null;
- String b = null;
- while( time-- != 0){
- a=in.next();
- b=in.next();
- System.out.println(sub(a,b));
- }
- }
- public static int sub(String a,String b){
- int[][] arr = new int[a.length()+1][b.length()+1]; // 初始化递推数组
- //这个数组表示 a字符串前n位 与 b字符串前k位 的最长公共子序列长度 int[][] arr = new int[n][k];
- for(int i=0;i<a.length();i++){
- arr[i][0] = 0; //初始化递推数组 a数组的(0-i)子串和b数组的(0-0)子串 公共部分当然是0
- }
- for(int j=0;j<b.length();j++){
- arr[0][j] = 0; //初始化递推数组 b数组的(0-i)子串和a数组的(0-0)子串 公共部分当然也是0
- }
- //上面也就是第一种情况
- for(int i=1;i<=a.length();i++){
- for(int j=1;j<=b.length();j++){
- if(a.charAt(i-1)==b.charAt(j-1)){
- arr[i][j] = arr[i-1][j-1]+1; //对应第二种情况
- }
- else if(arr[i-1][j] > arr[i][j-1]){
- arr[i][j] = arr[i-1][j]; //对应第三种情况 这是递推式 一行一行算的 先第一行 所以 arr[i-1][j] 不会为空
- }
- else{
- arr[i][j] = arr[i][j-1]; //对应第三种情况 arr[i][j-1]也算过了 也不会为空
- }
- }
- }
- return arr[a.length()][b.length()];
- }
- }