🌱 Keegan's Digital Garden

518. Coin Change II

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- dynamic programming approach used to count the number of ways to make up the given `amount` using the available coins
- use a bottom-up approach
- iterate through the coins and update the number of ways to make every amount from the coin's value up to the target amount
- ensure all combinations are correctly considered

🤔What Did I Struggle With?

- initial implementation failed for larger test cases due to integer overflow when using the int datatype for the dp array
- C++ couldnt handle the large values generated during the summation for scenarios where the number of ways to form an amount was very high
- resolve the issue by using `uint64` for the dp array, avoiding overflow

💡 Explanation of Solution

Key Idea

  • use a DP array where dp[x] represents the number of ways to form amount x using the given coins

Recurrence Relation

dp[x] = dp[x] + dp[x - coin[i]]

  • for each coin coin[i]
    • include coin[i] : add the number of ways to form x - coin[i] (reuse of coins allowed)
    • skip coin[i]: keeps the number of ways to form x without using this coin

Base Case

  • dp[0] = 1: there is exactly one way to make the amount 0 - by using no coins

Steps

  1. initialize a DP array of size amount + 1 with all elements set to 0
  2. set dp[0] = 1 to handle the base case
  3. iterate through each coin and update the DP array for all amounts from the coin’s value up to amount
  4. return dp[amount] as the result

⌛ Complexity Analysis

Time Complexity: O(n * amount)
- iterates through each of the `n` coins, and for each coin, updates the DP array for all amounts from the coin's value to `amount`

Space Complexity: O(amount)
- the dp array stores the number of ways to make each amount up to `amount`

💻 Implementation of Solution

/*
Recurrence Relation Explanation:
 
For each coin coin[i], to make amount x:
 
- Include coin[i]: Add the number of ways to make x - coin[i] (reuse of coins allowed).
- Skip coin[i]: Use the number of ways to make x without this coin.
 
Thus, the recurrence relation is:
 
    dp[x] = dp[x] + dp[x - coin[i]]
 
Where:
    dp[x] is the number of ways to make amount x.
    dp[0] = 1 (1 way to make amount 0: use no coins).
 
We update dp[x] for each coin iteratively to count the number of ways to form the amount.
*/
 
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
 
        // Use a vector of uint64_t to avoid overflow for large test cases.
        vector<uint64_t> dp(amount + 1, 0);
 
        // Base case: There's 1 way to make the amount 0 (use no coins).
        dp[0] = 1;
 
        // Iterate through coins from the last to the first.
        for (int coin = n - 1; coin >= 0; coin--) {
            // For each coin, update the dp array for all target amounts.
            for (int target = coins[coin]; target <= amount; target++) {
                dp[target] += dp[target - coins[coin]];
            }
        }
 
        // The answer is the number of ways to make the amount.
        return dp[amount];
    }
};

Graph View