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