Apa itu pemrograman dinamis?

Pemrograman dinamis (DP) adalah teknik algoritmik yang digunakan untuk menyelesaikan masalah optimisasi dengan memecahnya menjadi submasalah yang lebih sederhana, lalu menggunakan kembali solusi untuk submasalah tersebut guna menyelesaikan masalah awal.

DP sering digunakan untuk masalah yang solusinya dapat dinyatakan secara rekursif dalam bentuk submasalah yang lebih kecil. Teknik ini disebut "dinamis" karena solusi untuk submasalah dapat disimpan dan digunakan kembali untuk menyelesaikan masalah yang lebih besar, sehingga prosesnya lebih efisien daripada menyelesaikan masalah yang lebih besar dari awal.

DP dapat digunakan untuk berbagai masalah, seperti jalur terpendek, subsekuens umum terpanjang, dan subarray maksimum. Teknik ini sangat berguna ketika masalah memiliki submasalah yang tumpang tindih dan struktur optimal, yang berarti solusi optimal untuk masalah tersebut dapat dibentuk dari solusi optimal untuk submasalahnya.