1 写出最长公共子序列问题 最优子结构性质 2 写出最长公共子序列问题 求解递归式 3 设 X=( c, b, d, b), Y=( b, a, b, d, b, b) 写出c表格和b表格 写出最长公共子序列长度和最长公共子序列
时间: 2023-12-16 19:05:11 浏览: 15
1. 最长公共子序列问题具有最优子结构性质,即两个序列的最长公共子序列,可以通过它们的子序列的最长公共子序列推导得出。
2. 最长公共子序列问题的递归式为:
当 X[m] == Y[n] 时,LCS(X[1:m], Y[1:n]) = LCS(X[1:m-1], Y[1:n-1]) + 1
当 X[m] != Y[n] 时,LCS(X[1:m], Y[1:n]) = max(LCS(X[1:m], Y[1:n-1]), LCS(X[1:m-1], Y[1:n]))
其中,LCS(X[1:m], Y[1:n])表示X的前m个字符和Y的前n个字符的最长公共子序列长度。
3. X=(c, b, d, b),Y=(b, a, b, d, b, b) 的c表格和b表格如下:
c表格:
| X/Y | '' | b | a | b | d | b | b |
|------:|-----:|----:|----:|----:|----:|----:|----:|
| '' | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| c | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 | 1 | 2 | 3 |
| d | 0 | 1 | 1 | 1 | 2 | 2 | 3 |
| b | 0 | 1 | 2 | 2 | 2 | 3 | 4 |
b表格:
| X/Y | '' | b | a | b | d | b | b |
|------:|-----:|----:|----:|----:|----:|----:|----:|
| '' | '' | '' | '' | '' | '' | '' | '' |
| c | '' | ↑ | ↑↓ | ↑ | ↑↓ | ↑↓ | ↑↓ |
| b | '' | ←↑ | ← | ←↑ | ←↑ | ↑↓ | ↑↓ |
| d | '' | ←↑ | ←↑ | ←↑ | ← | ←↑ | ↑↓ |
| b | '' | ←↑ | ←↑ | ←↑ | ←↑ | ←↑ | ← |
最长公共子序列长度为4,其中一个可能的最长公共子序列是:b, d, b, b.