Skip to content

Instantly share code, notes, and snippets.

@reddragon
Created Oct 11, 2014
Embed
What would you like to do?
Count the number of distinct ways to make an amount N, with C coins.
#include <iostream>
#include <cstring>
// This is a toy program, so please excuse the trivial flaws.
#define MAXN 2000
#define MAXC 20
// An N*C array, hard-coding the max N = 2000, C = 20.
int r[MAXN][MAXC];
int cval[MAXC];
int N, C;
/**
* O(N*C) solution.
* N is the sum to make, and C is the number of coins you can use. In the method
* n is the amount we have to make, and c denotes the coin number which is the
* smallest coin we can use, i.e., we can only use coins [Cc, Cn-1]. This is to
* prevent double counting.
*/
int f(int n, int c) {
int &res = r[n][c];
if (res != -1) {
return res;
}
if (n == 0) {
return res = 1;
}
res = 0;
for (int i = c; i < C; i++) {
int rem = n - cval[i];
if (rem >= 0) {
res += f(rem, i);
}
}
return res;
}
/**
* Given a sum N, find out the number of distinct ways you can make it with a
* given set of coins. All permutations are counted only once.
*/
int f(int n) {
memset(r, -1, sizeof(r));
return f(n, 0);
}
void demo() {
C = 3;
// Use just 3 coins.
cval[0] = 1; cval[1] = 2; cval[2] = 5;
for (int i = 0; i <= 20; i++) {
std::cout << "Number of ways to make " << i << " " << f(i) << std::endl;
}
}
int main() {
demo();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment