# 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

#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:


### 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

#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

#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