若X={A,B,C,B,D,A,B} ,Y={B,D,C,A,B,A} 试用动态规划法计算其最长公共子序列
时间: 2023-10-08 11:04:17 浏览: 31
动态规划求解最长公共子序列的步骤如下:
1. 定义状态:设f[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列长度。
2. 初始化状态:f[0][j]和f[i][0]都为0,表示空序列与任意序列的最长公共子序列长度为0。
3. 状态转移方程:当X[i]等于Y[j]时,f[i][j]等于f[i-1][j-1]加1,表示当前字符可以加入最长公共子序列中;当X[i]不等于Y[j]时,f[i][j]等于max(f[i-1][j],f[i][j-1]),表示当前字符不能加入最长公共子序列中,取上一个状态中较大的值。
4. 最终结果:最长公共子序列的长度为f[n][m],其中n和m分别是X和Y的长度。
根据上述步骤,可以得到以下状态转移矩阵:
| | | A | B | C | B | D | A | B |
|----|---|---|---|---|---|---|---|---|
| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 2 |
| D | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| C | 0 | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| A | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
| B | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 4 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
因此,最长公共子序列为{B,C,A,B},长度为4。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)