最长公共子序列
难度:
标签:
题目描述
代码结果
运行时间: 1016 ms, 内存: 138.1 MB
// Longest Common Subsequence using Dynamic Programming with Java Streams
// This solution utilizes the same DP approach as above, but with a more functional style using streams.
// The 2D array is initialized and updated similarly to the above method.
import java.util.stream.IntStream;
public class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
IntStream.range(1, m + 1).forEach(i -> {
IntStream.range(1, n + 1).forEach(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];
}
}
解释
方法:
这个题解采用了动态规划的方法。定义dp(i, j)为text1[0:i]和text2[0:j]的最长公共子序列的长度。如果text1[i]和text2[j]相同,说明这两个字符可以成为当前的最长公共子序列的一部分,因此dp(i, j) = dp(i-1, j-1) + 1;如果不同,则最长公共子序列要么在text1[0:i-1]和text2[0:j]中,要么在text1[0:i]和text2[0:j-1]中,因此dp(i, j) = max(dp(i-1, j), dp(i, j-1))。为了避免重复计算,使用memoization技术(通过字典memo存储已计算的结果)。
时间复杂度:
O(m * n)
空间复杂度:
O(m * n)
代码细节讲解
🦆
为什么在定义dp(i, j)时选择使用索引-1作为边界条件,这是否意味着dp数组是从索引0开始而不是1?
▷🦆
在递归函数中,当text1[i]与text2[j]不匹配时,为什么选择比较dp(i-1, j)与dp(i, j-1),这两者的逻辑差别是什么?
▷🦆
你是如何确保使用字典memo作为存储时,每个状态dp(i, j)都只被计算一次,这种方法与传统动态规划表有何不同?
▷🦆
在实际应用中,这种递归加记忆化的方法与非递归的动态规划方法相比,哪一个更为高效或者易于实现?
▷