一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=<x1,x2,…,xm>，則另一序列Z＝<z1，z2，…，zk>是X的子序列是指存在一個嚴格遞增的下標序列<i1,i2,…,ik>,使得對于所有j=1,2,…,k有：Xij=Zj
例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相應的遞增下標序列為<2,3,5,7>。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X＝<A,B,C,B,D,A,B>和Y＝<B,D,C,A,B,A>，則序列<B,C,A>是X和Y的一個公共子序列,序列 <B,C,B,A>也是X和Y的一個公共子序列。而且，后者是X和Y的一個最長公共子序列．因為X和Y沒有長度大于4的公共子序列。
給定兩個序列X＝<x1，x2，…，xm>和Y=<y1,y2…．yn>．要求找出X和Y的一個最長公共子序列。