applying dynamic programming to the lcs problem recall that in the lcs problemwe are given two character stringsx and of length and mrespectivelyand are asked to find longest string that is subsequence of both and since and are character stringswe have natural set of indices with which to define subproblems--indices into the strings and let us define subproblemthereforeas that of computing the value , which we will use to denote the length of longest string that is subsequence of both prefixes [ jand [ kthis definition allows us to rewrite , in terms of optimal subproblem solutions this definition depends on which of two cases we are in (see figure , , , max( , , =gt cc taa ta =gt ctaa ycgataat tgaga ycgataat tgag ( (bfigure the two cases in the longest common subsequence algorithm for computing , (ax - yk- (bx - yk- - yk- in this casewe have match between the last character of [ jand the last character of [ kwe claim that this character belongs to longest common subsequence of [ jand [ kto justify this claimlet us suppose it is not true there has to be some longest common subsequence xa xa xac yb yb ybc if xac - or ybc yk- then we get the same sequence by setting ac and bc alternatelyif xac  - and ybc yk- then we can get an even longer common subsequence by adding - yk- to the end thusa longest common subsequence of [ jand [ kends with - thereforewe set , - , - if - yk- - yk- in this casewe cannot have common subsequence that includes both - and yk- that iswe can have common subsequence end with - or one that ends with yk- (or possibly neither)but certainly not both thereforewe set , max{ - , , - if - yk- we note that because slice [ is the empty stringl , for nsimilarlybecause slice [ is the empty stringl , for