---
# System prepended metadata

title: Dynamic Programming I
tags: [Dynamic Programming]

---

# Dynamic Programming I
 
###### tags: `Dynamic Programming`

>Prerequisite: Recursion 

## Content
[ToC]


## The rod cutting problem (1-Demension DP)



### Problem Statement
```
Input: 
    n, the lenght of a steel rod
    p[i], the price of a rod of lenght i
    
Output:
    the maximum revenue r
    
Example:
    length i:  1  2  3  4  5  6  7  8  9  10  11  
    price p[i]:2  5  6  9 11 16 17 20 22  24  25
```
The possible ways to sell a rod with length 3: (p[1]+p[2]), (p[1]+p[1]+p[1]), and (p[2]+p[1]). The maximum revenue will be 7 (p[1]+p[2]).

Obviously, we use the recursion to solve the problem r[j] (best revenue of length j) since r[0],... r[j-1] shares the common optimal substructures. Therefore, we can get the recursion relation as following:

```
r[0] = 0
r[j] = max{r[j-i]+p[i]}, where i = 1,2,...j
```

### Top-Down Method
Once we have the recursion relation, we can now move to our top-down recursion function. We will need an array s[] to store the current cut point of the rod of length j, and the array s[] can help us to backtrack all of the cut points of the rod of length j. As the pseudo code below:
```
function top_down(p[], j, s[])
    if j == 0: 
        return 0;
    else:
        for i = 1 to j
            k = top_down(p, j-i, s);
            if k+p[i] > max
                max = k+p[i];
                s[j] = i;
        return max;
```

### Memoized Top-Down Method
As we all know, the top down method will not be a polynomial time algorithm. If we use a recursion tree to represent our algorithm, we will get several same substree. For example, if we get the maximum revenue as below:
```
lenght i: 0  1  2  3  4  5  6  7  8  9  10
revenue:  0  2  5  7 10 12 16 18 21 23  26
array s:  0  1  2  1  2  1  6  1  1  2  1 
```
If we first calculate the max revenue of length 4, we will next call the recursion function to calculate max revenue of length 2 and 2. After finishing calculating the first length 2, we will calculate the length 2 again, which has already been calculated in the previous recursion. 

Hence, we can state that this recursion has overlapping subproblems. 

Therefore, we can use a method to record which length of the rod has been calculated. The method can be a tabular method that contains the current recorded max revenue value. Once the length i has been calculated, we will directly assign the value when we meet length i next time. The method is called memoization.

As the code following:


```
function top_down_memoized(p[], j, s[], check[])
    if j == 0: 
        return 0;
    else:
        for i = 1 to j
            if check[j-i] != 0:
                k = check[j-i];
            else:
                k = top_down(p, j-i, s);
            if k+p[i] > max
                max = k+p[i];
                check[j] = max;
                s[j] = i;
        return max;
```
### Dynamic Programming
Now we can move to implement dynamic programming. The implementation of dynamic programming is similar to memoized top-down method. Yet, DP is based on the top-down method.

Recall the recursion relation equation:

```
r[0] = 0
r[j] = max{r[j-i]+p[i]}, where i = 1,2,...j
```
In order to calculate r[j], we have to first calculate r[1], r[2], ...r[j-1], then find an index i such that r[j-i]+p[i] is maximum.

As the following code:

```
function DP(k, p[], s[]):
    r[0] = 0;
    for j = 1 to k:
        for i = 1 to j:
            if r[j-i] + p[i] > r[j]:
                r[j] = r[j-i] + p[i];
                s[j] = i; 
```
### Complexity
Complexity of dynamic programming will be the size of table times the operation complexity to fill a single cell of the table. Therefore, the overall complexity will be $O(n^2)$.



