Bagaimana Anda mengidentifikasi masalah yang cocok untuk pemrograman dinamis?

Saya telah membaca tentang pemrograman dinamis belakangan ini. Ingin mendengar dari seseorang yang mulai dari awal dan sekarang cukup pandai mengidentifikasi dan memecahkan masalah DP. Saya berjuang dalam mengidentifikasi masalah ini sebagai DP dan membingkai solusi singkat.

Saya telah melalui sebagian besar masalah DP pemula dan sumber daya MIT dll

Saya berasal dari latar belakang fisika, dan dengan demikian, banyak matematika. Saya menemukan masalah yang mudah dikenali cocok untuk solusi pemrograman rekursif / dinamis dengan menemukan kesamaan dengan bukti dengan induksi .

Dibuktikan dengan induksi Anda memiliki dua bagian:

• Anda membuktikan bahwa jika sesuatu benar untuk iterasi N, itu juga berlaku untuk iterasi N +1
• Anda membuktikan bahwa itu benar untuk iterasi 1

Dalam pemrograman rekursif / pemrograman dinamis:

• Anda mengidentifikasi kondisi keluar (misalnya, Anda memasang solusi untuk iterasi 1)
• Anda menghitung solusi untuk iterasi N yang diberikan solusi untuk iterasi N-1

Jadi, ketika orang lain menjawab, itu adalah masalah pengalaman dan mengambil petunjuk, tetapi Anda dapat menggunakan kembali keterampilan lain untuk membimbing Anda. Setelah itu, Anda harus selalu memiliki dua bagian yang saya sebutkan: jika tidak, maka tidak akan berfungsi.

Misalnya, untuk menghasilkan semua permutasi dari set:

• kondisi keluar: jika Anda hanya memiliki satu elemen, kembalikan
• rekursi: permutasi dari set item N adalah set permutasi N yang Anda dapatkan dengan memilih setiap elemen dan menggabungkan semua set N-1 dari (banyak) permutasi dari subset yang Anda dapatkan dengan menghapus elemen tersebut.

Sebagian besar masalah pemrograman yang dinamis dapat diselesaikan melalui memoisasi. Memoisasi biasanya lebih intuitif dan lebih mudah dikodekan. Mungkin bermanfaat jika Anda berpikir dalam hal memoisasi alih-alih DP.

Biasanya lebih mudah untuk mengetahui apakah suatu masalah cocok untuk memoisasi (langkah-langkahnya sama dengan jawaban Slivvz , tetapi saya pikir perubahan mentalnya sedikit lebih pendek). Namun, setelah Anda menyelesaikan masalah melalui memoisasi, Anda dapat memeriksa bagaimana cache memo Anda diisi dan kemudian mengisinya secara berurutan, tanpa rekursi ... yang mengubah algoritme Anda menjadi algoritme pemrograman dinamis.

TL; DR; versi: Anda mungkin lebih mudah memahami pemrograman dinamis dalam hal memoisasi.

Lihat juga StackOverflow: Pemrograman dinamis dan memoisasi: pendekatan bottom-up vs top-down .

Pemrograman dinamis secara definitif tentang dua hal:

1. Substruktur Optimal
   Solusi yang lebih besar dapat diperoleh dari solusi yang lebih kecil; pemecahan bukanlah dua arah.

2. Subproblem yang tumpang tindih
   Solusi kecil akan digunakan kembali berkali-kali. Jika submasalah tidak tumpang tindih sama sekali, maka Anda tidak mendapat manfaat dari DP / memoisasi; apa yang Anda miliki adalah membagi dan menaklukkannya .

Pendekatan umum untuk masalah DP adalah:

• Tulis versi rekursif atau berulang yang naif yang berfungsi.

• Perhatikan bahwa fungsinya melakukan pekerjaan yang berlebihan.

• Temukan cara untuk menghindari melakukan pekerjaan yang berlebihan itu, seringkali dengan memoisasi.

Saya tidak pernah menerapkan pemecah pemrograman dinamis tunggal - latar belakang saya adalah matematika / fisika / komputasi numerik, bukan CS - sampai beberapa tahun yang lalu ketika saya mulai melakukan masalah Project Euler . Masalah yang dapat dipecahkan oleh DP di sana (mis. 76 , 158 , 161 , 242, tapi ada banyak lagi) ternyata jenis favorit saya. Anda benar-benar mendapatkan lebih baik dalam bercak ketika itu akan menjadi teknik yang berguna: pada dasarnya mencari hal-hal yang tampaknya dapat diselesaikan dengan semacam pendekatan rekursif, divide-and-conquer di mana juga memungkinkan untuk menjinakkan ledakan jalur yang membutuhkan untuk dieksplorasi dengan mengenali subproblem berulang dan menggunakan kembali hasil yang dihitung sebelumnya; mampu mengidentifikasi vektor keadaan minimal untuk digunakan - dan "sejarah" yang tidak relevan dapat dihapus - adalah langkah penting.