LeetCode: Coin Change

LeetCode Challenge

You are given coins of different denominations and a total amount of money amount.

Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Backtracking Solution

This is a classic problem with a backtracking solution. We can recursively try to solve a smaller problem. If we want to know how many coins need for 100, we subtract a coin with a denomination of 5, we get a similar problem with 95 as the target amount.

The code for recursive solution is like this:

class Solution {
public:
    int res = INT_MAX;

    int coinChange(vector<int>& coins, int amount) {
        if(amount < 0 || coins.size() == 0)
          return -1;
        findWay(coins, amount, 0);
        return res  == INT_MAX ? (-1) : res;
    }

    void findWay(vector<int>& coins, int amount, int count) {
        if(amount == 0) res = min(res, count);
        if(amount < 0) return;
        for(int i=0; i<coins.size(); i++) {
            findWay(coins, amount - coins[i], count+1);
        }
    }
};

Optimization with memorization

In the backtracking solution, there is a lot of repeated computation. We can see from the below diagram, the sub-problem of 9, 8,7 are all computed more than two times.

An optimization is removing these duplicated computations. The general algorithm design guide for this kind of problem is search memorized optimization, and use a HashMap(or an array) to save the results of sub-problem and reducing unnecessary recursion.

class Solution {
public:
    int res = INT_MAX;
    std::unordered_map<int, int> dict;
    
    int coinChange(vector<int>& coins, int amount) {
        if(amount < 0 || coins.size() == 0)
          return -1;
        return findWay(coins, amount);
    }

    int findWay(vector<int>& coins, int amount) {
        if(amount == 0) return 0;
        if(amount < 0) return -1;

        std::unordered_map<int, int>::iterator it = dict.find(amount);
        if(it != dict.end()) 
            return it->second;

        int min_count = INT_MAX;
        for(int i=0; i<coins.size(); i++) {
            int left_count = findWay(coins, amount - coins[i]);
            if(left_count >= 0)
                min_count = min(left_count + 1, min_count);
        }
        dict[amount] = min_count == INT_MAX ? (-1) : min_count;
        return dict[amount];
    }
};

Dynamic programming: bottom-up

The above solution is a strategy of top-bottom. We can also use a bottom-up approach to think about it. We define F(i) as the minimum number of coins required to form the amount i, assuming we have already known the value of F(0), F(1) ... F(i-1), then the value of F(i) should be the minimum value of F(i-coin_j), where j start from 0 to i-1.

The time complexity is $O(Sn)$, where S is the target amount, and n is the number of different kinds of coins.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

Join my Email List for more insights, It's Free!😋

Tags: LeetCode Backtracking DP

← LeetCode: Max Consecutive Ones III Top 5 Books for Python Programming →