My first Magazine pemrograman-kompetitif-dasar | Page 72

7
Dynamic Programming
Dynamic programming (DP) sejatinya adalah brute force yang dioptimasi. Seperti greedy ,
persoalan yang dapat diselesaikan dengan DP jika persoalan tersebut memiliki subpersoalan.
Perbedaannya, DP tidak melakukan greedy choice , melainkan mencoba seluruh kemungkinan yang
ada. DP ini sendiri merupakan topik yang sangat luas dan memerlukan latihan yang mendalam
agar dapat menguasai topik ini.
7.1
Konsep Dynamic Programming
DP merupakan metode penyelesaian persoalan yang melibatkan pengambilan keputusan
dengan memanfaatkan informasi dari penyelesaian subpersoalan yang sama namun lebih kecil.
Solusi subpersoalan tersebut hanya dihitung satu kali dan disimpan di memori. Sama seperti
greedy , solusi DP dapat bekerja hanya jika solusi optimal dari persoalan dapat ditentukan dari
solusi optimal subpersoalan tersebut.
Terdapat dua cara mengimplementasikan DP:
• Top-down : diimplementasikan secara rekursif sambil mencatat nilai yang sudah ditemukan
(memoisasi).
• Bottom-up : diimplementasikan secara iteratif dengan menghitung mulai dari kasus yang
kecil ke besar.
DP.
Kita akan menggunakan contoh soal Coin Change berikut sebagai sarana mempelajari teknik
Contoh Soal 7.1: Coin Change
Diberikan M jenis koin, masing-masing jenis bernilai a 1 , a 2 , ..., a M rupiah. Asumsikan banyak-
nya koin untuk setiap nominal yang ada tak terbatas. Tentukan banyaknya koin paling sedikit
untuk membayar tepat sebesar N rupiah!
Contoh soal tersebut sudah dibahas pada bab sebelumnya dan dapat dibuktikan bahwa
soal tersebut tidak dapat diselesaikan dengan greedy . Mari kita selesaikan soal tersebut
menggunakan DP.
7.1.1 Top-down
Pendekatan top-down biasa juga disebut memoisasi. Kata memoisasi berasal dari "memo",
yang artinya catatan. Pada top-down , penyelesaian masalah dimulai dari kasus yang besar.
Untuk menyelesaikan kasus yang besar, dibutuhkan solusi dari kasus yang lebih kecil. Karena
62