Example - Coin Change (Greedy Fails)

Make change for $6$ cents using coins ($1$, $3$, $4$). Minimize the number of coins. Greedy approach: take $4$ first ($2$ left), then take $1$, take $1$. Total: $3$ coins. But wait: $3$ + $3$ = $6$ using only $2$ coins! Greedy gave the wrong answer.

What went wrong? The coin values are not "canonical." Taking the locally best coin ($4$) blocked the globally best solution ($3$ + $3$). That's exactly when you need DP instead. The $4$ cent coin breaks the canonical property. Taking it first blocks the globally optimal pair. This is why you need to verify greedy choice property before coding.