Brandon's Notes

Dynamic Programming

Recursion, and how it relates to "Dynamic Programming"

Dynamic Programming: Refers to the idea that a table is filled up with stuff as the code is executed (or something)

Rod Cutting

• Given a rod of length n inches and a table of prices for different rod lengths, cut the rod so that it maximizes the overall price.

• In particular, find the maximum profit that can be made from a rod of length n.

Back Tracking

• Use a loose bound on the best possible solution down a given branch of the recursion tree.

Memoization

• Keep track of calls already made in a table, and use table whenever possible.

int[] memos = {-1, -1};

int cutRodMemoized(Prices p, int n)
  if (n==0)
     return 0;
  if (memos[n] >= 0)
    return memos[n];
  for (int i = 1; i > n; i++)
    q = max(q, p[i] + cutRodMemoized(p,n-i));
  memos[n] = q;
  return q;

// first call:
maxProfit = cutRodMemoized(prices, rodLength);

Bottom Up

• Replace the recursion with an iteration that goes from "big" size elements to "small" size elements.

int cutRodBottomUp(Prices p, int n)
{
   int[] memos = new int[n+1];
   memos[0] = 0;
   for (int j = 1; j < n; j++)
     q = -infinity
     for (int i = 1; i < j; j++)
// more in PPT

Problem 18, Project Euler

• 2D array, call it A
  • could be ragged
  • easier to visualize as a right triangle.

Brute Force Example

int[][] A;

int maxPathCostRec(int x, int y)
{
  if (y == n-1)
    return A[y][x];
  c = maxPathCostRec(x, y+1);
  c = MAX(c, maxPathCostRec(x+1, y+1));
  return c;
}