Problem 🤔

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 1

Input: coins = [1,2,5], amount = 11

Output: 3

Explanation

11 = 5 + 5 + 1

Example 2

Input: coins = [2], amount = 3

Output: -1

Example 3

Input: coins = [1], amount = 0

Output: 0

Example 4

Input: coins = [1], amount = 1

Output: 1

Example 5

Input: coins = [1], amount = 2

Output: 2

Note

• Let’s denote S as the amount Let’s denote N as length of the coins list.

Constraints

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

Real World Applications 🌎

Before we jump into the dynamic programming solution, let’s get a bit imaginative. I know we’re talking about coins here - but take a moment.. can you imagine this as a graph problem?

The Finer Details 🔎

Let’s start with modelling this as a graph. Each path on the graph can represent the coins we selected. To get the sum at any given point we’d only need to keep track and sum all the vertexes we’ve seen until that point.

Vertices

Each vertex can hold a value of coin. The graph in theory would be endless! Because we can use each coin as many times as we want (no constraints here). But we don’t actually need to initialize an infinite graph.

We can just hop to “new vertexes” on the go :) In most cases, it won’t even be that many hops — because one we reach or surpass the amount we can end our travesal.

Edges

Edges will exist between each coin for every vertex (since we’re not limited in usage per coin).

Recursive Brute Force Solution 💡

This is a brute force solution with a small optimization. We check all possible denominations. I think we can do better!

Optimized Dynamic Programming Solution 💡

This problem can be extrapolated and used as a very common template for solving dynamic programming questions! Why so? Dyanmic Programming questions are often aimed at maximizing / minimizing certain values. This is exactly what we’re doing here! If we want to save computing the combos every single time we’ll need to cache our caclculations. But which calculations exactly? There are a few ways to go about this but I think caching the coins needed to get to target k, such that 1 <= k <= n is very intuitive.

So, how does this look in practice? Our dp cache can be a list of size amount. We can do a bottom-up approach to caclulcate dp[amount].

Complexity Analysis 🧮

Time Complexity

O(S * N)

Two nested for loops of those lengths.

Space Complexity

O(S)

Aux list of size S (which is our given amount).

Takeaways 🎉🥳

This is a classic DP problem! DP often deals with recursive problems where the optimized solution is based on optimizing smaller subproblems. Because of this, I recommend you review this and internalize it. This pattern can be applied for many other DP problems!

Resources 📚

Leetcode