Penukaran Koin

Diberikan pecahan koin coins (jumlah tiap pecahan tak terbatas) dan total amount. Kembalikan jumlah koin minimum untuk membentuk amount, atau -1 jika tidak mungkin.

coins = [1, 2, 5], amount = 11 → 3   // 5 + 5 + 1
coins = [2],       amount = 3  → -1

Perhatikan bahwa greedy tidak selalu optimal: untuk koin [1, 3, 4] dan total 6, greedy memberi 4+1+1 (3 koin), padahal 3+3 hanya 2 koin.