Pemrograman dinamis

Gambar 1. Menemukan jalur terpendek dalam grafik menggunakan substruktur optimal; garis lurus menunjukkan satu sisi; garis bergelombang menunjukkan jalur terpendek antara dua sudut yang terhubung (di antara jalur lain, tidak ditampilkan, berbagi dua sudut yang sama); garis tebal adalah jalur terpendek keseluruhan dari awal sampai tujuan.

Pemrograman dinamis (bahasa Inggris: dynamic programming) adalah sebuah metode pemecahan masalah yang digunakan dalam ilmu komputer, matematika dan ekonomi. Inti dari metode ini adalah membuat sebuah masalah kompleks menjadi masalah kecil yang lebih sederhana, dan menyelesaikan masalah kecil tersebut. Lalu, menggunakan solusi dari masalah kecil tersebut, seseorang dapat menyelesaikan masalah awal.

Pemrograman dinamis dapat digunakan ketika masalah yang didapatkan agar dapat dipecah lagi menjadi masalah-masalah kecil yang seluruhnya mirip.

Richard Bellman, seorang matematikawan Amerika Serikat menggunakan istilah ini pada tahun 1940-an, ketika dia ingin menyelesaikan sebuah masalah di bidang teori kontrol. Dia juga menyatakan Bellman's Principle of Optimality:

apapun keadaan awal dan keputusan awal, keputusan optimum selanjutnya membentuk kebijakan optimum dengan memperhatikan keadaan yang dihasilkan oleh keputusan awal.

— Bellman, 1957

Referensi

• "On the Theory of Dynamic Programming". PubMed Central (PMC) (dalam bahasa Inggris). Diakses tanggal 25 September 2016.