题目描述:输入两个字符串s
和t
,求它们的最长公共子序列(不连续)。
样例输入:
BDCABA
ABCBDAB
样例输出:
4
解释:s和t的最长公共子序列为BDAB、BCAB、BCBA,长度为4
方法:
定义
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示
s
1
,
s
2
,
s
3
,
.
.
.
.
,
s
i
s_{1},s_{2},s_{3},....,s_{i}
s1,s2,s3,....,si与
t
1
,
t
2
,
t
3
,
.
.
.
.
,
t
j
t_{1},t_{2},t_{3},....,t_{j}
t1,t2,t3,....,tj的最长公共子序列;
那么
d
p
[
i
+
1
]
[
j
+
1
]
=
{
d
p
[
i
]
[
j
]
+
1
,如果
s
i
+
1
=
t
j
+
1
m
a
x
(
d
p
[
i
]
[
j
+
1
]
,
d
p
[
i
+
1
]
[
j
]
)
,如果
s
i
+
1
≠
t
j
+
1
dp[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;i<s.length();i++) {
for(int j=0;j<t.length();j++) {
if(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()]);
}
}
}