Minimum coin change in C++ - a dynamic programming question

Key takeaways:
Optimal solution through dynamic programming: The dynamic programming approach efficiently solves the coin change problem by avoiding redundant calculations, reducing time complexity to $O(M \cdot N)$ .
Recursive solution’s limitations: The recursive approach has exponential time complexity $O(2^N)$ , making it inefficient for larger inputs due to overlapping subproblems.
Memoization for optimization: Using memoization in the recursive approach (top-down dynamic programming) reduces redundant calculations, improving efficiency and reducing time complexity to $O(M \cdot N)$ .
Real-world applicability: This problem models scenarios like currency exchange, resource allocation, and vending machines, where optimal combinations of available denominations must be found to meet a target amount.
Commonly asked in interviews: The coin change problem is frequently posed in technical interviews, especially for software engineering roles, as it tests problem-solving skills and proficiency in recursion, dynamic programming, and algorithm optimization.

What is the minimum coin change?

The minimum coin change problem is a classic problem in which you are given a total amount of money and a set of coin denominations. The goal is to determine the minimum number of coins needed to make up the given amount. If it is not possible to achieve the target amount using the available denominations, the solution should return $-1$ .

Problem statement

Given an integer total representing the target amount of money and a list of integers coins representing coin denominations, determine the minimum number of coins required to achieve the target. If it’s not possible to form the target using the given coins, return $-1$ . If the target amount is $0$ , return $0$ .

Note: You can assume that we have an infinite number of each kind of coin.

Constraints:

$1 \leq$ coins.length $\leq 12$
$1 \leq$ coins[i] $\leq 10^4$
$0 \leq$ total $\leq 900$

Examples

Solution to find minimum coin change

The coin change problem can be solved using two different approaches:

Recursive approach
Dynamic programming approach

We’ll take a look at both of these approaches in detail, along with their code examples and explanations.

1. Recursive approach

The recursive approach tries all combinations of coins to reach the target amount, reducing the target by each coin value in every step. It finds the minimum coins required but is inefficient due to repeated calculations, leading to exponential complexity.

Here are the detailed steps of the algorithm discussed above:

We iterate through each coin in the coins array:
1. If a coin’s value is less than or equal to the remaining target (N), we make a recursive call for the new target N - coin.
2. We calculate the minimum number of coins required by taking the minimum of all possible subproblem results, adding 1 for the current coin used.
The recursive function returns the minimum number of coins if a solution exists; otherwise, it returns -1.

Let’s look at the example code for the recursive approach:

#include <bits/stdc++.h>
using namespace std;
int minCoins(int coins[], int m, int N) {
    if (N == 0)
        return 0;
    // Initialize result to a large value
    int res = INT_MAX;
    for (int i = 0; i < m; i++) {
        // Check if the coin can be used (coin value <= remaining target)
        if (coins[i] <= N) {
            // Recursive call for the reduced amount
            int sub_res = minCoins(coins, m, N - coins[i]);
      
            // Update the result if a smaller value is found
            if (sub_res != INT_MAX) // Ensure no overflow
                res = min(res, 1 + sub_res);
        }
    }
  
    return res;
}
int main() {
    struct TestCase {
        vector<int> coins; // Coin denominations
        int target;        // Target amount
    };
  
    TestCase testCases[] = {
        {{1, 2, 3, 4, 5}, 11},
        {{2, 5, 10}, 7},
        {{1}, 3},
        {{5, 10, 25}, 30},
        {{3, 7}, 5}
    };
  
    int totalTests = sizeof(testCases) / sizeof(testCases[0]);
    for (int i = 0; i < totalTests; i++) {
        TestCase tc = testCases[i];
        int m = tc.coins.size();
        int result = minCoins(tc.coins.data(), m, tc.target);
    
        cout << "Test case " << i + 1 << ":\n";
        cout << "\tCoins: [";
        for (int j = 0; j < tc.coins.size(); j++) {
            cout << tc.coins[j];
            if (j != tc.coins.size() - 1)
                cout << ", ";
        }
        cout << "]\n";
        cout << "\tTarget: " << tc.target << "\n";
        cout << "\tMinimum coins required: " << (result == INT_MAX ? -1 : result) << "\n";
        cout << string(100, '-') << "\n";
    }
  
    return 0;
}

Recursive approach to solve the coin change problem

