一. 问题描述
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。如果给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。现给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，要求使用动态规划算法思想，找出X和Y的最长公共子序列。
二. 审题
给两个字符串str1和str2，返回这两个字符串的最长公共子序列。就是找出两个字符串中相等的字符。例如：如图中字符串ABCDE和字符串ACE的最长公共子序列为ACE，长度为3。
三. 问题建模
可以根据str1[i]和str2[j]的情况，将最长公共子序列问题分为两种情况解决：
①若strl[i] == str2[j] ，也就是说两个字符串的最后一位相等，那么问题就转化成了字符串str1的[1,j-1]区间和字符串str2的[1,j-1]区间的最长公共子序列长度再加上1，即dp[i][j] = dp[i - 1][j - 1] + 1。（下标从1开始）。
②若str1[i] != str2[j]，也就是说两个字符串的最后一位不相等，那么字符串str1的[1,i]区间和字符串str2的[1,j]区间的最长公共子序列长度无法延长，因此dp[i][j]就会继承dp[i-1][j]与dp[i][j-1]中的较大值，即dp[i][j] = max(f[i - 1][j],f[i][j - 1])。（下标从1开始）
根据上面的描述，可以得出目标函数：
最后通过逆序获取值相同的字符，并将结果逆置即可。
时间复杂度分析： O(nm)，其中 n 和 m 分别是字符串 str1 和 str2 的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中每个元素进行计算。
空间复杂度分析： O(nm)，其中 n 和 m 分别是字符串 str1 和 str2 的长度。创建了 m+1 行 n+1 列的二维数组 dp。
来源于：力扣
四. 代码实现
1. 求解最大子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| package ch01;
import java.util.Scanner;
public class dp {
public static String removespace(String a){
String a1="";
for (int i=0;i<a.length();i++)
if (a.charAt(i)!=32){
a1+=a.charAt(i);
}
return a1;
}
public static String reserve(String a){
String k="";
for (int i=a.length()-1;i>=0;i--){
k += a.charAt(i);
}
return k;
}
public static String llist(String a,String b){
String ned="";
int lena=a.length(),lenb=b.length();
int[][] dp=new int[lena+1][lenb+1];
for (int i=0;i<=lena;i++){
for (int j=0;j<=lenb;j++){
dp[i][j]=0;
}
}
for (int i=1;i<=lena;i++){
for (int j=1;j<=lenb;j++){
if (a.charAt(i-1)==b.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]= Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int temp=dp[lena][lenb];
for (int i=lena;i>=1;i--){
for (int j=lenb;j>=1;j--){
if (dp[i][j]==temp && a.charAt(i-1)==b.charAt(j-1)){
ned+=b.charAt(j-1);
temp--;
}
}
}
return reserve(ned);
}
public static void main(String[] args) {
String str1,str2;
Scanner scanner = new Scanner(System.in);
str1=scanner.nextLine();
str2=scanner.nextLine();
String lon=llist(removespace(str1),removespace(str2));
System.out.print("[");
for (int i=0;i<lon.length();i++){
if (i!=lon.length()-1)
System.out.print("'"+lon.charAt(i)+"',"+" ");
else
System.out.print("'"+lon.charAt(i)+"'");
}
System.out.print("]");
}
}
|
运行结果：
2. 求解最大子序列个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| package ch01;
public class Lo {
public static void main(String[] args) {
String a = "ABCDFR";
String b = "ll";
int h = longestCommonSubsequence(a, b);
System.out.println(h);
}
public static int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
char c1 = text1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = text2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
|
运行结果：
