Intermediate LevelData Structures & Algorithms
How do you solve the Coin Change problem with Dynamic Programming?
ā Interview Prompt: Solve Coin Change (minimum coins for target amount) using bottom-up DP, identifying the recurrence relation and state transitions.
Problem: Given coin denominations and a target amount, find the minimum number of coins to reach the target.
DP Formulation:
ā¢
State:
dp[i] = minimum coins needed to make amount i.ā¢
Base case:
dp[0] = 0.ā¢
Recurrence:
dp[i] = 1 + min(dp[i - coin]) for each coin ā¤ i.ā¢
Time: $O(\text{amount} \times \text{coins})$, Space: $O(\text{amount})$.
Code Implementation Example
typescript
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i && dp[i - coin] !== Infinity) {
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 5, 6, 9], 11)); // 2 (5+6)
console.log(coinChange([2], 3)); // -1š”Coin Change bottom-up DP with recurrence dp[i] = 1 + min(dp[i-coin]).
šÆ Interview Key Takeaway
Coin Change is the archetypal unbounded knapsack DP. The recurrence dp[i] = 1 + min(dp[i - coin]) models "use 1 coin + optimal remaining".
#DSA#Dynamic Programming#Coin Change#Knapsack#Intermediate
Back to all Data Structures & Algorithms Questionsā