# Introduction to Dynamic Programming – Cutting Rods

This problems is presented in Introduction to Algorithms as an intro to Dynamic Programming.
Given a rod of length `n` inches and a table of prices `pi` for rod lengths: `i = 1, 2, ... n`, determine the maximum revenue `rn` obtainable by cutting up the rod to pieces and selling them.
The table looks like this

A naive solution could be

```CUT-ROD(p, n)
q = 0
for i = 1 to n
q = max(q, p[i] + CUT-ROD(p, n - i))
return q```

This solution has exponential asymptotic time. So, we’re introduced to dynamic programing.
The method works as follows:

• We rearrange for each subproblem to be solved only once.
• If we need to refer to this subproblem’s solution again later, we can just look it up in a hash table or an array.

The modified version of the previous algorithm is:

```CUT-ROD(p, n)
if CUT-ROD(p, n) is solved before				// use previous solutions
return s[n]
q = 0
for i = 1 to n
q = max(q, p[i] + CUT-ROD(p, n - i))
s[n] = q							// store the new solution
return q```

There’s a top-down approach and a bottom-up approach:

• The top-down approach recurses from larger problems to smaller subproblems until it reaches a pre-calculated subproblem. After that, it returns then combines the solutions of subproblems to solve the larger ones. The previous algorithm is top-down.
• The bottom-up method, as you can tell from its name, solves all the required subproblems first then the larger ones. Both methods are `$O(n^2)$` but the bottom-up way has better constants.

To get a clear insight of what the difference is, see the following subproblem tree:

The subproblem graph for the rod-cutting problem with n = 4.
The vertex labels give the sizes of the corresponding subproblems.
A directed edge (x, y) indicates that we need a solution to subproblem y when solving subproblem x.
To the left is the naive solution.
To the right is the DP one.

Implemented below in `C++`.

```#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000;
int p[11];
int r[N], s[N];

// initializer for prieces and optimal solutions
void init() {
memset(r, -1, N);
r[0] = 0;
p[0] = 0;
p[1] = 1;
p[2] = 5;
p[3] = 8;
p[4] = 9;
p[5] = 10;
p[6] = 17;
p[7] = 17;
p[8] = 20;
p[9] = 24;
p[10] = 30;
}

// naieve exponential solution
int cutRod(int n) {
int q = 0;
for (int i = 1; i <= n; ++i)
q = max(q, p[i] + cutRod(n - i));
return q;
}

// top-down solution
int topDownCutRod(int n) {
if (r[n] != -1)
return r[n];
int q = 0;
for (int i = 1; i <= n; ++i)
q = max(q, p[i] + topDownCutRod(n - i));
return r[n] = q;
}

// bottom-up solution
int buttomUpCutRod(int n) {
if (r[n] != -1)
return r[n];
for (int j = 1; j <= n; ++j) {
int q = 0;
for (int i = 1; i <= j; ++i)
q = max(q, p[i] + r[j - i]);
r[j] = q;
}
return r[n];
}

// bottom-up solution that maintains not only the best price but also the "required cut" for such solution
int extendedButtomUpCutRod(int n) {
if (r[n] != -1)
return r[n];
for (int j = 1; j <= n; ++j) {
int q = 0;
for (int i = 1; i <= j; ++i)
if (q < p[i] + r[j - i]) {
q = p[i] + r[j - i];
s[j] = i;
}
r[j] = q;
}
return r[n];
}

// prins the extended method's output
void printCutRodSoln(int n) {
do
cout << s[n] << " ";
while ((n -= s[n]) > 0);
}

int main() {
init();
int n;
cin >> n;
cout << extendedButtomUpCutRod(n) << endl;
printCutRodSoln(n);
return 0;
}
```