CC150 9.8

9_8.cpp

/* CC150 9.8 */
// represent n cents with quarters, dimes, nickels and pennies

#include <iostream>
#include <vector>

using namespace std;

// Return representation details
// repres: cnt25, cnt10, cnt5, cnt1
void representCents(vector<int> repres, int n, int lastCoin, vector<vector<int>> &represList)
{
	if (n == 0) { // store representing result
		represList.push_back(repres);
		return;
	}
	int coins[4] = { 25, 10, 5, 1 };
	for (int i = 0; i != 4; ++i) { // increment counts of all kinds of coins 
		if (n >= coins[i] && (lastCoin == 0 || coins[i] <= lastCoin)) { // AVOID DUPLICATIONS!
			++repres[i];
			representCents(repres, n - coins[i], coins[i], represList);
			--repres[i];
		}
	}
}

vector<vector<int>> representCents(int n)
{
	vector<vector<int>> represList;
	vector<int> repres(4, 0);
	representCents(repres, n, 0, represList);
	return represList;
}

// Return number of ways only
// Recursion approach
int represCount(int n, int denoms[], int currCoin)
{
	if (currCoin == 3)
		return 1;
	int count = 0;
	for (int i = 0; i * denoms[currCoin] <= n; ++i)
		count += represCount(n - i * denoms[currCoin], denoms, currCoin + 1);
	return count;
}

int represCount(int n)
{
	int denoms[] = { 25, 10, 5, 1 };
	return represCount(n, denoms, 0);
}

// DP approach
int represCountDP(int n, int denoms[], int index, vector<vector<int>> &buff)
{
	if (buff[n][index])
		return buff[n][index];
	int count = 0;
	for (int i = 0; i * denoms[index] <= n; ++i)
		count += represCount(n - i * denoms[index], denoms, index + 1);
	buff[n][index] = count;
	return count;
}

int represCountDP(int n)
{
	int denoms[] = { 25, 10, 5, 1 };
	vector<vector<int>> buff(n + 1, {0, 0, 0, 1});
	return represCountDP(n, denoms, 0, buff);
}

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> represList = representCents(n);
	cout << represList.size() << " ways to represent " << n << " cents." << endl;
	cout << "Combinations (quarter, dime, nickel, penny): " << endl;
	for (auto repres : represList) {
		for (auto i : repres)
			cout << i << " ";
		cout << endl;
	}
	cout << represCount(n) << " ways to represent " << n << " cents. " << endl;
	cout << represCountDP(n) << " ways to represent " << n << " cents. " << endl;
	return 0;
}