用java 写一段最长公共子序列的动态规划代码

### 回答1：

public class LCS {
public static int lcs(char[] X, char[] Y, int m, int n)
{
int L[][] = new int[m+1][n+1];

for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}

public static void main(String[] args)
{
String s1 = "AGGTAB";
String s2 = "GXTXAYB";

char[] X=s1.toCharArray();
char[] Y=s2.toCharArray();
int m = X.length;
int n = Y.length;

System.out.println("最长公共子序列的长度：" + lcs(X, Y, m, n));
}
}

### 回答2：
最长公共子序列(LCS)问题是一个经典的动态规划问题，涉及找出两个序列中最长的公共子序列的长度。

下面是用Java实现LCS的动态规划代码：

public class LCS {
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        int[][] dp = new int[m+1][n+1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i-1) == text2.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]);
                }
            }
        }
        
        return dp[m][n];
    }
    
    public static void main(String[] args) {
        String text1 = "ABCD";
        String text2 = "ACDF";
        int result = longestCommonSubsequence(text1, text2);
        
        System.out.println("最长公共子序列的长度为：" + result);
    }
}

在这段代码中，我们使用一个二维数组`dp`来记录两个序列中最长公共子序列的长度。首先，我们需要初始化一个`dp`数组，大小为`m+1`行`n+1`列，其中`m`和`n`分别是两个序列的长度。

我们使用两个循环来填充`dp`数组。当`text1.charAt(i-1) == text2.charAt(j-1)`时，表示当前字符相等，那么最长公共子序列的长度增加1，即`dp[i][j] = dp[i-1][j-1] + 1`。否则，我们需要从上方或左方选择一个较大的长度，即`dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])`。

最后，返回`dp[m][n]`，即两个序列的最长公共子序列的长度。

假设我们的输入是"ABCD"和"ACDF"，那么输出将是2，因为它们最长公共子序列是"AD"。

### 回答3：
最长公共子序列是指在两个字符串中找到的最长的公共部分序列。
以下是使用动态规划算法用Java编写的代码：

public class LongestCommonSubsequence {
    public static int findLCS(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.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]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String str1 = "ABCDGH";
        String str2 = "AEDFHR";

        int lcsLength = findLCS(str1, str2);

        System.out.println("最长公共子序列的长度为：" + lcsLength);
    }
}

这个代码片段使用了一个二维数组dp[m + 1][n + 1]来记录str1和str2的子序列的长度。首先初始化dp数组大小，然后通过两个嵌套的for循环来计算长度。

如果当前字符相同，那么公共子序列的长度加1，并且向左上角的对角线移动一步；如果当前字符不同，那么最长公共子序列的长度等于左边或上边的最长公共子序列的长度的较大值。

最后，返回dp[m][n]即为最长公共子序列的长度。

在代码中，我们使用字符串"ABCDGH"和"AEDFHR"作为示例输入，输出为最长公共子序列长度为3。