Recursive formulation Theorem c门=c+1=1+1 ifx=yl] max c[i-1,1, c[i,j-1]) otherwise Proof. Case x[=yU小 X y etz.k=LCS(x[.il,yll.D, where ci,jI k. Then, =k=xi, or else z could be extended Thus, zll. k-l is Cs ofx. i-1 and yll.j-11 c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.5© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.5 Recursive formulation Theorem. c[i, j] = c[i–1, j–1] + 1 if x[i] = y[j], max{c[i–1, j], c[i, j–1]} otherwise. Let z[1 . . k] = LCS(x[1 . . i], y[1 . . j]), where c[i, j] = k. Then, z[k] = x[i], or else z could be extended. Thus, z[1 . . k–1] is CS of x[1 . . i–1] and y[1 . . j–1]. Proof. Case x[i] = y[j]: L 1 2 i m L 1 2 j n x: y: =