leetcode
leetcode 1051 ~ 1100
最长公共子序列

最长公共子序列

难度:

标签:

题目描述

代码结果

运行时间: 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?
在定义dp(i, j)时使用索引-1作为边界条件是为了处理字符串为空的情况。这意味着当i或j为-1时,表示text1或text2中的一个字符串已经没有字符可比较,因此最长公共子序列长度为0。这种设置允许我们从索引0开始迭代,同时简化代码,因为索引从-1开始自然地处理了空字符串的情况,而不需要额外的初始化步骤。
🦆
在递归函数中,当text1[i]与text2[j]不匹配时,为什么选择比较dp(i-1, j)与dp(i, j-1),这两者的逻辑差别是什么?
当text1[i]与text2[j]不匹配时,我们需要找到不包含这两个不匹配字符中至少一个的最长公共子序列。dp(i-1, j)表示不考虑text1中的第i个字符(即text1[i])时,text1和text2的最长公共子序列的长度;dp(i, j-1)则表示不考虑text2中的第j个字符(即text2[j])时的最长公共子序列长度。比较这两者的最大值,我们可以得到在当前字符不匹配情况下,可能的最长公共子序列的长度。
🦆
你是如何确保使用字典memo作为存储时,每个状态dp(i, j)都只被计算一次,这种方法与传统动态规划表有何不同?
使用字典memo作为存储的关键在于我们在计算dp(i, j)之前先检查它是否已经被计算并存储。如果已经存在于字典中,我们直接返回存储的结果,避免重复计算。这种方法比传统的动态规划表更为灵活,因为它只计算需要的dp值,而不是填充整个表格。特别是当一些dp值根本不需要被计算时,这种方法可以节省大量的空间和计算资源。
🦆
在实际应用中,这种递归加记忆化的方法与非递归的动态规划方法相比,哪一个更为高效或者易于实现?
递归加记忆化的方法和非递归的动态规划方法各有优缺点。递归加记忆化通常更易于实现,代码更为直观和简洁,特别是在处理复杂问题时。然而,递归可能导致较深的调用栈,对于非常大的输入,可能会导致栈溢出。非递归的动态规划方法通常更稳定高效,因为它避免了递归调用的开销,并且可以更容易地进行空间优化,比如使用滚动数组。因此,选择哪种方法取决于具体问题的需求和环境限制。

相关问题