Coin Change, a Dynamic Programming problem, by LeetCode
Here it is: https://leetcode.com/problems/coin-change/description/
The idea with DP again is to construct the solution from 0,1,2... all the way to amount. Suppose that you're computing the solution for N. And assume that you have 3 coins C1, C2 and C3 (you can generalize later). To get to N, inevitably you'll have to get to either N-C1, or N-C2 or N-C3. Compute the min out of those, add 1. Keep doing that until you reach amount. That's it! Code is below, cheers, Marcelo.
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 =11Output:3Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins =[2], amount =3Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
Same cues again that this is a DP problem: asking for the fewest number of combinations (not the combinations themselves), exponential in nature if you were to compute all permutations. Now it was not said how large "amount" can be, but assume that it is a reasonable value (say <= 1000000). We can find a solution to this problem in O(amount * len(coins))-time and O(amount)-space using DP.You may assume that you have an infinite number of each kind of coin.
The idea with DP again is to construct the solution from 0,1,2... all the way to amount. Suppose that you're computing the solution for N. And assume that you have 3 coins C1, C2 and C3 (you can generalize later). To get to N, inevitably you'll have to get to either N-C1, or N-C2 or N-C3. Compute the min out of those, add 1. Keep doing that until you reach amount. That's it! Code is below, cheers, Marcelo.
public class Solution
{
public int CoinChange(int[] coins, int amount)
{
//Base
if (amount < 0) return -1;
if (amount == 0) return 0;
//Induction DP
int[] minChange = new int[amount + 1];
for (int i = 1; i <= amount; i++)
{
int min = Int32.MaxValue;
for (int j = 0; j < coins.Length; j++)
if (i - coins[j] >= 0 && minChange[i - coins[j]] != -1 && minChange[i-coins[j]] + 1 < min)
min = minChange[i - coins[j]] + 1;
minChange[i] = (min == Int32.MaxValue) ? -1 : min;
}
return minChange[amount];
}
}
Classics of DP :) My solution is more verbose because it keeps only 2 rows instead of entire matrix in memory, but the idea is the same.
ReplyDeleteclass Solution {
public:
int coinChange(vector& coins, int amount) {
vector> d(2, vector(amount+1, amount+1));
d[0][0] = 0;
bool prev = 0;
bool current = 1;
for (int c = 1; c <= coins.size(); ++c) {
d[current][0] = 0;
for (long a = 1; a <= amount; ++a) {
if (coins[c-1] <= a) {
d[current][a] = min(1 + d[current][a-coins[c-1]], d[prev][a]);
} else {
d[current][a] = d[prev][a];
}
}
prev = !prev;
current = !current;
}
auto min_coins = d[prev][amount];
return min_coins == amount+1 ? -1 : min_coins;
}
};