Pemrograman dinamis
Gambaran > Pemrograman komputer

Ada dua atribut utama yang harus dimiliki masalah agar pemrograman dinamis dapat diterapkan: substruktur yang optimal dan sub-masalah yang tumpang tindih. Jika suatu masalah dapat diselesaikan dengan menggabungkan solusi optimal untuk sub-masalah tidak tumpang tindih, strateginya disebut "divide and conquer". Inilah sebabnya mengapa merge sort dan quick sort tidak diklasifikasikan sebagai masalah pemrograman dinamis.
Substruktur optimal berarti bahwa solusi untuk masalah pengoptimalan yang diberikan dapat diperoleh dengan kombinasi solusi optimal untuk sub-masalahnya. Substruktur optimal seperti itu biasanya dijelaskan melalui rekursi. Misalnya diberi grafik G=(V,E), jalur terpendek p dari sebuah vertex u ke sebuah vertrex v menunjukkan substruktur yang optimal: ambil perantara vertex w di jalur terpendek ini p. Jika p benar-benar merupakan jalur terpendek, kemudian dapat dipecah menjadi sub-jalur p1 dari u ke w dan p2 dari w ke v sedemikian rupa sehingga ini, pada gilirannya, memang merupakan jalur terpendek antara simpul yang sesuai (dengan argumen potong-dan-tempel sederhana yang dijelaskan dalam Introduction to Algorithms). Oleh karena itu, salah satu dapat dengan mudah merumuskan solusi untuk menemukan jalur terpendek secara rekursif, yang dilakukan oleh algoritma Bellman–Ford atau algoritma Floyd–Warshall.
Sub-masalah yang tumpang tindih berarti bahwa ruang sub-masalah harus kecil, yaitu, algoritma rekursif apa pun yang memecahkan masalah harus menyelesaikan sub-masalah yang sama berulang kali, daripada menghasilkan sub-masalah baru. Misalnya, pertimbangkan formulasi rekursif untuk menghasilkan deret Fibonacci: Fi = Fi−1 + Fi−2, dengan kasus dasar F1 = F2 = 1. Lalu F43 = F42 + F41, dan F42 = F41 + F40. Sekarang F41 sedang diselesaikan di sub-pohon rekursif dari keduanya F43 sebaik F42. Meskipun jumlah total sub-masalah sebenarnya kecil (hanya 43 dari mereka), kita akhirnya menyelesaikan masalah yang sama berulang kali jika kita mengadopsi solusi rekursif naif seperti ini. Pemrograman dinamis memperhitungkan fakta ini dan memecahkan setiap sub-masalah hanya sekali.
Ini dapat dicapai dengan salah satu dari dua cara:
Pendekatan top-down: Ini adalah hasil langsung dari formulasi rekursif dari masalah apa pun. Jika solusi untuk masalah apa pun dapat dirumuskan secara rekursif menggunakan solusi untuk sub-masalahnya, dan jika sub-masalah tersebut tumpang tindih, maka seseorang dapat dengan mudah memoisasi atau menyimpan solusi untuk sub-masalah dalam sebuah tabel. Setiap kali kita mencoba untuk memecahkan sub-masalah baru, pertama-tama kita memeriksa tabel untuk melihat apakah sudah terpecahkan. Jika solusi telah dicatat, kita dapat menggunakannya secara langsung, jika tidak kita menyelesaikan sub-masalah dan menambahkan solusinya ke tabel.
Pendekatan bottom-up: Setelah kita merumuskan solusi untuk suatu masalah secara rekursif seperti dalam sub-masalah, kita dapat mencoba merumuskan kembali masalah secara bottom-up: coba selesaikan sub-masalah terlebih dahulu dan gunakan solusi mereka untuk membangun dan sampai pada solusi untuk sub-masalah yang lebih besar. Ini juga biasanya dilakukan dalam bentuk tabel dengan menghasilkan solusi secara berulang untuk sub-masalah yang lebih besar dan lebih besar dengan menggunakan solusi untuk sub-masalah kecil. Misalnya, jika kita sudah mengetahui nilai F41 dan F40, kita bisa langsung menghitung nilai F42.
Beberapa bahasa pemrograman dapat secara otomatis memoisasi hasil panggilan fungsi dengan sekumpulan argumen tertentu, untuk mempercepat evaluasi Call-by-name. (mekanisme ini disebut sebagai call-by-need). Beberapa bahasa membuatnya mungkin portabel (misalnya Scheme, Common Lisp, Perl atau D). Beberapa bahasa memiliki memoisasi otomatis  bawaan, seperti tabel Prolog dan J, yang mendukung memoization dengan kata keterangan M. . Bagaimanapun, ini hanya mungkin untuk fungsi transparansi referensial. Memoisasi juga ditemukan sebagai pola desain yang mudah diakses dalam bahasa berbasis penulisan-ulang istilah seperti Bahasa Wolfram.