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.


  • 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;