最长公共子序列问题 java

最长公共子序列（Longest Common Subsequence，LCS）问题是指：给定两个字符串S1和S2，求它们的最长公共子序列。

子序列是指在原序列中不改变字符的相对顺序的情况下删除任意个字符（也可以不删），得到的新序列。

例如，字符串S1 = "ABCD"和字符串S2 = "BDAC"的最长公共子序列为"BD"。

在Java中，最长公共子序列问题可以通过动态规划算法来解决。具体来说，可以使用一个二维数组dp[i][j]来记录S1的前i个字符与S2的前j个字符的最长公共子序列长度。

状态转移方程为：

如果S1[i] == S2[j]，则dp[i][j] = dp[i-1][j-1] + 1；
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最终，dp[S1.length()][S2.length()]就是S1和S2的最长公共子序列长度。