Leetcode — 322. Coin Change

The link to the problem: https://leetcode.com/problems/coin-change/

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.

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

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

Thoughts:

It is important to choose the right strategy to solve the problem. My first thought is to use backtracking and try to find every possible coin combinations. However, the code only passes half of the cases on Leetcode. The time complexity is too high and it is also unnecessary to find all the combinations in this problem.

Then, I try to use dynamic programming to solve the problem. My idea is to use an array to store the minimum numbers of coins needed for each amount. i.e., we will need dp[i] coins for $i.

Code Logic:

The initial value of the dp array should be an impossible number, like -1, Integer.MIN_VALUE, (amount+1), etc. This step is also important since this is how we know whether we can use this data to help our other amount.

There are several amounts in the dp array that will have different initial values before we start our loop.

1. dp[0] is 0 for sure since we need 0 coins to form the amount of $0.
2. All the coins in the given array coins only need 1 coin to form their amount.

While in each iteration in the loop, it means we are going to find if we can use the coins to form the amount i. We will always only pick one coin at a time. If we find that we have found the minimum number of coins needed for “the rest of the amount”, then we will see if this new combination can be our minimum coins needed for the current amount i.

⚠️Before we start anything, we need to first make sure the coins are sorted by increasing order.
Two benefits if we sort them —
1. We can just return -1 if we found the smallest amount of the coin is bigger than the target amount.
2. When we found the current coin amount is larger than the current amount, we can give up finding the coin combinations of the rest of the coins since they are all larger than the current amount. (Like you can’t form an amount of $50 even if you have a lot of $100, $200 coins)

👷Let’s see a simple example if we have coins = [2,3,5].

⚠️In the real process, we will need to find the minimum coins needed in all amounts from 1 to the target amount. Since I just want to show a simple idea here, I will just show how we do it in one iteration.

Assume our current amount is $6, and we have already checked the minimum coins needed for $0~$5.

🔧Step 1. We will first pick a $2 coin. We will see if we have found the number of coins needed for $(6–2) before. Since the minimum coins needed for $4 is 2, so if we first choose $2, we will need 3 coins to form $6.

🔧Step 2. We pick a $3 coin. Since the minimum coins needed for $(6–3) is 1, the current minimum number of coins needed for $6 is 2.

🔧Step 3. We pick a $5 coin. However, we cannot find a way how we form a $1 amount, hence, this combination failed.

🚧And we’re done with this iteration since we have checked all the possible coins.

Below is the 11ms code that beats 87% —

public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        if(amount!=0 && coins[0]>amount)
            return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp,-1);
        dp[0] = 0; 
        for(int coin: coins)
        {
            if(coin>amount)
                break;
            dp[coin] = 1;
        }
        for(int i=1;i<=amount;i++)
        {
            if(dp[i]==1)
                continue;
            int minCount = Integer.MAX_VALUE;
            for(int coin: coins)
            {
                if(coin>i)
                    break;
                if(dp[i-coin]==-1)
                    continue;
                minCount = Math.min(minCount, 1+dp[i-coin]);
            }
            if(minCount == Integer.MAX_VALUE)
                dp[i] = -1;
            else
                dp[i] = minCount;
        }
        return dp[amount];
    }

Time Complexity: O(n); Space Complexity: O(n)