07-孩子有多像爸爸-最长的公共子序列

4.3　孩子有多像爸爸——最长的公共子序列

假设爸爸对应的基因序列为X={x₁，x₂，x₃，…，x_m}，孩子对应的基因序列Y={y₁，y₂，y₃，…，y_n}，那么怎么找到他们有多少相似的基因呢？

如果按照严格递增的顺序，从爸爸的基因序列X中取出一些值，组成序列Z={x_i1，x_i2，x_i3，…，x_ik}，其中下标{i₁，i₂，i₃，…，i_k }是一个严格递增的序列。那么就说Z是X的子序列，Z中元素的个数就是该子序列的长度。

X和Y的公共子序列是指该序列既是X的子序列，也是Y的子序列。

最长公共子序列问题是指：给定两个序列X={x₁，x₂，x₃，…，x_m}和Y={y₁，y₂，y₃，…，y_n}，找出X和Y的一个最长的公共子序列。