经典算法-递归-最长公共子序列_递归算法 输出最长公共子序列

设x(i), y(i), z(i)表示单个字符，则X={x(1)x(2)……x(m)}，Y={y(1)y(2)……y(n)}，Z={z(1)z(2)……z(k)},我们称其为字符序列，其中m,n和k分别是字符序列X，Y，Z的长度，括号()中的数字被称作字符序列的下标。

如果存在一个严格递增而且长度大于0的下标序列{i1,i2……ik}，使得对所有的j=1,2,……k，有x(ij)=z(j)，那么我们称Z是X的字符子序列。而且，如果Z既是X的字符子序列又是Y的字符子序列，那么我们称Z为X和Y的公共字符序列。

在我们今天的问题中，我们希望计算两个给定字符序列X和Y的最大长度的公共字符序列，这里我们只要求输出这个最大长度公共子序列对应的长度值。

举例来说，字符序列X=abcd，Y=acde，那么它们的最大长度为3，相应的公共字符序列为acd。

输入格式

输入一行，用空格隔开的两个字符串

输出格式

输出这两个字符序列对应的最大长度公共字符序列的长度值

测试数据：a

import java.util.*;
public class Main {
 static Scanner sc = new Scanner(System.in);
 static char[] z1 = sc.next().toCharArray();
 static char[] z2 = sc.next().toCharArray();
 public static void main(String[] args) {
 	system.out.println(di(0,0));//递归
 }
 private static int d(int i,int j){
  if(i>=z1.length||j>=z2.length)
   return 0;//越界返回
  else if(z1[i]==z2[j])
   return d(i+1,j+1)+1;//若字符相同坐标加一向下寻找
  else
   return Math.max(d(i+1,j),d(i,j+1));//向下递归遍历每个字符寻找相同字符
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

非原创，参考本论坛一位大佬的代码，原文链接丢失，我只想说，这世间不乏天才的存在呀。