观山湖网站建设推广,wordpress主题域名授权破解,app关键词优化,网站会员注册怎么做动态规划。 美团暑期面试题#xff0c;没做过#xff0c;不会啊。
这个问题的目标是找出两个字符串text1和text2的最长公共子序列的长度。
动态规划数组的初始化
首先#xff0c;代码初始化了一个动态规划#xff08;DP#xff09;数组dp#xff0c;其维度为(m 1) x …动态规划。 美团暑期面试题没做过不会啊。
这个问题的目标是找出两个字符串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, m1):for j in range(1, n1):# 如果当前字符相等那最长公共子序列就应该是之前的加上现在的一个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]
