Java程序的最长公共子序列
以下是最长公共子序列的Java程序-
示例
public class Demo{
int subseq(char[] a, char[] b, int a_len, int b_len){
int my_arr[][] = new int[a_len + 1][b_len + 1];
for (int i = 0; i <= a_len; i++){
for (int j = 0; j <= b_len; j++){
if (i == 0 || j == 0)
my_arr[i][j] = 0;
else if (a[i - 1] == b[j - 1])
my_arr[i][j] = my_arr[i - 1][j - 1] + 1;
else
my_arr[i][j] = max_val(my_arr[i - 1][j], my_arr[i][j - 1]);
}
}
return my_arr[a_len][b_len];
}
int max_val(int val_1, int val_2){
return (val_1 > val_2) ? val_1 : val_2;
}
public static void main(String[] args){
Demo my_inst = new Demo();
String my_str_1 = "MNSQR";
String my_str_2 = "PSQR";
char[] a = my_str_1.toCharArray();
char[] b = my_str_2.toCharArray();
int a_len = a.length;
int b_len = b.length;
System.out.println("最长公共子序列的长度为"+ " " + my_inst.subseq(a, b, a_len, b_len));
}
}输出结果
最长公共子序列的长度为 3
名为Demo的类包含一个名为“subseq”的函数，该函数返回给定字符串的最长公共子序列，即str_1[0到len(str_1-1)，str_2（0到len(str_2-1)//2'for'循环在两个字符串的长度上进行迭代，并且如果'i'和'j'均为0，则将数组的特定索引分配为0。否则，my_arr[第一个字符串的长度+1][第二个字符串的长度+1]。
main函数定义了Demo类的新实例，并定义了两个字符串my_str_1和my_str_2。两个字符串都转换为数组，并且它们的长度存储在单独的变量中。在这些值上调用该函数。
这是一种动态编程技术，其中，一个值被计算并存储在数组中，而无需像递归那样一次又一次地计算它。每当需要先前计算的元素时，都会从数组中获取它。