给定序列 s1={1,3,4,5,6,7,7,8}s2={3,5,7,4,3,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。s1和s2的 其中一个最长公共子序列是{3,4,6,7,8}建表,画图
时间: 2024-04-27 15:24:57 浏览: 12
好的,下面是s1和s2的LCS的长度以及动态规划表格和对应的状态转移图:
LCS的长度为5。
动态规划表格:
| LCS长度 | 0 | 1 | 2 | 3 | 4 | 5 |
| :---------: | :-: | :-: | :-: | :-: | :-: | :-: |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 2 | 2 |
| 4 | 0 | 1 | 1 | 2 | 2 | 2 |
| 5 | 0 | 1 | 1 | 2 | 2 | 3 |
| 6 | 0 | 1 | 1 | 2 | 2 | 3 |
| 7 | 0 | 1 | 1 | 2 | 3 | 4 |
| 8 | 0 | 1 | 1 | 2 | 3 | 5 |
状态转移图:
![状态转移图](https://img-blog.csdn.net/20180515141612491?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzQ2OTMwOTM2MDkxODk0Mw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80)
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)