头歌求字符串序列“abcdbab”和“bdcaba”的最长公共子序列
时间: 2023-10-22 16:03:20 浏览: 117
我们可以使用动态规划算法来求解这个问题。
首先,定义状态:令 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子序列长度。
然后,初始化状态:dp[0][j] 和 dp[i][0] 均为 0。
接着,考虑状态转移方程:
当 s1[i-1] == s2[j-1] 时,dp[i][j] = dp[i-1][j-1] + 1;
当 s1[i-1] != s2[j-1] 时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最后,最长公共子序列的长度即为 dp[n][m],其中 n 和 m 分别是字符串 s1 和 s2 的长度。
按照上述算法,我们可以得到以下动态规划表格:
| dp | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| :----: | - | - | - | - | - | - | - |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| 3 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| 4 | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| 5 | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| 6 | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
因此,字符串序列“abcdbab”和“bdcaba”的最长公共子序列长度为 4,即序列“bcba”。