### C++ Code
```cpp=
#include <iostream>
using namespace std;

//let r[j] be the maximum revenue for lenght j
// r[j] = 0, when j = 0
// r[j] = max{p[i] + r[j-i]} for i = 1~j
int top_down(int p[], int j, int s[]){
    if(j == 0) return 0;
    else{
        int max = 0;
        for(int i = 1; i <= j; i++){
            int k = top_down(p, j-i, s);
            if(p[i] + k > max){
                max = p[i]+k;
                s[j] = i;
            }
        }
        return max;
    }
}

int top_down_with_memoized(int p[], int j, int s[], int check[]){
    if(j == 0) return 0;
    else{
        int max = 0;
        for(int i = 1; i <= j; i++){
            int k;
            if(check[j-i] != 0) k = check[j-i];
            else
                k = top_down_with_memoized(p, j-i, s, check);
            if(p[i] + k > max){
                max = p[i]+k;
                check[j] = max;
                s[j] = i;
            }
        }
        return max;
    }
}

int DP(int k, int p[], int s[]){
    int r[k];
    memset(r, 0, sizeof(r));
    for(int j = 1; j <= k; j++){
        for(int i = 1; i <= j; i++){
            if(r[j-i] + p[i] > r[j]){
                r[j] = r[j-i] + p[i];
                s[j] = i;
            }
        }
    }
    return r[k];
}

void backtrack(int s[], int k){
    if(k == s[k]) cout << k << " ";
    else{
        backtrack(s, s[k]);
        backtrack(s, k-s[k]);
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int p[12] = {0,2,5,6,9,11,16,17,20,22,24,25};
    int s[12];
    int check[12];
    int k = 11;
    memset(s, 0, sizeof(s));
    memset(check, 0, sizeof(check));
    cout << top_down(p, k, s) << endl;
    cout << top_down_with_memoized(p, k, s, check) << endl;
    cout << DP(k, p, s) << endl;
    backtrack(s, k);
    return 0;
}
//output:
//28
//28
//28
//1 2 2 6 
```



## Matrix-Chain Multiplication

### Problem Statement


```
Input: 
    (p0,p1,...,pn): dimension of n matrices A1A2...An, where Ai = pi-1*pi.

Output:
    parenthesize A1A2...An to minimize the number of scalar multiplcation.
    
Example: (p0,p1,p2,p3) = (10, 100, 5, 50)

    1. ((A1A2)A3) = 10*100*5 + 10*5*20 = 7500 (min)
    2. (A1(A2A3)) = 100*5*50 + 10*100*50 = 75000
```
### Optimize Substructure
```
If ((A1(A2A3))((A4(A5A6))A7)) is an optimal solution to A1A2...A7, then

    (A1(A2A3) is an optimal solution to A1A2A3.

    (A4(A5A6))A7) is an optimal solution to A4A5A6A7.
```
As we see, we can write down the recursion relation through the optimal substructure we've discussed previously. Suppose we can divide the matrix-chain (Ai...Aj) into two parts at index k, we will need to calculate the left part (Ai...Ak) ,right part (Ak+1...Aj) and p[i-1]*p[k]*p[j]. The reason why we need to calculate the value of p[i-1]*p[k]*p[j] is that the dimension of (Ai...Ak) is p[i-1]*p[k]; also, the dimension of (Ak+1...Aj) is p[k+1]*p[j].

Therefore, let m[i,j] be the minimum number of scalar multiplications for computing Ai...Aj; then, we need to find the index k such that m[i,j] = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j] is minimum.

### Recursion Relation
```
m[i,j] = 0, if i = j
m[i,j] = min{m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]} where i<=k<j && i < j
```
Before moving into the algorithm, we will need to decide the order of filling up the DP table.

We will need to fill m[i,j] with the knowledge of m[i,k], m[k+1, j] where k = i..j-1. Therefore, use the diagonal line to fill the table as the following graph:

