Coin Change
- 3 min read
- LC-Medium
- Dynamic Programming
3 years ago
Solution
- Bottom-up DP
- Basically, start with the smallest target possible (i.e. dp[0] and work your way up)
- i.e. for
[1, 3, 4, 5]dp[0]would mean how many coins do we need to get a sum of 0? We need 0dp[1]would be how many coins do we need to get a sum of 1? We need 1 (there's only one coin with value of 1)dp[2] = 1 + dp[1]- 1 from the coin 1
- And
dp[1]is valid since we can use the same coin multiple times
- We see that repeated work (i.e. checking
dp[1]is avoided, even in this case it is not that much of an improvement, you can see that for more complex cases, the dfs tree would be super deep, and with memoization we can avoid all of that) - Gemini 2.5 Flash explanation:
- // We are trying to find the minimum coins for 'amt'.
// If we use the current 'coin':
// The number of coins would be
1 (for the current coin) + dp[amt - coin]//dp[amt - coin]is the minimum coins needed for the remaining amount. // We take the minimum of: // a) The current best known way to make 'amt' (dp[amt]) // b) Using the current 'coin' plus the minimum coins for the remainder (1 + dp[amt - coin])
- // We are trying to find the minimum coins for 'amt'.
// If we use the current 'coin':
// The number of coins would be
- The condition
remaning >= 0is important ->- WE ONLY recur if the sum exactly matches the target (i.e. remaining amount is 0, i.e. we've seen all the coins already)
- if the condition is not true, then our dp would probably just be left as the infinite amount to indicate that yo from this point we can't really add up to your target sum
| Time | Space | Explanation |
|---|---|---|
O(amount * len(coints)) | O(amount) | space is from the dp array |
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let amt = 1; amt <= amount; amt++) {
for (let coin of coins) {
const remaining = amt - coin;
if (remaining >= 0) {
dp[amt] = Math.min(dp[amt], 1 + dp[remaining]);
}
}
}
return dp[amount] === (amount + 1) ? -1 : dp[amount];
};
TLE Solution (Backtracking + DFS)
- The
curNumCoins >= numCoinsis just an early exit condition - the code passes test cases without it - You can also sort the array to potentially prune branches quickly
function coinChange(coins: number[], amount: number): number {
let numCoins = Infinity;
function backtrack(i: number, curNumCoins: number, curSum: number) {
if (i === coins.length || curSum > amount || curNumCoins >= numCoins) {
return;
}
if (curSum === amount) {
numCoins = Math.min(numCoins, curNumCoins);
return;
}
backtrack(i, curNumCoins + 1, curSum + coins[i]);
backtrack(i + 1, curNumCoins, curSum);
}
backtrack(0, 0, 0);
return numCoins === Infinity ? -1 : numCoins;
};