以下是最长公共子序列的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。两个字符串都转换为数组,并且它们的长度存储在单独的变量中。在这些值上调用该函数。
这是一种动态编程技术,其中,一个值被计算并存储在数组中,而无需像递归那样一次又一次地计算它。每当需要先前计算的元素时,都会从数组中获取它。