Count the number of distinct ways to make an amount N, with C coins.

Coins.cpp

#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();
}