Algorithms - Dynamic Programming

1. Bottom-up
   Starting at the smallest value, we can calculate any functions using previously computed values at each step.


2. Top-down
   This allows us to execute recursive functions at the same cost (or less cost than) as the bottom-up dynamic programming in an automatic way. We implement the recursive code to save each value that it computes as its final action. We also check the saved values to avoid recomputing as its first action. This is also called memoization.

The difference will be more clear when we look at the Fibonacci



codes below.

#include <iostream>
using namespace std;

const int MAX = 1001;

// recursive
int fibo_rec(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fibo_rec(n-1)+fibo_rec(n-2);
}

// bottom-up
int fibo_bu(int n)
{
    int map[MAX];
    map[0] = 0;
    map[1] = 1;

    for(int i = 2; i <= n; i++) 
		map[i] = map[i-1]+map[i-2];	
    return map[n];
}

// top-down
int fibo_td(int n)
{
    static int map[MAX];
    if(map[n] > 0) return map[n];
    if(n == 0) 
	map[n] = 0;
    else if(n == 1) 
	map[n] = 1;
    else
	map[n] = fibo_td(n-1)+fibo_td(n-2);

    return map[n];
}

int main()
{
    cout << fibo_rec(10) << endl;
    cout << fibo_bu(10) << endl;
    cout << fibo_td(10) << endl;

    return 0;
}





Number of ways to reach at the top of stairs

Given a n-step stair case, the code below counts the ways of reaching at the stop of stairs. There are three ways of stepping: 1, 2, or 3 steps.





We use top-down approach. In other words, suppose we are at the last step (n-1, n-2, or n-3), the number of ways up to that point (i.e. the last step) is the step count we want to calculate.

The code takes two approach: simple recursive (count()) and dynamic programming (countDP()):

#include <iostream>
using namespace std;

const int N = 100;

int count(int n)
{
	if(n < 0) return 0;
	if(n == 0) return 1;

	return count(n-3)+count(n-2)+count(n-1);
}

int countDP(int n)
{
	static int map[N];
	if(n < 0) return 0;
	if(n == 0) return 1;
	if(map[n] > 0) return map[n];
	map[n] = countDP(n-3)+countDP(n-2)+countDP(n-1);
	return map[n];
}

int main()
{
	int steps = 10;
	cout << count(steps) << endl;      // 274
	cout << countDP(steps) << endl;;   // 274
	return 0;
}





Minimum number of coins for a given change



Recursive Coin Change

In this problem, we need to use minimum number of coins to make a given amount for a set of denominations.

Amount = 40 cents, and denominations are $\{1, 5, 10, 25\}$.

We need to choose the smallest of the following:

1. 1 + MinChange(39) - a penny (=1) given
2. 1 + MinChange(35) - a nickel (=5) given
3. 1 + MinChange(30) - a dime (=10) given
4. 1 + MinChange(15) - a quarter (=25) given

In other words, we have the following recursive formula:

1. Define $C[j]$ to be the minimum number of coins we need to make change for $j$ cents.
2. Denominations are given as $$D = \{d_1, d_2, ..., d_k\}.$$
3. If we know that an optimal solution for the problem of making change for $j$ cents using a coin of denomination $d_i$, we have: $$C[j] = 1 + C[j-d_i].$$
4. Recursively define the value of an optimal solution. $$C[j] = \begin{cases} \infty & \text{if }j < 0, \\ 0 & \text{if }j = 0, \\ 1 + min_{1 \le i \le k} (C[j-d_i]) & \text{if }j \ge 1 \end{cases}$$

Here is the code:

#include <iostream>
using namespace std;

int CoinChange(int amount, int d[], int size)
{
    if(amount <= 0) return 0;
    int min_coins =(int)INT_MAX;

    for(int i = 0; i < size; i++) {
	if(d[i] <= amount) 
	    min_coins = min(min_coins, CoinChange(amount-d[i], d, size) + 1);
    }
    return min_coins;
}

int main()
{
    int d[] = {1, 5, 10, 25};
    int amount = 40;
    int size = sizeof(d)/sizeof(d[0]);
    int ans = CoinChange(amount, d, size);
    cout << "Minimal # of coins = " << ans << endl;

    return 0;
}

Output is:

Minimal # of coins = 3





Dynamic programming - Coin Change I

We now know how to solve coin change problem recursively. The recursive algorithm looks elegant and concise, however, when we go a little bit deeper, we can realize it's doing the same calculation repeatedly. As a result, it dramatically slows down as the problem size gets bigger, and the time required increases almost exponentially. So, we want to keep the calculation time as polynomial. That's why we need dynamic programming.

The recursive algorithm reduces the amount of change whenever we call CoinChange() until the change amount becomes 0. In other words, we used top-down approach. However, in the following dynamic programming code, we will take bottom-up approach.

We can use the following formula: $$C[j] = \begin{cases} \infty & \text{if }j < 0, \\ 0 & \text{if }j = 0, \\ 1 + min_{1 \le i \le k} (C[j-d_i]) & \text{if }j \ge 1 \end{cases}$$

So, starting from $C[0] = 0$ where no coin is required for change $0$. Then, to the next one: $$C[1] = min \begin{cases} 1 + (C[1-d_1]) \\ 1 + (C[1-d_2]) \\ ... \\ 1 + (C[1-d_k]) \end{cases}$$

