Belon Meletup: DP Selang Songsang

Diberikan n belon dengan nilai nums, meletupkan belon i memperoleh nums[i-1] * nums[i] * nums[i+1] syiling (hasil darab belon itu sendiri dengan jiran semasanya). Selepas belon itu meletup, jiran-jirannya menjadi bersebelahan. Cari jumlah maksimum syiling yang boleh dikumpulkan dengan meletupkan semua belon. Simulasi naif sukar kerana tindakan meletup mengubah jiran — DP selang songsang mengatasi kesukaran ini dengan berkesan.

Jika kita cuba mentakrifkan dp[i][j] sebagai syiling maksimum daripada meletupkan belon dalam julat [i, j] dan memikirkan belon yang perlu diletupkan dahulu, kita menghadapi masalah: meletupkan belon k dahulu bermakna nums[k-1] dan nums[k+1] mestilah jiran semasa — tetapi belon-belon itu mungkin diletupkan kemudian, lalu mengubah jiran secara dinamik. Keadaan ini sukar ditakrifkan dengan kemas dalam arah ke hadapan.

Helahnya ialah memikirkan belon yang menjadi belon terakhir untuk diletupkan dalam selang [i, j]. Apabila belon k ialah belon terakhir yang diletupkan dalam [i, j], semua belon lain dalam [i, j] sudah tiada. Jadi jiran belon k tepat-tepat ialah nums[i-1] dan nums[j+1] — belon sempadan yang berada di luar selang. Hal ini menjadikan pengiraan syiling bagi letupan terakhir tentu: pengiraan itu tidak bergantung pada susunan letupan terdahulu.

Tambahkan belon penanda: tambahkan 1 pada awal dan akhir nums untuk membentuk nums = [1] + nums + [1]. Takrifkan dp[i][j] sebagai syiling maksimum daripada meletupkan semua belon yang terletak tepat di antara indeks i dan j (tidak termasuk kedua-duanya), dengan nums[i] dan nums[j] sebagai belon sempadan yang masih kekal. Hubungan rekursi: bagi setiap calon belon terakhir k dalam (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Kita menambah belon penanda pada tatasusunan, memulakan jadual DP dengan sifar (selang kosong = 0 syiling), dan mengisinya mengikut panjang selang yang semakin meningkat. Jawapan akhir ialah dp[0][n+1], yang mewakili syiling maksimum daripada meletupkan semua belon asal dengan belon penanda sebagai sempadan kekal.

Bagi [3, 1, 5, 8], selepas ditambah belon penanda menjadi [1, 3, 1, 5, 8, 1] (indeks 0 hingga 5). Kita mahu dp[0][5]. Bagi selang panjang=2 (satu belon di dalamnya): dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40. Dengan membina secara berperingkat, pilihan optimum ialah meletupkan 1 terakhir antara {3,1,5,8} selepas meletupkan jiran-jirannya terlebih dahulu, menghasilkan jumlah 167 syiling.

Terdapat O(n²) selang dan bagi setiap selang kita mencuba O(n) titik pemisahan, lalu menghasilkan kerumitan masa O(n³). Ruang ialah O(n²) untuk jadual DP. Bagi n = 500 belon, ini bersamaan dengan 125 juta operasi — masih munasabah untuk kekangan temu duga. Penambahan belon penanda pada kedua-dua hujung memudahkan pengendalian sempadan: tanpanya, anda perlu membuat semakan khusus untuk menentukan sama ada i-1 dan j+1 berada dalam sempadan.

Penyelesaian yang sama boleh ditulis secara atas ke bawah dengan @lru_cache, yang mungkin lebih mudah diterbitkan semasa temu duga. Takrifkan solve(i, j) sebagai syiling maksimum dalam selang terbuka (i, j). Fungsi ini mencuba semua k sebagai belon terakhir yang diletupkan dan menyimpan hasilnya secara memoisasi. Kedua-dua pendekatan mempunyai kerumitan masa dan ruang yang sama.

Satu kesilapan biasa ialah mentakrifkan dp[i][j] sebagai syiling apabila belon pertama dalam [i,j] diletupkan, bukannya belon terakhir. Pendekatan ini gagal kerana pengiraan syiling bagi letupan pertama bergantung pada belon jiran yang belum diletupkan — dan keadaan jiran tersebut berubah apabila algoritma berjalan. Sentiasa fikirkan elemen terakhir dalam DP selang apabila sempadan bergantung pada elemen yang masih ada.

Penanda bernilai 1 dipilih kerana bertindak sebagai unsur neutral bagi pendaraban. Apabila belon sempadan menjadi belon terakhir yang diletupkan, nilai syilingnya ialah boundary * last * boundary = 1 * last * 1 = last. Menggunakan 0 akan memberikan 0 syiling (salah), manakala nilai lain akan memesongkan pengiraan. Helah penanda menyatukan semua kes sempadan dengan kemas tanpa memerlukan pengendalian khusus untuk belon paling kiri dan paling kanan.

Dalam DP selang standard (pendaraban rantaian matriks), titik pemisahan k mewakili tempat kita membahagikan masalah kepada dua submasalah yang diselesaikan secara bebas. Dalam Masalah Belon Meletup, k ialah belon yang diletupkan terakhir dalam selang, lalu menjadikan dua subselang [i,k] dan [k,j] tidak bersandar antara satu sama lain apabila k masih wujud sebagai sempadan. Perspektif songsang ini ialah idea kreatif yang menjadikan masalah belon meletup boleh diselesaikan dengan DP selang.

Dalam pelajaran ini, anda telah mempelajari: simulasi ke hadapan gagal kerana pemecahan belon mengubah jiran secara tidak dapat diramalkan, pemerhatian songsang mentakrifkan k sebagai belon terakhir yang dipecahkan dalam suatu selang, menjadikan jiran sebagai nums[i] dan nums[j], dan hubungan dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) dengan penambahan nilai penanda memberikan penyelesaian O(n³). Seterusnya, kita beralih kepada DP beg galas, bermula dengan beg galas 0/1 klasik dan pengoptimuman ruangnya.