Problems which are amenable to this technique have both optimal substructure and overlapping subproblems, which distinguishes it from "divide and conquer" and allows the use of memoization.
One use of this technique is an efficient algorithm for computing Levenshtein distances, a fact which is used in the Smith-Waterman algorithm for optimal local sequence alignments. This technique can also be used to generate a pseudo-polynomial time solution to the 0-1 knapsack problem that runs in time proportional to the product of the number of items and the size of the knapsack. Other applications include the (*) CYK algorithm for bottom-up parsing of context free grammars. Problems which are amenable to this technique have both optimal substructure and overlapping subproblems, which distinguishes it from "divide and conquer" and allows the use of memoization. For 10 points, name this algorithm design technique in which the optimal solutions to increasingly large subproblems are recorded in a table.
One use of this technique is an efficient algorithm for computing Levenshtein distances, a fact which is used in the Smith-Waterman algorithm for optimal local sequence alignments.
dynamic programming