Dynamic Programming

Coin Problem

From the Competitive Programmer’s Handbook. What is the smallest number of coins required to form a sum $x$?

Recursive Solution

bool ready[N]; 
int value[N];
 
int solve(int x) {
	if (x < 0) return INF;
	if (x == 0) return 0;
	if (ready[x]) return value[x];
	int best = INF;
	for (auto c : coins) {
		best = min(best, solve(x-c)+1);
	}
	value[x] = best;
	ready[x] = true;
	return best;
}

My recent submission on LeetCode where I return -1 when no solution exists.

Iterative solution + storing solution

value[0] = 0;
for (int x = 1; x <= n; x++) {
	value[x] = INF;
	for (auto c : coins) {
		if (x-c >= 0 && value[x-c]+1 < value[x]) {
			value[x] = value[x-c]+1;
			first[x] = c; // Store Solution
		}
	}
}
 
//Print Solution
while (n > 0) {
	cout << first[n] << "\n";
	n -= first[n];
}