$$C[2] = min \begin{cases} 1 + (C[2-d_1]) \\ 1 + (C[2-d_2]) \\ ... \\ 1 + (C[2-d_k]) \end{cases}$$

Here is the code:

#include <iostream>
using namespace std;

int CoinChangeDynamic(int amount, int d[], int size, int C[])
{  
    C[0] = 0;
    for(int j = 1; j <= amount; j++) {
	C[j] = INT_MAX;
	for(int i = 0; i < size; i++) {
	    if(j >= d[i] && 1 + C[j-d[i]] < C[j] ) {
		C[j] = 1 + C[j-d[i]];
	    }
        }
    }     
    return C[amount];
}

int main()
{
    int d[] = {1, 5, 10, 25};
    int amount = 67;
    int size = sizeof(d)/sizeof(d[0]);
    int *C = new int[amount+1];
    int ans = CoinChangeDynamic(amount, d, size, C);
    cout << "Minimal # of coins = " << ans << endl;
    delete[] C;

    return 0;
}

Output:

Minimal # of coins = 6

We can also check which denominations were used by recording the denomination index for a specific amount of changes:

#include <iostream>
using namespace std;

int CoinChangeDynamic(int amount, int d[], int size, int C[], int s[])
{  
    C[0] = 0;
    for(int j = 1; j <= amount; j++) {
	C[j] = INT_MAX;
	for(int i = 0; i < size; i++) {
	    if(j >= d[i] && 1 + C[j-d[i]] < C[j] ) {
		C[j] = 1 + C[j-d[i]];

		// i-th denomination used for the amount of j
		s[j] = i;  
	    }
	}
    }
    return C[amount];
}

int main()
{
    int d[] = {1, 5, 10, 25};
    int amount = 67;
    int size = sizeof(d)/sizeof(d[0]);
    int *C = new int[amount+1];
    int *s = new int[amount+1];
    int ans = CoinChangeDynamic(amount, d, size, C, s);
    cout << "Minimal # of coins = " << ans << endl;
	
    cout << "coins used: " ;
    int k = amount;
    while(k) {
	cout << d[s[k]] << " ";
	k = k - d[s[k]];
    }

    delete[] C;
    delete[] s;

    return 0;
}

Output is;

Minimal # of coins = 6
coins used: 1 1 5 10 25 25

In main() code, the array $s[k]$ represents the index for the biggest denomination at specific amount of change:

k     0 1 2 3 4 5 6 7 8 9 10 11 12 ... 21 22 23 24 25 26 27... 65 66 67
s[k]  0 0 0 0 0 1 1 1 1 1  2  2  2  2   2  2  2  2  3  3  3 3   3  3  3







Dynamic programming - Coin Change II

In this section, though the basic theory is the same as before, we're going to use a table form (2D array).

Let $D = \{d_0, d_1, ..., d_{k-1}\}$ be the set of coin denominations, arranged such that $d_0 = 1 \text{ cent}$. As before, the problem is to make change for n cents using the fewest number of coins.

1. Use a table $C[0...k-1][0...n]$ where $n = amount$:
   $C[i][j]$ is the smallest number of coins used to make change for $j$ cents, using only coins $d_0, d_1, ..., d_{k-1}$.
2. The overall number of coins (the final optimal solution) will be computed in $C[k][n]$

The algorithm looks like this:

1. Making change for $j$ cents with coins $d_0, d_1, ..., d_{k-1}$ can be done in two ways:
   1. Don't use coin $d_i$ (even if it's possible): $$C[i][j] = C[i-1][j]$$
   2. Use coin $d_i$ and reduce the amount: $$C[i][j] = 1+C[i][j-d_i].$$
2. We will pick the solution with least number of coins: $$C[i][j] = min(C[i-1][j], 1+C[i][j-d_i])$$

#include <iostream>
#include <vector>
using namespace std;

int CoinChange(int amount, int d[], int size, int s[])
{
    // C[i,j] = C[denomination, amount of change]
    vector<vector<int> > C(size, vector<int>(amount+1));	
    for(int i = 0; i < size; i++) 
	C[i][0] = 0;
    for(int j = 0; j <= amount; j++) {
	C[0][j] = j;
	s[j] = 0;
    }

    for(int i = 1; i < size; i++) {
	for(int j = 1; j <= amount; j++) {
	    if(j < d[i]) {
		C[i][j] = C[i-1][j];
	    }
	    else {
		C[i][j] = min(C[i-1][j], C[i][j-d[i]] + 1);
		s[j] = i;  
	    }
	}
    }
    return C[size-1][amount];
}


int main()
{
    int d[] = {1, 5, 10, 25};
    int amount = 67;
    int size = sizeof(d)/sizeof(d[0]);
    int *s = new int[amount+1];
    int ans = CoinChange(amount, d, size, s);
    cout << "Minimal # of coins = " << ans << endl;
    cout << "coins used: " ;
    int k = amount;
    while(k) {
	cout << d[s[k]] << " ";
	k = k - d[s[k]];
    }
    delete[] s;

    return 0;
}

Output:

Minimal # of coins = 6
coins used: 25 25 10 5 1 1




For recursive, please visit C++ - Recursion

Or C++ - Math & Probability.





Knapsack Problems

Please visit Algorithm - Knapsack problems.






Note: To use formula, visit LaTex.












bogotobogo.com site search: