Dynamic programming Design technique, like divide-and-conquer Example: Longest Common Subsequence (LCs) Given two sequences x[l.. m] and yll.n], find a longest subsequence common to them both a' not the 2 :A CB DA B BCBA :B D C A B A LCS(, y) functional notation but not a function c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.2 Dynamic programming Design technique, like divide-and-conquer. Example: Longest Common Subsequence (LCS) • Given two sequences x[1 . . m] and y[1 . . n], find a longest subsequence common to them both. x:A B C B D A B y:B D C A B A “a” not “the” BCBA = LCS(x, y) functional notation, but not a function