Minimum Number of coin with given denom for a given amount

ncents.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int denom[] = { 1, 5, 10, 25 };

int ncents(int val, vector<unsigned int> &numCoins)
{
  for(int i=0; i < sizeof(denom)/sizeof(int); i++)
  {
    if (val == denom[i])
      numCoins[val] = 1;

    if (val - denom[i] >= denom[0])
    {
      if (numCoins[val-denom[i]] == -1)
      {
	if (ncents(val-denom[i], numCoins) == -1)
	  continue;
      }
      
      numCoins[val] = min(numCoins[val-denom[i]]+1, numCoins[val]);
    }
  }

  cout << "Val " << val << " " << numCoins[val] << endl ;
}

int main()
{
  int val = 20;
  vector<unsigned int> numCoins(val+1,-1);
  numCoins[0] = 0;
  ncents(val, numCoins);
  return 0;
}