Dynamic Programming

• Dynamic Programming is an Algorithm applied to recursive problems.

  • It is usually applied to optimization algorithm with optimal substructure — that is, the optimal solution incorporates optimal solutions to related subproblems. This can be discovered with the following pattern
    • The problem involves making a choice which splits the problem into one or more subproblems.
    • For subproblems, we assume that the choice leads to an optimal solution (regardless of how it is obtained).
    • As a result of the choice, we determine which subproblems are present and thus characterize the subproblem space — typically we want simpler spaces first.
    • Show that the solutions to the subproblems used within an optimal solution to the problem must themselves be optimal via cut and paste — cutting out the non-optimal solution to the subproblem and pasting in the optimal one leads to a better solution.
  • Because of optimal substructure, we can decompose the problem into subproblems and solve them independently. The optimal substructure of a problem varies in:
    • How many subproblems are used for an optimal solution
    • How many choices we have to determine which subproblems to use.
  • Subproblems exhibit the following properties:
    • Subproblems are independent. That is, the solution to one subproblem does not affect the solution of another subproblem of the same problem.
    • Subproblems are overlapping. That is, a naive recursive solution to the problem revisits the same problem repeatedly .
  • Subproblems can be organized using a subproblem Graph where vertices corresponds to subproblems and all edges are of the form where is a subproblem that requires the solution of subproblem .

• The general framework follows the following steps

  • Characterize the optimal solution structure
  • Recursively define the value of an optimal solution
  • Compute the value of an optimal solution, typically in bottom up fashion.
  • Construct an optimal solution from computed information.

• Dynamic Programming is less about building giant tabulations, and more about doing recurrences smartly.

Performance §

• Dynamic Programming prevents us from efficiently redoing work for subproblems that have already been computed.

  • One approach is through memoization or caching all computed solutions to subproblems. This imposes a space time tradeoff
    • If some subproblems need not be solved, then the top down approach is faster than the corresponding bottom-up approach.
  • Another approach is to use a bottom-up approach where we solve subproblems based on “size” such that we solve smaller subproblems first. Larger problems only depend on smaller subproblems. No subproblem is solved until all its dependents are solved.
    • Typically if all subproblems must be solved at least once, a bottom up approach outperforms the corresponding memoized approach by a constant factor.

• With the subproblem graph in mind, typically the run time of a DP approach is given as

  Where is the time to solve each subproblem. This is also the number of choices we have per subproblem (on average).

  Typically the time for subproblem is given by , in which case a DP approach is .

• If we want something that can be done quickly, a Greedy Algorithm might be better.

Specific Problems §

• Longest Common Subsequence Problem

  Given two sequences and , we wish to find the maximum-length subsequence of and

  A subsequence of is defined as a sequence where are indices.

• Optimal Binary Search Tree

  Given a sequence of distinct keys in sorted order, a set dummy keys such that

  represents all values less than , for represents all values between

  And a probability distribution associated with each key and dummy key which indicates the probability of them being queried

  Find the binary tree which minimizes the expected search cost in the tree .

• Edit Distance Problem

  Let be a string we wish to transform to a target string . Find the least number of transformations needed.

  The transformations allowed are chosen from the following. Let be a working array that is initialized as empty, and which, by the end of the algorithm, is made so that

  Throughout the process we maintain an index for and for .

  • Copy a character so that , then increment both and

  • Replace a character from by another character , setting .

  • Delete a character from by incrementing .

  • Insert the character into by setting and incrementing

  • Twiddle the next two characters by copying the next two characters in reverse order so that

  • Kill the remainder of by setting . It must be the final operation if performed.

Links §

• CLRS - Ch. 15