Coin Change

Solution 1: Brute-Force approach

The naive approach to solving the coin change problem involves a recursive strategy to explore all possible combinations of coins to find the minimum number needed to make up the target amount. It starts by recursively trying each coin denomination to reduce the target amount.

For each coin, the algorithm subtracts the coin’s value from the current amount and solves the reduced problem. If the amount becomes zero, it indicates that no more coins are needed, and the function returns zero. If the amount becomes negative, it signals that this path is not feasible, so the function returns infinity or a large number. The algorithm combines the results from each recursive call with the current coin to determine the minimum number of coins required.

Finally, after exploring all possibilities, it returns the minimum number of coins found or -1 if it is not possible to make the target amount with the given coins.

Pseudocode
FUNCTION coin_change_naive(coins, amount):
    IF amount == 0:
        RETURN 0  // Base case: No coins are needed to make amount 0

    IF amount < 0:
        RETURN infinity  // Amount is negative, path is not feasible

    min_coins = infinity

    FOR EACH coin IN coins:
        result = coin_change_naive(coins, amount - coin)  // Recursively solve for the remaining amount
        IF result != infinity:
            min_coins = MIN(min_coins, result + 1)  // Update min_coins with the minimum value

    RETURN min_coins IF min_coins != infinity ELSE -1  // Return the minimum number of coins or -1 if no solution exists

Time Complexity: The solution has a time complexity of O(m^n), where n is the amount and m is the number of coin denominations. The exponential time complexity arises from the recursive exploration of all possible combinations of coins. Each recursive call generates multiple further calls, leading to an exponential growth in the number of computations required. The total number of recursive calls can be as large as $m^n$ due to the need to try each coin denomination for each sub-amount.

Space Complexity: The space complexity of the naive approach is O(n), where n is the target amount. The space complexity is determined by the maximum depth of the recursion stack. In the worst case, the recursion depth can be as deep as the target amount n (when using coins of value 1). Therefore, the space required for the call stack is proportional to the target amount.

As you can see, this solution does not perform very well. Let's take a look at a better solution.

Solution 2: Dynamic programming approach

Our solution employs a dynamic programming approach to determine the fewest number of coins needed to make up a given amount. We use a DP array, where each index represents a specific amount, and its value represents the minimum number of coins required to achieve that amount. The array is initialized with a value greater than the maximum possible number of coins needed (infinity), except for the base case where dp[0] is set to 0, indicating that zero coins are needed to make amount 0.

For each amount from 1 to the target amount, we iterate through each coin denomination and update the DP array. If the current amount minus the coin value is non-negative and the previous amount can be formed, we update the current amount’s value to be the minimum of its current value or one more than the value of the previous amount. This ensures that we are considering the fewest coins needed by checking each possible coin combination.

After processing all amounts, if the value for the target amount is still set to infinity, it means it's not possible to form the target amount with the given coins, and we return -1. Otherwise, we return the value at dp[amount], which represents the minimum number of coins needed.

Time Complexity: The solution has a time complexity of O(n * m), where n is the amount and m is the number of coin denominations. This is because we iterate over each amount from 1 to the target amount, and for each amount, we iterate over all coin denominations to update the DP array.

Space Complexity: The solution uses O(n) space for the DP array, where n is the target amount. The array stores the minimum number of coins required to make each amount up to the target amount. This space complexity is necessary to hold the results for all subproblems up to the target amount.