动态规划最长公共序列 java
时间: 2023-08-05 14:59:53 浏览: 44
动态规划最长公共子序列(Longest Common Subsequence, LCS)的 Java 实现可以使用二维数组来解决。下面是一个示例代码:
```java
public class LongestCommonSubsequence {
public static int lcs(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = 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) {
dp[i][j] = 0;
} else 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 = "ABCD";
String str2 = "ACDF";
int result = lcs(str1, str2);
System.out.println("最长公共子序列的长度为: " + result);
}
}
```
上述代码中,我们使用了一个二维数组 `dp` 来保存每个子问题的最优解。通过两个嵌套的循环遍历字符串 `str1` 和 `str2` 的所有可能的子序列,根据动态规划的原理,逐步计算出最长公共子序列的长度。最后返回 `dp[m][n]`,即为最长公共子序列的长度。
在上述示例中,我们计算了字符串 "ABCD" 和 "ACDF" 的最长公共子序列的长度,输出结果为 3。