然后我们让Y多出一个D做帮手,{"",A,B,AB} vs {"",B,D,BD},显然,继续填1. 一直填到Y的第二个B之前,都是1。 因为到BDCAB时,它们有另一个公共子序列,AB。
x | "" | B | D | C | A | B | A | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
"" | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||
A | 0 | 0 | 0 | 0 | 1 | 1 | 1 | ||||||
B | 0 | 1 | 1 | 1 | 1 | 2 | |||||||
C | 0 | ||||||||||||
D | 0 | ||||||||||||
A | 0 | ||||||||||||
B | 0 |
到这一步,我们可以总结一些规则了,之后就是通过计算验证我们的想法,加入新的规则或限定条件来完善。
Y将所有字符派上去,X依然是2个字符,经仔细观察,还是填2.
看五行,X再多派一个C,ABC的子序列集合比AB的子序列集合大一些,那么它与Y的B子序列集合大一些,就算不大,就不能比原来的小。显然新增的C不能成为战力,不是两者的公共字符,因此值应该等于AB的子序列集合。
× | "" | B | D | C | A | B | A | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
"" | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||
A | 0 | 0 | 0 | 0 | 1 | 1 | 1 | ||||||
B | 0 | 1 | 1 | 1 | 1 | 2 | 2 | ||||||
C | 0 | 1 | |||||||||||
D | 0 | ||||||||||||
A | 0 | ||||||||||||
B | 0 |
并且我们可以确定,如果两个字符串要比较的字符不一样,那么要填的格子是与其左边或上边有关,那边大就取那个。