Complexity analysis

Time complexity: The time complexity of the recursive approach is $O(2^N)$ in the worst case, because at each step, we explore every coin denomination for every possible subproblem, leading to an exponential number of function calls due to overlapping subproblems.

Space complexity: The space complexity is $O(N)$ because the maximum depth of the recursion tree is proportional to the target amount $N$ , and we store the function call stack for each recursive call.

2. Dynamic programming approach

The dynamic programming approach uses a dp[] array to store the minimum coins needed for each amount. It builds solutions iteratively, avoiding redundant calculations and making it more efficient.

Here are the detailed steps of the algorithm discussed above:

We create a dp[] array of size N + 1 where dp[i] stores the minimum number of coins needed to make up the sum i.
1. Initialize all entries of dp[] to INT_MAX except dp[0], which is 0 because no coins are needed to make a sum of 0.
We loop through all possible target sums from 1 to N:
1. For each target sum, we check every coin in the coins array.
2. If the coin’s value is less than or equal to the current sum, we update dp[i] using:

#include <bits/stdc++.h>
using namespace std;
int minCoins(int coins[], int M, int N) {
    vector<int> dp(N + 1, INT_MAX);
    dp[0] = 0;
    // Fill the dp array for all amounts from 1 to N
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            if (coins[j] <= i) {
                if (dp[i - coins[j]] != INT_MAX) {
                    dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
                }
            }
        }
    }
    // If dp[N] is still INT_MAX, no solution exists
    return dp[N] == INT_MAX ? -1 : dp[N];
}
int main() {
    struct TestCase {
        vector<int> coins; // Coin denominations
        int target;        // Target amount
    };
    TestCase testCases[] = {
        {{1, 2, 3, 4, 5}, 11},
        {{2, 5, 10}, 7},
        {{1}, 3},
        {{5, 10, 25}, 30},
        {{3, 7}, 5}
    };
    int totalTests = sizeof(testCases) / sizeof(testCases[0]);
    for (int i = 0; i < totalTests; i++) {
        TestCase tc = testCases[i];
        int m = tc.coins.size();
        int result = minCoins(tc.coins.data(), m, tc.target);
        cout << "Test case " << i + 1 << ":\n";
        cout << "\tCoins: [";
        for (int j = 0; j < tc.coins.size(); j++) {
            cout << tc.coins[j];
            if (j != tc.coins.size() - 1)
                cout << ", ";
        }
        cout << "]\n";
        cout << "\tTarget: " << tc.target << "\n";
        cout << "\tMinimum coins required: " << result << "\n";
        cout << string(100, '-') << "\n";
    }
    return 0;
}

Dynamic programming approach to solve the coin change problem

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What are the differences between the recursive and dynamic programming approaches?

Recursive approach: This approach solves the problem by exploring all possible combinations of coin denominations recursively. It checks each coin to see if it can contribute to the solution, which leads to a lot of redundant calculations.
Dynamic programming approach: This method optimizes the recursive approach by storing the results of previously solved subproblems in a dp[] array. It avoids redundant calculations, making it much more efficient.

Why is the recursive approach inefficient?

The recursive approach is inefficient because it recalculates the results of the same subproblems multiple times. For example, if a coin is included, the same subproblem (with a reduced amount) is solved again in multiple recursive branches, leading to exponential time complexity

When would the coin change problem be useful?

The coin change problem can be useful in scenarios where you need to make a specific amount with limited resources (such as coins or currency), such as in vending machines, automated ticketing systems, or even in dynamic pricing models.

Aspect	Recursive	Dynamic Programming
Approach	Top-down, repeatedly solving subproblems	Bottom-up, solving subproblems iteratively
Time complexity	O(2^N), exponential due to overlaps	O(M⋅N), efficient
Space complexity	O(N) for recursion stack	O(N) for the `dp` array
Optimal for large value of `N`	No	Yes

Minimum coin change in C++ - a dynamic programming question

What is the minimum coin change?

Problem statement

Examples

Knowledge test

Solution to find minimum coin change

1. Recursive approach

Complexity analysis

2. Dynamic programming approach

Complexity analysis

Comparison of both approaches

Additional resources

Frequently asked questions

What are the differences between the recursive and dynamic programming approaches?

Why is the recursive approach inefficient?

When would the coin change problem be useful?