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

Pranala luar

• Sebuah Tutorial tentang Pemrograman Dinamis
• MIT course on algorithms – Termasuk video kuliah tentang DP bersama dengan catatan kuliah, lihat lecture 15.
• Lebih banyak Catatan DP
• King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." Pengantar pemrograman dinamis sebagai alat penting dalam teori ekonomi.
• Dynamic Programming: from novice to advanced sebuah artikel TopCoder.com oleh Dumitru tentang Pemrograman Dinamis
• Algebraic Dynamic Programming – kerangka kerja formal untuk pemrograman dinamis, termasuk kursus tingkat awal kepada DP, University of Bielefeld
• Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming."
• Tutorial pemrograman dinamis
• Pengantar Lembut tentang Pemrograman Dinamis dan Algoritma Viterbi
• Prolog Tabel BProlog dan XSB
• IFORS online interactive dynamic programming modulestermasuk, jalur terpendek, penjual keliling, ransel, koin palsu, menjatuhkan telur, jembatan dan obor, penggantian, produk matriks yang dirantai, dan masalah jalur kritis.