![](https://i.imgur.com/J3pg4gL.png)

 
### Pseudo Code
```
function Matrix_Chain(p[]):
    N = p.length;
    for i = 1 to N: m[i,i] = 0
    for l = 2 to N:
        for i = 1 to n-l+1:
            j = i+l-1;
            m[i,j] = inf;
            for k = i to j-1:
                min = m[i,k] = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j];
                if min < m[i,j]:
                    m[i,j] = min;
                    s[i,j] = k;
```

Note that the diagonal line l will be started at 2.
```
When l = 1 (i = j), j-i+1 = l. Therefore, j=i+l-1.

Since j <= N, i+l-1 <= N. Therefore, i <= N-l+1
```

s[i,j] indicates that the separation point of Ai...Aj. Then we will use s[i,j] to backtrack the parentheses pattern of Ai...Aj.

### Complexity
Complexity of dynamic programming will be the size of table times the operation complexity to fill a single cell of the table. Therefore, the overall complexity will be $O(n^3)$.



### C++ Code

```cpp=
#include <iostream>
using namespace std;

int m[100][100];
int s[100][100];

void backtrack(int, int);
void DP(int p[], int N){
    for(int i = 1; i < N+1; i++){
        for(int j = 1; j < N+1; j++){
            m[i][j] = 0;
            s[i][j] = 0;
        }
    }
    for(int i = 1; i <= N; i++) m[i][i] = 0;
    for(int l = 2; l <= N; l++){
        for(int i = 1; i <= N-l+1; i++){
            int j = l+i-1;
            m[i][j] = INT_MAX;
            for(int k = i; k < j; k++){
                int min = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if(min < m[i][j]) {
                    m[i][j] = min;
                    s[i][j] = k;
                }
            }
        }
    }
    cout << m[1][N] << endl;
    backtrack(1, N);
}

void backtrack(int i, int j){
    if(i == j) cout << "A" << i;
    else{
        cout << "(";
        backtrack(i, s[i][j]);
        backtrack(s[i][j]+1, j);
        cout << ")";
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int p[] = {30,35,15,5,10,20,25};
    DP(p, 6);
    return 0;
}
//Output:
//15125
//((A1(A2A3))((A4A5)A6))
```

## 0-1 Knapsack Problem

### Problem Statement

Given weights and value of n items, select some items to put into a knapsack of capacity W to get the maximum total value in the knapsack.

```
Input:
    W = 50
    value[]:  {60, 100, 120}
    weight[]: {10, 20, 30}
Output: 220
```
### Optimal Substructure

Consider that the i-th item will have two conditions: i-th item is put in the knapsack; i-th item is not put in the knapsack. Therefore, the optimal solution will exist in these two conditions. Let C[i, w] be the total value of all i items and maximum weight w.

```
Putting i-th item into knapsack, then
    C[i,w] = C[i-1,w-weight[i]] + value[i]
    
Not putting i-th item into knapsack, then
    C[i,w] = C[i-1,w]
    
Since we will need to choose the optimal solution, then
    C[i,w] = max(C[i-1,w-weight[i]] + value[i], C[i-1,w])
```
Note that we will get C[i,w] = 0 if we don't assign any item (i = 0) or give a 0 weight (w = 0) knapsack. Also, if the knapsack weight is not enough for the i-th item, then we cannot put i-th iten into the knapsack. Therefore, the final recursion will be:
```
C[i,w] - 0. if i = 0 or w = 0
C[i,w] = max(C[i-1,w-weight[i]] + value[i], C[i-1,w]) if w ≥ weight[i]
C[i,w] = C[i-1,w] if w ≤ weight[i]
```

### Pseudo Code

```
function 0-1Knapsack(val[], weight[], W, n)
    for i = 0 to n:
        for w = 0 to W:
            if i == 0 || w == 0:
                DP[i,w] = 0;
            else 
                if w ≥ weight[i]:
                    DP[i,w] = max(DP[i-1,w],DP[i-1,w-weight[i]]+value[i]);
                else:
                    DP[i,w] = DP[i-1,w]    
```
### Complexity

Complexity of dynamic programming will be the size of table times the operation complexity to fill a single cell of the table. Therefore, the overall complexity will be $O(nW)$.

### C++ Code

```cpp=
#include <iostream>
#include <math.h>
using namespace std;

int DP[100][100];

int func(int val[], int wt[], int i, int j){
    if(i == 0|| j == 0) return 0;
    if(j >= wt[i]) return func(val, wt, i-1, j);
    else{
        return max(func(val, wt, i-1, j), func(val, wt, i-1, j-wt[i-1])+val[i-1]);
    }
}

void knapsack(int val[], int wt[], int W, int n){
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= W; j++){
            if(i == 0 || j == 0)
                DP[i][j] = 0;
            else{
                if(j >= wt[i-1]){
                    DP[i][j] = max(DP[i-1][j], DP[i-1][j-wt[i-1]]+val[i-1]);
                }
                else
                    DP[i][j] = DP[i-1][j];
            }
        }
    }
    cout << DP[n][W] << endl;
}


int main(int argc, const char * argv[]) {
    // insert code here...
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    knapsack(val, wt, W, n);
    cout << func(val, wt, n, W);
    return 0;
}
//Output:
//220
//220
```
