E
Euroken@euroken
Coin Change is usually the first problem where dynamic programming is the intended answer, and where a greedy approach looks right but is not.
Two questions for anyone who has solved it:
- What told you greedy would fail? A small counter-example is the most convincing thing to share.
- When you see a new problem, what are your signs that it might be DP? Mine are: it asks for a minimum, maximum or count, and the same smaller subproblem seems to come up more than once.
If you are stuck rather than done, say where. Is it defining the subproblem, or filling in the table?