← Quiz: 1D Dynamic Programming Patterns: all 10 questions
Quiz: 1D Dynamic Programming Patterns · Question 4 of 10
With coins {1, 3, 4} and amount 6, what does greedy (largest coin first) give, and what is optimal?
With coins {1, 3, 4} and amount 6, what does greedy (largest coin first) give, and what is optimal?
- A.Greedy 2 coins, optimal 2 coins
- B.Greedy 3 coins, optimal 3 coins
- C.Greedy 3 coins (4 + 1 + 1), optimal 2 coins (3 + 3)
- D.Greedy 2 coins, optimal 3 coins
Answer & explanation
Correct answer: Greedy 3 coins (4 + 1 + 1), optimal 2 coins (3 + 3)
Greedy is not safe for every coin system; DP tries every last coin.
Can you get the rest right without peeking?
Take the timed Quiz: 1D Dynamic Programming Patterns quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →