最长公共子序列力扣题

本文主要是介绍最长公共子序列力扣题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划。
美团暑期面试题，没做过，不会啊。

这个问题的目标是找出两个字符串text1和text2的最长公共子序列的长度。

动态规划数组的初始化

首先，代码初始化了一个动态规划（DP）数组dp，其维度为(m + 1) x (n + 1)，其中m和n分别是text1和text2的长度。这个DP数组用于存储子问题的解，dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度。初始化时，所有元素都设置为0。

dp = [[0] * (n + 1) for _ in range(m + 1)]

填充DP数组

接下来，代码通过两层循环遍历这个DP数组，外层循环变量i从1到m，内层循环变量j从1到n。这里，i和j分别代表text1和text2当前考虑的字符位置。

for i in range(1, m + 1):for j in range(1, n + 1):

对于每一对(i, j)，我们比较text1[i - 1]和text2[j - 1]（即当前考虑的字符）。

• 如果这两个字符相等，说明我们找到了一个公共子序列中的字符，所以dp[i][j]应该是这个字符加上之前的最长公共子序列的长度，即dp[i - 1][j - 1] + 1。

if text1[i - 1] == text2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1

• 如果这两个字符不相等，那么当前的最长公共子序列的长度将是两种情况中的较大值：一种是不包含text1[i - 1]时的最长公共子序列长度dp[i - 1][j]，另一种是不包含text2[j - 1]时的最长公共子序列长度dp[i][j - 1]。

else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

返回结果

最后，dp[m][n]包含了整个问题的解，即text1和text2的最长公共子序列的长度。

return dp[m][n]

这个动态规划解法的核心在于逐步构建解的过程，它利用了子问题的解来解决更大的问题，直到解决了整个问题。通过填充DP数组，我们可以高效地找到两个字符串的最长公共子序列的长度。

整合：

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# 计算字符串长度m, n = len(text1), len(text2)# 初始化序列长度数组dp = [[0] * (n + 1) for _ in range(m + 1)]# 双重遍历for i in range(1, m+1):for j in range(1, n+1):# 如果当前字符相等，那最长公共子序列就应该是之前的加上现在的一个if text1[i-1] == text2[j-1]:dp[i][j] = dp[i - 1][j - 1] + 1# 否则，应该是那么当前的最长公共子序列的长度将是两种情况中的较大值# 一种是不含第一个字符串的当前字符# 一种是不含第二个字符串的当前字符else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回最终结果return dp[m][n]

这篇关于最长公共子序列力扣题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---