Apa itu "dinamis" tentang pemrograman dinamis?

Salah satu senior saya memiliki wawancara kerja dan dia ditanya mengapa itu disebut dinamis. Dia tidak bisa menjawab dan setelah dia menyerah pewawancara mengatakan bahwa tidak ada yang dinamis tentang hal itu, itu hanya disebut seperti itu. Sulit bagi saya untuk percaya.

Apakah ini merujuk pada fakta bahwa subproblem diselesaikan pada saat run-time dan digunakan dalam mencapai tujuan akhir? Suka alokasi memori dinamis yang terjadi saat run-time?

[MENJAWAB]

Saya harus memiliki membaca ini artikel wiki sebelum mengajukan pertanyaan, maaf.

Saya selalu intuisi bahwa itu berarti bahwa algoritma yang menggunakan pemrograman dinamis tampaknya mengedit ruang masalah " secara dinamis " sampai masalah dapat diselesaikan dengan algoritma serakah.

Misalnya, dengan masalah Kotak-kotak , algoritma pemrograman dinamis mengedit seluruh papan saat melewatinya, dan akhirnya, algoritma serakah dapat digunakan (sama, dengan algoritma jalur terpendek Dijkstra, dll.).

Saya tidak yakin apakah ini digeneralisasi untuk setiap masalah pemrograman dinamis.

Sebenarnya, tidak ada yang istimewa dalam nama "pemrograman dinamis"; teknik itu sendiri hanya tentang perulangan cerdik. Lihat pertanyaan ini dan lihat jawaban @Jeffe, di mana dilaporkan bahwa Belman memilih nama itu untuk sengaja dikacaukan.

Ada cerita yang menarik di sini .. Bellman memelopori paradigma ini. Tapi, ini sebenarnya penelitian matematika. Kembali pada zamannya, menteri pertahanan saat itu paranoid dari kata-kata Research and Math (orang gila, benar!). Bellman takut bahwa secretart akan marah pada pekerjaannya dan akhirnya akan membuatnya kesulitan. Jadi untuk mengaburkan hal-hal sedikit, ia menyebutnya Pemrograman Dinamis , namun tidak ada yang 'dinamis' tentang hal itu ..

Richard Bellman menyebutnya Pemrograman Dinamis dalam kata-kata dalam Bellman

Saya menghabiskan kuartal Musim Gugur (1950) di RAND. Tugas pertama saya adalah menemukan nama untuk proses pengambilan keputusan multistage.

Pertanyaan yang menarik adalah, Dari mana nama, pemrograman dinamis, berasal? Tahun 1950 bukanlah tahun yang baik untuk penelitian matematika. Kami memiliki seorang pria yang sangat menarik di Washington bernama Wilson. Dia adalah Sekretaris Pertahanan, dan dia benar-benar memiliki ketakutan dan kebencian patologis terhadap kata riset. Saya tidak menggunakan istilah ini dengan ringan; Saya menggunakannya dengan tepat. Wajahnya akan suffuse, dia akan memerah, dan dia akan menjadi kejam jika orang menggunakan istilah penelitian di hadapannya. Anda dapat membayangkan bagaimana perasaannya, kemudian, tentang istilah, matematika. RAND Corporation dipekerjakan oleh Angkatan Udara, dan Angkatan Udara memiliki Wilson sebagai bosnya, pada dasarnya. Karena itu, saya merasa harus melakukan sesuatu untuk melindungi Wilson dan Angkatan Udara dari kenyataan bahwa saya benar-benar mengerjakan matematika di dalam RAND Corporation. Judul apa, nama apa, dapatkah saya memilih? Pertama-tama saya tertarik dalam perencanaan, pengambilan keputusan, dan pemikiran. Tetapi perencanaan, bukan kata yang baik karena berbagai alasan. Karena itu saya memutuskan untuk menggunakan kata, "pemrograman". Saya ingin menyampaikan ide bahwa ini dinamis, ini multistage, ini bervariasi waktu. Saya pikir, mari kita bunuh dua burung dengan satu batu. Mari kita ambil sebuah kata yang memiliki makna yang sangat tepat, yaitu dinamis, dalam pengertian fisik klasik. Ia juga memiliki sifat yang sangat menarik sebagai kata sifat, dan tidak mungkin menggunakan kata dynamic dalam arti merendahkan. Coba pikirkan beberapa kombinasi yang mungkin akan memberinya makna merendahkan. Tidak mungkin. Jadi, saya pikir pemrograman dinamis adalah nama yang bagus. Itu adalah sesuatu yang bahkan tidak bisa ditolak oleh anggota Kongres.

Sumber: Eye of the Hurricane, Richard Bellman (Autobiografi)