Leetcode solution 322: Coin Change

包子小道消息@12/14/2019

亚马逊的Alexa已经五岁了，经历了野蛮生长之后，Alexa准备开始变现了，包括subscribtion fee for premium content，skills收费，和spotify合作等等。保护好我的钱包呀

Leetcode solution 322: coin change

Blogger:https://blog.baozitraining.org/2019/12/leetcode-solution-322-coin-change.html

Youtube: https://youtu.be/8DXh60kNZmQ

博客园: https://www.cnblogs.com/baozitraining/p/12004581.html

B站: https://www.bilibili.com/video/av78467381/

Problem Statement

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. Example 1:

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

Example 2:

Input: coins = [2], amount = 3
Output: -1

Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

This is a classic problem and greedy might be the first thing comes into mind. For example, sort the coins on denomination and always use the largest amount coin. However, the optimal solution might not include the largest denomination.

for example , [1, 3, 4] and target value 6. The optimal is two 3s, not [4, 1, 1].

It seems we have to list out all the different combinations and find the min value, that leads to a brute fore solution as described here using recursion. It would be an exponential time complexity.

We can use a hash map as a lookup to remember for each amount, what would be the min cost. That would significantly reduce the time complexity from exponential to O(S*N) where S is the amount and N is the coins array size. It's not obvious why but once you see the DP solution, you can understand better, it's the same time complexity.

Another way is to use dynamic programming because the problem is asking for a single yes/no, extreme value(min, max), building up a lookup table using formula is the coding pattern. We have similar problems, Wild Card Matching, Regular Expression Matching

The idea is to build a lookup table for each amount, what's the minimal number of coins needed given current denomination.

lookup[i] = min(lookup[i], lookup[i - coin value] + 1) given i - coin value >= 0

Solutions

Dynamic Programming

 1 public int coinChangeDP(int[] coins, int amount) {
 2     if (coins == null || coins.length == 0) {
 3         return -1;
 4     }
 5     // lookup contains the min number of coins needed to reach the amount(i.e., index)
 6     int[] lookup = new int[amount + 1];
 7     lookup[0] = 0;
 8 
 9     for (int i = 1; i <= amount; i++) {
10         int min = Integer.MAX_VALUE;
11         for (int coin : coins) {
12             if (i >= coin && lookup[i - coin] != -1) {
13                 min = Math.min(min, lookup[i - coin] + 1);
14             }
15         }
16         lookup[i] = (min == Integer.MAX_VALUE ? -1 : min);
17     }
18 
19     return lookup[amount];
20 }

Time Complexity: O(S*N) where S is the amount and N is the coins array size

Space Complexity: O(N) since we used a lookup array

References

• Leetcode official solution (download pdf)