Counting Change Combinations

• Time : $O(money * coin)$
• Space : $O(money)$

c++

#include <vector>
unsigned long long countChange(const unsigned int money, const std::vector<unsigned int>& coins) {
    std::vector<unsigned long long> dp(money + 1);
    dp[0] = 1;
    for(auto& c : coins) {
        for(unsigned int i = c; i <= money; i++) dp[i] += dp[i-c];
    }
    return dp[money];
}