## 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;
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;
}
``````