Code challenged for dynamic programming. I solved using Boost's multiprecision library and test it using Boost's unit test.

MoneyChanger.cpp

//
//  MoneyChanger.cpp
//
//
//  Created by Liu Hao on 6/3/14.
//  http://haoliu.org
//  Copyright (c) 2014 liu hao. All rights reserved.
//

#include "MoneyChanger.h"
#include <iostream>


BoostInt MoneyChanger::howManyCombinations(double dollors) {
    //change it to cents and call combination function cents
    int cents = int(dollors*100);
    if (cents/100.0 != dollors) {
        throw MoneyChangerException("The input Money of MoneyChanger object cannot be represented by integer in cents");
    }
    //if overfloating, forward the exception as MoneyChangerException
    try {
        return howManyCombinationsInCents(cents);
    } catch (std::overflow_error &e) {
        std::string message = std::string("In computing for ")
                            + std::to_string(dollors) + std::string(". ")
                            + e.what();
        throw MoneyChangerException(message);
    }
    
}

BoostInt MoneyChanger::howManyCombinationsInCents(int cents) {
    // zero fast return
    if (cents == 0)
        return 1;
    // negative check
    if (cents < 0) {
        throw MoneyChangerException("The input Money of MoneyChanger object is negative");
    }
    // vectore memory check
    if (numOfCombinations.size() < cents + 1) {
        try {
            numOfCombinations.resize(cents + 1);
        } catch (std::bad_alloc& ba) {
            throw MoneyChangerException("bad_alloc caught in howManyCombinationsInCents");
        }
    }
    //find last calculated cents
    int startCents = maxCentsAvailavle / SKIP_STEP * SKIP_STEP;
    // begin the computing
    // Loop over cents
    for (int p = startCents; p <= cents; p += SKIP_STEP) {
        // get new space
        try {
            numOfCombinations[p].resize(NUM_OF_DENOMINATIONS + 1);
        } catch (std::bad_alloc& ba) {
            throw MoneyChangerException("bad_alloc caught in howManyCombinationsInCents");
        }
        numOfCombinations[p][1] = 1;
        // Loop over number of denominations to use
        for (int q = 2; q <= NUM_OF_DENOMINATIONS; ++q) {
            int lastDenomination = denominations[q - 1];
            // do dynamic programming bottom-up here
            if (lastDenomination < p)
                numOfCombinations[p][q] = safeADD(numOfCombinations[p-lastDenomination][q], numOfCombinations[p][q - 1]);
            else if(lastDenomination == p)
                numOfCombinations[p][q] = safeADD(1, numOfCombinations[p][q - 1]);
            else
                numOfCombinations[p][q] = numOfCombinations[p][q-1];
        }
        // TODO: here can save some memory if needed
        // set next (SKIP_STEP - 1) elements point to same vectors
        for (int offset = 1; offset < SKIP_STEP ; ++offset)
            numOfCombinations[p+offset] = numOfCombinations[p];
    }
    maxCentsAvailavle = maxCentsAvailavle < cents ? cents : maxCentsAvailavle;
    return numOfCombinations[cents][NUM_OF_DENOMINATIONS];
}

void MoneyChanger::printCombinationTable() {
    for (int p = 0; p <=maxCentsAvailavle; p+=1) {
        for (int q = 0; q <= NUM_OF_DENOMINATIONS; ++q)
            std::cout <<numOfCombinations[p][q] <<",";
        std::cout<<std::endl;
    }
}

MoneyChanger.h

//
//  MoneyChanger.h
//
//
//  Created by Liu Hao on 6/3/14.
//  http://haoliu.org
//  Copyright (c) 2014 liu hao. All rights reserved.
//


#ifndef __MoneyChanger__
#define __MoneyChanger__

#define NUM_OF_DENOMINATIONS 10
#define DENOMINATIONS {1,5,10,25,100,500,1000,2000,5000,10000}
#define SKIP_STEP 5


#include "BoostInt.h"
#include <exception>
#include <string>
#include <vector>


// The exception for MoneyChanger
class MoneyChangerException: public std::exception
{
    std::string message;
public:
    MoneyChangerException(std::string message) {
        this->message = "[Exception] in MoneyChanger: ";
        this->message += message;
    }
    virtual const char* what() const throw()
    {
        return message.c_str();
    }
};


//MoneyChanger to get the number of combinations
class MoneyChanger {
    // Denominations in cents
    std::vector<int> denominations;
    // numOfCombinations[n][k] store the number of
    // cimmbinations for n cents with first k denominations
    std::vector<std::vector<BoostInt> > numOfCombinations;
    // max number of cents have been calculated
    int maxCentsAvailavle;
    // use for safty adding
    BoostInt safeADD(BoostInt x, BoostInt y){
#ifdef  ___USING___LONGLONG___
        if( x < LOCAL_MAX - y)
            return x + y;
        else
            throw std::overflow_error("Overflowing in computation");
#else
        return x + y;
#endif
    }
public:
    MoneyChanger(){
        //init attributes
        maxCentsAvailavle = 0;
        denominations = std::vector<int>(DENOMINATIONS);
        // malloc the space for 0 cent, and calloc will init it with 0
        numOfCombinations.resize(1);
        numOfCombinations[0].resize(NUM_OF_DENOMINATIONS + 1);
        numOfCombinations[0] = {0};
    }
    // return the number of combination of given 'dollars'
    BoostInt howManyCombinations(double dollors);
    // return the number of combination of given 'cents'
    BoostInt howManyCombinationsInCents(int cents);
    void printCombinationTable();

};


#endif /* defined(__MoneyChanger__) */