Corak dalam Pengaturcaraan Dinamik - 2

Penafian: Kaedah yang diterangkan di bawah tidak universal, tetapi ia selalunya boleh menyelesaikan masalah atau membantu anda mendapatkan penyelesaian yang betul.

Jika masalah meminta anda memusnahkan/runtuh/mencantum (atau serupa) secara optimum suatu tatasusunan, maka anda harus cuba menyelesaikannya menggunakan pengaturcaraan dinamik pada subsegmen.

Mari dapatkan dp[l][r] - jawapan optimum untuk subsegmen dengan indeks dari l hingga r. Pengiraan semula dinamik sangat bergantung kepada tugas, tetapi terdapat idea umum berikut:

1) Lihat unsur ekstrem l dan r. Jika ia sepadan atau melengkapi dalam beberapa cara lain, maka kemungkinan besar adalah mungkin untuk mengemas kini nilai dp[l][r] melalui dp[l+1][r-1]. Jika tidak melalui dp[l][r-1] atau dp[l+1[r].

2) Selalunya berlaku bahawa segmen [l;r] tidak boleh diwakili melalui satu binaan. Maka adalah perlu untuk mempertimbangkan semua bahagian yang mungkin bagi subsegmen ini kepada dua bahagian, iaitu, lelaran ke atas elemen k dari l ke r-1 dan pengiraan semula dp[l][r] melalui dp[l][k] dan dp[ k+1][r] . Dalam subsegmen yang lebih kecil, bahagian ini juga telah disusun, oleh itu, sebenarnya, pilihan untuk membahagi subsegmen [l;r] bukan sahaja kepada dua bahagian, tetapi kepada mana-mana nombor daripadanya diambil kira.
 

Penafian: Kaedah yang diterangkan di bawah tidak universal, tetapi ia selalunya boleh menyelesaikan masalah atau membantu anda mendapatkan penyelesaian yang betul.

Jika anda perlu menyemak kewujudan pilih atur dalam masalah, atau mencari bilangan pilih atur yang sepadan, atau sesuatu yang serupa, maka anda harus mempertimbangkan untuk menggunakan pengaturcaraan subset dinamik.

Parameter utama ialah bitmask, yang akan menunjukkan elemen yang telah dimasukkan dalam pilih atur, dan yang tidak. Juga sering diperlukan ialah parameter kedua yang menunjukkan elemen yang terakhir disertakan.

Selalunya pilih atur boleh dilihat dalam konteks laluan dalam graf. Sehubungan itu, mari kita pertimbangkan contoh klasik - masalah laluan Hamiltonian.
Laluan Hamiltonian ialah laluan mudah yang melalui setiap bucu graf tepat sekali. Ia boleh diwakili hanya sebagai pilih atur panjang n, dengan n ialah bilangan bucu. Susunan dalam pilih atur ini akan menunjukkan susunan bucu dalam laluan ini dilalui.

Untuk menyemak kehadiran laluan Hamiltonian dalam graf, mari kita mulakan dinamik dp[mask][last] - adakah terdapat laluan mudah yang memintas bucu yang ditandakan dengan yang dalam bitmask topeng dan berakhir di bucu terakhir.
Nilai awal ialah dp[2ⁱ][i] = benar, selebihnya palsu, yang bermaksud bahawa sentiasa ada laluan kosong bermula pada mana-mana bucu.
Mempunyai nilai true dalam dp[mask][last] kita akan membuat peralihan ke hadapan, dalam erti kata "memperluaskan laluan". Iaitu, kita akan mencari nombor bucu yang ditandakan dengan sifar dalam topeng (kami belum melawatnya dalam perjalanan) dan pada masa yang sama supaya terdapat kelebihan dari akhir ke puncak ini (laluan mesti dilanjutkan dengan tepi sedia ada). Iaitu, kami melakukan dp[mask | 2^k][k] = benar jika dp[mask][last] = benar DAN topeng & 2^k = 0 (bucu k belum lagi dilawati) Dan ada tepi terakhir -> k.
Akhirnya, laluan Hamiltonian wujud jika terdapat nilai sebenar dalam dp untuk parameter bitmask semua-satu dan sebarang bucu terakhir.