Problem statement
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
Link to problem
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
Solutions
Approach 1: Dynamic Programming
This was a tough one, there’s two approaches in DP, bottom-up and top-down.
I wasted too much time on one approach because even though the concept itself
is pretty easy, coding that proved quite challenging and I resorted to a simple
implementation. I couldn’t wrap my head around using DFS because even though
it was the simplest approach, I failed to implement it. Perhaps I’ll give it a shot
on Sunday.
Anyway, the heart of the problem is knowing how to add up to the amount given, while
starting at 0.
You essentially add one coin whenever you pick a coin and check if that particular coin
that you picked had any previous.. results. Perhaps a pseudocode or an example might be helpful.
Example:coins = [1, 3, 4, 5]
amount = 7
Start with an array that has same amount of entries as amount + 1, with the values amount + 1
In this case, consider dp = [8, 8,...8]
Start at the bottom, so dp[0] = 0
Now start looking at your coins and see what you can cook with them
dp[1] = you pick a coin that does not exceed 1, that's 1 coin
dp[1] = 1
dp[2] = there's no 2 coin so you pick the 1 coin and another 1 coin
dp[2] = 2
dp[3] = there is a threes coin so you pick that one up
dp[3] = 1
dp[4] = there is a fours coin so you pick that one up
dp[4] = 1
Now that our target is 7
we need to find out what dp[7] is, and for that we need to compare all the coins
and check what we found above
Following are some of the outcomes including optimal one:
dp[7] = 1 + dp[7-1] - the 1 denotes value one, so a coin with value one, and now we are left with 6
dp[6] = 2
dp[7] = 3
Is that an optimal one? Perhaps, but lets keep going.
dp[7] = 1 + dp[7-3]
do[4] = 1
dp[7] = 2
Oh neat, we found something better, is there a better one?
dp[7] = 1 + dp[7-4]
dp[3] = 1
dp[7] = 2
Same as above, essentially the same combination
dp[7] = 1 + dp[7-5]
dp[2] = 2
dp[7] = 3
Back to three, so not optimal
And we found our minimum combo, which is (3, 4).
Implementation in Rust
fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
let mut dp = vec![amount + 1; amount as usize + 1];
dp[0] = 0;
for i in 1..(amount + 1) {
for coin in &coins {
if (i - coin) >= 0 {
dp[i as usize] = std::cmp::min(dp[i as usize], dp[(i - coin) as usize] + 1);
}
}
}
if dp[amount as usize] != amount + 1 {
dp[amount as usize]
} else {
-1
}
}
Time Complexity: $O(n\times{m})$
$n = amount$
$m = coins$
Space Complexity: $O(n)$
Runtime on LeetCode: $12$ms