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 yang 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, sudah tersedia dan kita tidak perlu menghitung ulang.

Teknik menyimpan nilai subproblem ini disebut memoization. Dengan menyimpan nilai dalam larik, kami menghemat waktu untuk penghitungan sub-masalah yang telah kami temui.

var m = map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] = fib(n − 1) + fib(n − 2)
    return m[n]

Pemrograman dinamis dengan memoization adalah pendekatan top-down untuk pemrograman dinamis. Dengan membalik arah kerja algoritma yaitu dengan memulai dari kasus dasar dan bekerja menuju solusi, kita juga dapat mengimplementasikan pemrograman dinamis dengan cara bottom-up.

function fib(n)
    if n = 0
        return 0
    else
        var prevFib = 0, currFib = 1
        repeat n − 1 times
            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 serakah 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.