Structured Sharing for Dynamic Programming Extended Abstract
Nicolas Wu · 2013
Dynamic programming is a technique for designing algorithms to solve certain optimisation problems. It is similar to the divideand-conquer method in that a problem is split into subproblems that are recursively solved, and the subsolutions are combined to form a final solution. However, unlike divide-and-conquer, the subproblems are not necessarily independent. Indeed, the efficiency of dynamic programming algorithms relies on sharing the solutions to subproblems that are revisited. The usual approach to dynamic programming is to use an array to store the subsolutions. The construction of the array begins with base cases, and must carefully respect the dependencies that subsolutions have. As a motivating example, we will be considering the minimum edit distance problem, which nicely demonstrates how a recursive definition can be turned into a more efficient dynamic algorithm. In this problem we are concerned with finding the minimal edit distance of two strings. One such measure is the Levenshtein distance, which is the minimum number of substitutions, insertions, and deletions of single characters that can be made to turn one string into another.