Dynamic Programming, Part 2–2

Example of Dynamic Programming, Part 2

This is a note I took while taking Avik Das’ Dynamic Programming course at Linkedin Learning. His course is awesome and I highly recommend it!

Coin change problem

What is the least number of coins that can be used to reach the target amount?

Example) What is the minimum number of coins used to make 16 cents?

n-1 because we start from index 0

Approach 1 Recursion

C++

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int a[] = {1, 5, 12, 19};
int change(int i, int t)
{
    if (i == 0) return t;
    if (t == 0) return 0;
    if (t < 0) return INT_MAX - 1;
    return min(change(i, t-a[i]) + 1, change(i-1, t));
}
int main()
{
    int n, t;
    while(true){
        cin >> n >> t;
        cout << change(n-1, t) << endl;
    }
}

Approach 2.1: Dynamic Programming

The top-down approach of memorization. Using a 2-dimensional array for a cache.

C++

#include <iostream>
using namespace std;
int coin[4] = {1,5,12,19};
int cache[100][100];
int change(int i, int t){
    if (i==0) return t;
    if (t==0) return 0;
    if (t<0) return INT_MAX;
    if (cache[i][t] != -1) {
        return cache[i][t];
    }
    int result = min(change(i, t-coin[i]) + 1, change(i-1, t));
    cache[i][t] = result;
    return result;
}
int main()
{
    for(int i=0; i<100; i++){
        for(int j=0; j<100; j++){
            cache[i][j] = -1;
        }
    }
    int n, t;
    cin >> n >> t;
    cout << change(n-1, t) << endl;
}

Python

coin= [1,5,12,19]
cache = [[-1]*100] * 100
def change(i,  t):
    if i==0: return t
    if t==0: return 0
    if t<0: return INT_MAX
    if (cache[i][t] != -1):
        return cache[i][t]
    result = min(change(i, t-coin[i]) + 1, change(i-1, t))
    cache[i][t] = result
    return result
while True:
  n = int(input())
  t = int(input())
  print(change(n-1, t))

Approach 2.2: Dynamic Programming

The top-down approach of memorization. Using a hashmap.

C++

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int a[] = {1, 5, 12, 19};
std::map< std::pair<int, int>, int> cache;
int change(int i, int t)
{
    if (i == 0) return t;
    if (t == 0) return 0;
    if (t < 0) return INT_MAX - 1;
    auto r = cache.find(std::make_pair(i,t));
    if (r != cache.end()) {
        return cache[std::make_pair(i,t)];
    }
    int result = min(change(i, t-a[i]) + 1, change(i-1, t));
    cache[std::make_pair(i,t)] = result;
    return result;
}
int main()
{
    int n, t;
    while(true){
        cin >> n >> t;
        cout << change(n-1, t) << endl;
    }
}

python

coin= [1,5,12,19]
cache = {}
def change(i,  t):
    if i==0: return t
    if t==0: return 0
    if t<0: return 10000
    if (i,t) in cache == False:
        return cache[(i,t)]
    result = min(change(i, t-coin[i]) + 1, change(i-1, t))
    cache[(i,t)] = result
    return result
while True:
  n = int(input())
  t = int(input())
  print(change(n-1, t))

Bug Report

The above solution has a serious bug. If the smallest coin is not a 1cent coin, it will not work.

Below is a version that works for any coins. Here, the assumption is coin is sorted, but if not, you can sort it before running the algorithm.

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int a[] = {2, 5, 12, 19};
std::map< std::pair<int, int>, int> cache;
int change(int i, int t)
{
    if (i == 0 && a[i] == 1) {
        return t;
    } else if (i == 0 && a[i] != 1) {
        if (t % a[i] == 0 )
            return t / a[i];
        else
            return INT_MAX - 1;
    }
    if (t == 0) return 0;
    if (t < 0) return INT_MAX - 1;
    auto r = cache.find(std::make_pair(i,t));
    if (r != cache.end()) {
        return cache[std::make_pair(i,t)];
    }
    int result = min(change(i, t-a[i]) + 1, change(i-1, t));
    cache[std::make_pair(i,t)] = result;
    return result;
}
int main()
{
    int n, t;
    while(true){
        cin >> n >> t;
        cout << change(n-1, t) << endl;
    }
}