HGPA

Dynamic Programming (DP)

tl;dr

Dynamic Programming:

Technique (Skiena):

  1. formulate answer as recurrence relation or recursive function
  2. show number of different parameter values taken on by recurrence is bounded by a hopefully small polynomial
  3. specify an order of evaluation for the recurrence so that the partial results you need are always available

Examples

Three traditional examples:

Techniques

You always have to solve the subproblems first. There are two different approaches to do this:

Common Applications

Longest Common Substring: Given a set of strings, find the longest substring common to all strings. This could also be solved with a suffix tree.

Longest Common Subsequence (LCS): Given a set of sequences, find the longest subsequence common to all sequences. A subsequence of a string is a set of characters that appear in left-to-right order, but may not be consecutive. This is precisely what diff does.

Knapsack problem: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Subset Sum problem: Given set of integers is there is non-zero subset whose sum is zero? Special-case of knapsack.

Partition problem: Given a multiset of positive integers, can it be partitioned into two subsets such that the sum of the numbers in each subset are equal. Special-case of subset sum.

Cocke–Younger–Kasami (CYK): Parses context-free grammars.

TODO:

REFERENCES

Dynamic Programming. Wikipedia.

Longest Common Subsequences. David Eppstein. 1996-02-29.

Filename: dynamic-programming.md (Edit)
Modified: 2017-02-25 (2a439f02c6a8a5282b6b2152f312cbf219e25d4c)
Created: 2017-02-05 (64083d761ff026a97561f9a01c3907f20d024f9b)