418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 7

ให้ $OPT(i,j)\,$ เป็นความยาวที่มากที่สุดของ common subsequence ของ $x[1...i]\,$ และ $y[1...j]\,$

แนวคิดจะทำการพิจารณาว่าตัวอักษร $y_{j}\,$ ตรงกับตัวอักษร $x_{i}\,$ หรือไม่ ถ้าตรงแสดงว่าเราได้ common subsequence มาแล้วหนึ่งตัว แต่ถ้าไม่ตรง อาจเป็นไปได้ที่ตัวอักษร $y_{j}\,$ นี้ไปตรงกับตัวอักษรที่ $x_{i-1}\,$ หรือ ตัวอักษร $x_{i}\,$ ไปตรงกับตัวอักษร $y_{j-1}\,$ ซึ่งการที่เราจะเลือกกรณีไหน ก็ขึ้นอยู่กับว่ากรณีนั้นต้องมี common subsequence ยาวที่สุด ดังนั้นเราจะได้ว่า

$OPT(i,j)=0\,$ ถ้า $i=0\,$ หรือ $j=0\,$

$OPT(i,j)=max(OPT(i-1,j),OPT(i,j-1))\,$ ถ้า $x_{i}!=y_{j}\,$

$OPT(i,j)=1+OPT(i-1,j-1)\,$ ถ้า $x_{i}=y_{j}\,$

เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c"> LCS(x,n,y,m)

   for i=1 to n do
       M[i,0] = 0
   for j=1 to m do
       M[0,j] = 0
   for i = 1 to n do
       for j = 1 to m do
           if x[i] = y[j] then
               M[i,j] = 1+M[i-1,j-1]
           else
               M[i,j] = max(M[i-1,j],M[i,j-1])
   return M[n,m]

</geshi>

เห็นได้ชัดว่าอัลกอริทึมข้างต้นใช้เวลาทำงานเป็น $O(n)+O(m)+O(nm)=O(nm)\,$