| x | "" | B | D | C | A | B | A | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| "" | |||||||||||||
| A | |||||||||||||
| B | |||||||||||||
| C | |||||||||||||
| D | |||||||||||||
| A | |||||||||||||
| B | |||||||||||||
假令X ＝ "ABCDAB"， Y＝"BDCABA"，各自取出最短的序列，也就是空字符串与空字符串比较。LCS的方程解为一个数字，那么这个表格也只能填数字。两个空字符串的公同区域的长度为0.
| x | "" | B | D | C | A | B | A | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| "" | 0 | ||||||||||||
| A | |||||||||||||
| B | |||||||||||||
| C | |||||||||||||
| D | |||||||||||||
| A | |||||||||||||
| B | |||||||||||||
然后我们X不动，继续让空字符串出阵，Y让“B”出阵，很显然，它们的公共区域的长度为0. Y换成其他字符， D啊，C啊， 或者， 它们的连续组合DC、 DDC， 情况没有变， 依然为0. 因此第一行都为0. 然后我们Y不动，Y只出空字任串，那么与上面的分析一样，都为0，第一列都是0.
| x | "" | B | D | C | A | B | A | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| "" | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||
| A | 0 | ||||||||||||
| B | 0 | ||||||||||||
| C | 0 | ||||||||||||
| D | 0 | ||||||||||||
| A | 0 | ||||||||||||
| B | 0 | ||||||||||||
LCS问题与背包问题有点不一样，背包问题还可以设置-1行，而最长公共子序列因为有空子序列的出现，一开始就把左边与上边固定死了。
然后我们再将问题放大些，这次双方都出一个字符，显然只有两都相同时，才有存在不为空字符串的公共子序列，长度也理解数然为1。
A为"X", Y为"BDCA"的子序列的任意一个
| x | "" | B | D | C
内容版权声明：除非注明，否则皆为本站原创文章。 |
|---|