用动态规划求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列
时间: 2023-11-10 20:06:44 浏览: 145
动态规划求解最长公共子序列的步骤如下:
1. 定义状态:$dp[i][j]$ 表示字符串序列 $s1$ 的前 $i$ 个字符和字符串序列 $s2$ 的前 $j$ 个字符的最长公共子序列长度。
2. 状态转移方程:当 $s1_i == s2_j$ 时,$dp[i][j] = dp[i-1][j-1] + 1$,否则 $dp[i][j] = max(dp[i-1][j], dp[i][j-1])$。
3. 边界条件:$dp[0][j]=0$ 和 $dp[i][0]=0$。
4. 最终结果:$dp[len(s1)][len(s2)]$。
根据上述步骤,可以得到字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列长度为 4,即“BDAB”:
| | | B | D | C | A | B | A |
|:-:|---|---|---|---|---|---|---|
| | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| D | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| B | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
相关问题
用动态规划求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列,求代码
939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958动态规划求解最长公共子序列的思路如下:
1. 定义状态:dp[i][j, 959, 960, 961, 962, 963, 964, 965, 966, 967, ]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。
2.968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 状态转移方程:当A[i] == B[j]时,dp[i][j] = dp[i-1][j- 978, 979, 980, 981, 982, 983, 984, 985, 986, 9871] + 1;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1, 988, 989, 990, 991, 992, 993, 994, 995, 996, ])。
3. 初始状态:dp[0][j] = dp[i][0] = 0,表示其中一个字符串为空字符串时,它们的最长公共子序列长度为0。
4. 最终结果:dp[m][n],其中m、n分别为字符串A、B的长度。
以下是Python实现代码:
```python
def longest_common_subsequence(str1, str2):
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]
str1 = 'ABCDBAB'
str2 = 'BDCABA'
print(longest_common_subsequence(str1, str2)) # 输出结果为 4
```
时间复杂度为$O(mn)$,其中m、n分别为字符串A、B的长度。
求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列
这是一个经典的动态规划问题,可以使用动态规划算法来求解。
首先,定义一个二维数组dp,其中dp[i][j]表示序列1中前i个字符和序列2中前j个字符的最长公共子序列的长度。
然后,我们可以通过以下公式来计算dp[i][j]的值:
如果序列1的第i个字符等于序列2的第j个字符,则dp[i][j] = dp[i-1][j-1] + 1。
如果序列1的第i个字符不等于序列2的第j个字符,则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最后,dp[len1][len2]即为所求的最长公共子序列的长度,其中len1和len2分别为序列1和序列2的长度。
对于字符串序列“ABCDBAB”和“BDCABA”,可以通过动态规划算法求得它们的最长公共子序列为“BCBA”,其长度为4。