Dynamic Programming

Coin Problem

LeetCode question: 322. Coin Change What is the smallest number of coins required to form a sum x?

Iterative + 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];
}