Chapter 6

Dynamic Programming notes

• Divide & conquer algorithms are characterized by the fact that they divide the input into smaller groups and solve the problem recursively. Unlike D&C, however, it tends to require memoization - making “memos” of values stored in an array, so as to prevent recalculating values.
• The first example of such a problem is Weighted Interval Scheduling: Like interval scheduling but each interval has a value and we want to maximize the sum value.
  • Thus, we store the optimal value for each interval (working backward) by the insight that we either schedule or do not schedule an interval. We then pick the solution that gives the maximum value.
  • We can memoize the values given at an interval i by saying M[i] = max(solution(i-1), v_i+solution(p(i)) where p(i) is the next interval that fits with i.
    • Note that this only gives the value, not the solution itself. To find that, we have to go back up, selecting the intervals themselves that yield maximum value
• Thus we can do each of these in O(n) time.

• If we have an algorithm that relies on memoization to solve a dynamic programming problem, you can express it iteratively as well.
• Dynamic programming problems are identified by the facts that:
  • The number of subproblems is polynomial
  • The solution to the original problem is easily computed from the subproblem
  • The subproblems have some natural ordering.

• Here we want to make a “best-fit” piecewise function - a best-fit line given by multiple line segments, where there's some sort of cost associated with adding an additional segment.
• In order to do this, we look at all pairs (i,j) where i⇐j and compute the least-squares error for the i→j segment.
• We memoize M[j] =min(error(i,j)+C+opt(i-1)) where C is some constant giving the price of segmentation.
• We return M[n].
• This has O(n^3)

• Given n objects with weights w_i and values v_i for each i⇐n, how do we pack a backpack with weight capacity W so as to maximize value?
• The memoization for this problem is a little unintuitive, and we have to memoize for both each additional item i and each additional unit of weight up to and including W.
  • We recursively pick the items that maximize our knapsack's value. For new items, this is either the new item j, plus the old solution for W-j and the other available items, or it is the old solution for W and the other available items. Again, the key insight is that we either do or do not pick an item.
• This runs in O(nW) time, and finding the solution that yields the optimal value takes O(n) time, because you have to work back from the end of the memoized array.