322. Coin Change

Description

The coin change problem is a classic dynamic programming problem where you are given a set of coin denominations and a target amount. The goal is to find the minimum number of coins needed to make up that amount. If it is not possible to make up the amount with the given coins, return -1.

Intuition

The intuition behind solving the coin change problem is to use a recursive approach with memoization to minimize redundant calculations. The problem can be broken down into subproblems where we try to make change for smaller amounts and build up the solution for the target amount. By storing the results of these subproblems, we can efficiently find the minimum number of coins needed.

Approach

1. Base Cases: - If the amount is 0, return 0 because no coins are needed. - If the amount is negative, return a large number (infinity) to indicate that it's not possible to form this amount.
2. Recursive Function: - Define a recursive function dfs(remaining) that returns the minimum number of coins needed for the given remaining amount. - If remaining is already computed (exists in the memoization map dp), return the stored result to avoid redundant calculations. - For each coin in the given set of coins, recursively calculate the minimum number of coins needed for remaining - coin. - Keep track of the minimum number of coins needed among all possible coin choices.
3. Memoization: - Use a map (or array) to store the results of subproblems (i.e., minimum number of coins needed for each amount). - This helps to avoid recalculating results for the same amount multiple times, thus optimizing the solution.
4. Final Result: - Start the recursive function with the target amount. - If the result is still a large number (infinity), return -1 indicating it's not possible to form the target amount with the given coins. - Otherwise, return the result which is the minimum number of coins needed.

Complexity

Time Complexity:

O(amount * n), where amount is the target amount and n is the number of different coin denominations. This is because in the worst case, we need to compute the result for each amount from 1 to the target amount, and for each amount, we check all coin denominations.

Space Complexity:

O(amount), which is the space required for the memoization map (or array) to store the minimum number of coins needed for each amount from 0 to the target amount.

Code

C++

class Solution {
public:
    int coinChange(std::vector& coins, int amount) {
        if (amount == 0) return 0;
        std::unordered_map dp;
        
        int result = dfs(coins, amount, dp);
        return result == INT_MAX ? -1 : result;
    }
private:
    int dfs(std::vector& coins, int remaining, std::unordered_map& dp) {
        if (remaining < 0) return INT_MAX;
        if (remaining == 0) return 0;
        if (dp.find(remaining) != dp.end()) return dp[remaining];

        int minCoins = INT_MAX;
        for (int coin : coins) {
            int res = dfs(coins, remaining - coin, dp);
            if (res != INT_MAX) {
                minCoins = std::min(minCoins, 1 + res);
            }
        }
        dp[remaining] = minCoins;
        return minCoins;
    }
};

Python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        dp = {}

        def dfs(remaining):
            if remaining < 0:
                return float('inf')
            if remaining == 0:
                return 0
            if remaining in dp:
                return dp[remaining]
            
            min_coins = float('inf')
            for coin in coins:
                res = dfs(remaining - coin)
                if res != float('inf'):
                    min_coins = min(min_coins, 1 + res)
            
            dp[remaining] = min_coins
            return dp[remaining]

        result = dfs(amount)
        return -1 if result == float('inf') else result

Java

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        Map dp = new HashMap<>();
        
        int result = dfs(coins, amount, dp);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int dfs(int[] coins, int remaining, Map dp) {
        if (remaining < 0) return Integer.MAX_VALUE;
        if (remaining == 0) return 0;
        if (dp.containsKey(remaining)) return dp.get(remaining);

        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = dfs(coins, remaining - coin, dp);
            if (res != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, 1 + res);
            }
        }
        dp.put(remaining, minCoins);
        return minCoins;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(solution.coinChange(coins, amount)); // Output: 3
    }
}

JavaScript

var coinChange = function(coins, amount) {
    if(amount === 0) return 0
    dp = {}
    function dfs(total){
        if(total > amount){
            return Infinity
        }
        if(total === amount) return 0;
        if(dp[total]){
            return dp[total]
        }
        let temp = Infinity     
        for(let i =0; i