最长公共子序列递归备忘录
时间: 2023-11-25 09:51:24 浏览: 36
最长公共子序列问题是指:给定两个字符串,求它们的最长公共子序列。递归备忘录是一种优化算法的方法,可以避免重复计算。下面是最长公共子序列递归备忘录的实现:
```python
def lcs(s1, s2):
memo = [[None] * (len(s2) + 1) for _ in range(len(s1) + 1)]
def lcs_helper(i, j):
if memo[i][j] is not None:
return memo[i][j]
if i == len(s1) or j == len(s2):
result = 0
elif s1[i] == s2[j]:
result = 1 + lcs_helper(i+1, j+1)
else:
result = max(lcs_helper(i+1, j), lcs_helper(i, j+1))
memo[i][j] = result
return result
return lcs_helper(0, 0)
```
其中,memo[i][j]表示s1[i:]和s2[j:]的最长公共子序列的长度。lcs_helper(i, j)是递归函数,用于计算memo[i][j]的值。如果memo[i][j]已经被计算过,则直接返回memo[i][j]的值;否则,根据s1[i]和s2[j]是否相等,分别计算memo[i][j]的值,并将其存入memo[i][j]中。