Puzzles for Programmers and Pros

6.7. Selective Greed

So far, except for our preview of overloaded scheduling and our use of speculation, the best strategy has smacked of a "follow your nose" (also known as greedy) approach:

If a move lowers the cost/gets closer to the solution, take it; otherwise, avoid it.

Sometimes that basic philosophy works but requires a slight modification:

Find the lowest cost solutions to subproblems, and then glue the solutions to the best subproblems together.

Welcome to dynamic programming. This is a technique with an enormous number of applications. We'll start with string editing, but soon you'll be planning menus.

The string edit problem is to convert a source string to a target string in the fewest number of "edits" possible. There are three kinds of edits: changing a letter (e.g., 'a' becomes 'b'), inserting a letter (e.g., replace a blank by 'c'), and deleting a letter (e.g., replacing 'c' by a blank). For example, to edit the word 'rent' to the semantically equivalent (if you live in the United Kingdom) 'let', we would change 'r' to 'l' and delete 'n'. To go the other way, we would change 'l' to 'r' and insert 'n'. The other letters don't change. Either way, the edit distance is 2.

6.7.1. Warm-Up

When the words are short, it is easy to find an answer by eye, but consider this example inspired by genomics.

How many edits are needed to convert 'TAGATGGTCT' to 'TGGAGACAGTCT'? ...