Dalam tutorial ini, Anda akan mempelajari apa itu pemrograman dinamis. Juga, Anda akan menemukan perbandingan antara pemrograman dinamis dan algoritma rakus untuk menyelesaikan masalah.
Pemrograman Dinamis adalah teknik dalam pemrograman komputer yang membantu memecahkan kelas masalah secara efisien yang memiliki subproblem yang tumpang tindih dan properti substruktur yang optimal.
Masalah seperti itu melibatkan penghitungan berulang kali nilai sub masalah yang sama untuk menemukan solusi optimal.
Contoh Pemrograman Dinamis
Ambil contoh menghasilkan urutan fibonacci.
Jika urutannya adalah F (1) F (2) F (3)… F (50), maka mengikuti aturan F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Perhatikan bagaimana ada subproblem yang tumpang tindih, kita perlu menghitung F (48) untuk menghitung F (50) dan F (49). Ini persis seperti jenis algoritma di mana Pemrograman Dinamis bersinar.
Bagaimana Pemrograman Dinamis Bekerja
Pemrograman dinamis bekerja dengan menyimpan hasil subproblem sehingga ketika solusinya diperlukan, mereka sudah dekat dan kita tidak perlu menghitung ulang.
Teknik menyimpan nilai subproblem ini disebut memoization. Dengan menyimpan nilai dalam larik, kami menghemat waktu untuk perhitungan sub-masalah yang telah kami temui.
var m = map (0 → 0, 1 → 1) fungsi fib (n) jika kunci n tidak ada di peta mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Pemrograman dinamis dengan memoization adalah pendekatan top-down untuk pemrograman dinamis. Dengan membalikkan arah kerja algoritma yaitu dengan memulai dari kasus dasar dan bekerja menuju solusi, kita juga dapat mengimplementasikan pemrograman dinamis dengan cara bottom-up.
fungsi fib (n) jika n = 0 return 0 else var prevFib = 0, currFib = 1 ulangi n - 1 kali var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Rekursi vs Pemrograman Dinamis
Pemrograman dinamis sebagian besar diterapkan pada algoritma rekursif. Ini bukan kebetulan, sebagian besar masalah pengoptimalan memerlukan rekursi dan pemrograman dinamis digunakan untuk pengoptimalan.
Tetapi tidak semua masalah yang menggunakan rekursi dapat menggunakan Pemrograman Dinamis. Kecuali ada subproblem yang tumpang tindih seperti pada masalah urutan fibonacci, rekursi hanya dapat mencapai solusi menggunakan pendekatan divide and conquer.
Itulah alasan mengapa algoritme rekursif seperti Merge Sort tidak dapat menggunakan Pemrograman Dinamis, karena subproblem tidak tumpang tindih dengan cara apa pun.
Algoritma Greedy vs Pemrograman Dinamis
Algoritma Greedy mirip dengan pemrograman dinamis dalam arti keduanya adalah alat untuk pengoptimalan.
Namun, algoritma serakah mencari solusi optimal secara lokal atau dengan kata lain, pilihan serakah, dengan harapan menemukan optimal global. Karenanya algoritme rakus dapat membuat tebakan yang terlihat optimal pada saat itu tetapi menjadi mahal di masa mendatang dan tidak menjamin optimal secara global.
Pemrograman dinamis, di sisi lain, menemukan solusi optimal untuk sub-masalah dan kemudian membuat pilihan yang tepat untuk menggabungkan hasil dari sub-masalah tersebut untuk menemukan solusi yang paling optimal.
