问题: 已知序列str1和序列str2,求出他们的最长公共子序列。
dp[i][j]的定义: str[0-i]和str[0-j]所拥有的最长公共子序列。
法一:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def length_common_strength(str1, str2) -> int:
"""
递归法求解
:param str1:
:param str2:
:return:
"""
def dp(i, j):
if i == -1 or j == -1: return 0
if str1[i] == str2[j]:
return dp(i-1, j-1) + 1
else:
return max(dp(i-1, j), dp(i, j-1))
return dp(len(str1) - 1, len(str2) - 1)
|
法二:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def length_common_strength_dp(str1, str2) -> int:
"""
dp背包
:param str1:
:param str2:
:return:
"""
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if str1[i-1] == str2[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]
|
