题目描述:输入两个字符串s
和t
,求它们的最长公共子序列(不连续)。
样例输入:
BDCABA
ABCBDAB
样例输出:
4
解释:s和t的最长公共子序列为BDAB、BCAB、BCBA,长度为4
方法:
定义dp[i][j]dp[i][j]dp[i][j]表示s1,s2,s3,....,sis_{1},s_{2},s_{3},....,s_{i}s1,s2,s3,....,si与t1,t2,t3,....,tjt_{1},t_{2},t_{3},....,t_{j}t1,t2,t3,....,tj的最长公共子序列;
那么
dp[i+1][j+1]={dp[i][j]+1,如果si+1=tj+1max(dp[i][j+1],dp[i+1][j]),如果si+1≠tj+1dp[i+1][j+1]=\begin{cases} dp[i][j]+1& \text{,如果$s_{i+1}=t_{j+1}$}\\ max(dp[i][j+1],dp[i+1][j])& \text{,如果$s_{i+1}≠t_{j+1}$} \end{cases}dp[i+1][j+1]={dp[i][j]+1max(dp[i][j+1],dp[i+1][j]),如果si+1=tj+1,如果si+1=tj+1
程序代码:
import java.util.Arrays;
import java.util.Scanner;public class LCS {public static void main(String[] args) {String s="",t="";Scanner sc = new Scanner(System.in);while(sc.hasNext()) {s=sc.next();t=sc.next();int[][] dp = new int[s.length()+1][t.length()+1];for(int i=0;ifor(int j=0;jif(s.charAt(i)==t.charAt(j)) {dp[i+1][j+1]=dp[i][j]+1;} else {dp[i+1][j+1]=Math.max(dp[i][j+1], dp[i+1][j]);}}}System.out.println(dp[s.length()][t.length()]);}}
}