动态规划策略编程实现最长公共子序列问题代码

public class LongestCommonSubsequence {
   static int lcs(String s1, String s2) {
       int m = s1.length();
       int n = s2.length();
       int[][] dp = new int[m + 1][n + 1];
       int[][] path = new int[m + 1][n + 1];

       // 初始化dp数组的第一行和第一列为0
       for (int i = 0; i <= m; i++) {
           dp[i][0] = 0;
       }
       for (int j = 0; j <= n; j++) {
           dp[0][j] = 0;
       }

       // 使用动态规划计算lcs，并记录路径信息到path数组中
       for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
               if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
                   path[i][j] = 1; // 左上方转移
               } else {
                   if (dp[i - 1][j] >= dp[i][j - 1]) {
                       dp[i][j] = dp[i - 1][j];
                       path[i][j] = 2; // 上方转移
                   } else {
                       dp[i][j] = dp[i][j - 1];
                       path[i][j] = 3; // 左方转移
                   }
               }
           }
       }

       // 回溯得到最长公共子序列
       StringBuilder sb = new StringBuilder();
       int i = m, j = n;
       while (i > 0 && j > 0) {
           if (path[i][j] == 1) {
               sb.append(s1.charAt(i - 1));
               i--;
               j--;
           } else if (path[i][j] == 2) {
               i--;
           } else {
               j--;
           }
       }

       // 将sb中的字符反转得到最长公共子序列
       String lcs = sb.reverse().toString();
       System.out.println("最长公共子序列是： " + lcs);

       // 返回lcs的长度
       return dp[m][n];
   }

   public static void main(String[] args) {
       String s1 = "ABCDGHLQR";
       String s2 = "AEDPHR";
       System.out.println("最长公共子序列长度是： " + lcs(s1, s2));
   }
}