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。两个字符串都转换为数组，并且它们的长度存储在单独的变量中。在这些值上调用该函数。

这是一种动态编程技术，其中，一个值被计算并存储在数组中，而无需像递归那样一次又一次地计算它。每当需要先前计算的元素时，都会从数组中获取它。