We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Coin Change Problem
  5. Discussions

The Coin Change Problem

  • jerryz88
     + 1 comment

    Bottom up approach. First sort coins in ascending order. For each coin, we either take it or don't. If we don't take it, it is the value before. And if we take it, the i value must be greater than coin value and dp[i - coin] would have already been calculated so just add that.

    long getWays(int n, vector<long> c) {
    std::vector<uint64_t> dp(n+1, 0);
    dp[0] = 1;
    std::sort(c.begin(), c.end());
    for (auto coin : c)
    {
        for (auto i = 0; i <= n; ++i)
        {
            if (i >= coin)
            {
                dp[i] += dp[i - coin];
            }
        }
    }
    return dp[n];
}