Burst Balloons: DP Interval Terbalik

Diberikan n balon dengan nilai nums, meletuskan balon i menghasilkan nums[i-1] * nums[i] * nums[i+1] koin (hasil kali balon itu sendiri dan tetangganya saat ini). Setelah balon tersebut meletus, tetangganya menjadi bersebelahan. Temukan jumlah koin maksimum yang dapat Anda kumpulkan dengan meletuskan semua balon. Simulasi naif sulit dilakukan karena tetangga berubah saat balon meletus — DP interval terbalik mengatasi kesulitan ini dengan elegan.

Jika kita mencoba mendefinisikan dp[i][j] sebagai jumlah koin maksimum dari meletuskan balon dalam rentang [i, j] dan memikirkan balon mana yang harus diletuskan terlebih dahulu, kita menghadapi masalah: meletuskan balon k terlebih dahulu berarti nums[k-1] dan nums[k+1] harus menjadi tetangga saat ini — tetapi balon-balon tersebut mungkin baru diletuskan kemudian, sehingga tetangganya berubah secara dinamis. Keadaan ini sulit didefinisikan dengan rapi dalam arah maju.

Caranya adalah memikirkan balon mana yang menjadi yang terakhir meletus dalam rentang [i, j]. Ketika balon k menjadi balon terakhir yang meletus dalam [i, j], semua balon lain dalam [i, j] sudah tidak ada. Jadi, tetangga balon k tepatnya adalah nums[i-1] dan nums[j+1] — balon batas yang berada tepat di luar rentang. Hal ini membuat perhitungan koin untuk letusan terakhir menjadi deterministik: perhitungan tersebut tidak bergantung pada urutan letusan sebelumnya.

Tambahkan balon sentinel: tambahkan awalan dan akhiran 1 ke nums untuk membentuk nums = [1] + nums + [1]. Definisikan dp[i][j] sebagai jumlah koin maksimum dari meletuskan semua balon yang berada tepat di antara indeks i dan j (keduanya tidak termasuk), dengan nums[i] dan nums[j] sebagai balon batas yang tetap ada. Relasi rekurensi: untuk setiap balon kandidat terakhir k dalam (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Kita menambahkan padding sentinel pada larik, menginisialisasi tabel DP dengan nol (rentang kosong = 0 koin), lalu mengisinya berdasarkan panjang rentang yang meningkat. Jawaban akhirnya adalah dp[0][n+1], yang merepresentasikan jumlah koin maksimum dari meletuskan semua balon asli dengan sentinel sebagai batas permanen.

Untuk [3, 1, 5, 8], setelah diberi padding menjadi [1, 3, 1, 5, 8, 1] (indeks 0-5). Kita ingin menghitung dp[0][5]. Untuk rentang dengan panjang=2 (satu balon 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 membangun hasil secara bertahap, strategi optimal adalah meletuskan 1 terakhir di antara {3,1,5,8} setelah meletuskan tetangganya terlebih dahulu, sehingga menghasilkan total 167 koin.

Terdapat O(n²) rentang dan untuk setiap rentang kita mencoba O(n) titik pemisahan, sehingga menghasilkan kompleksitas waktu O(n³). Ruang yang digunakan adalah O(n²) untuk tabel DP. Untuk n = 500 balon, jumlahnya adalah 125 juta operasi — masih layak untuk batasan soal wawancara. Padding sentinel menyederhanakan penanganan batas: tanpanya, Anda perlu memeriksa secara eksplisit apakah i-1 dan j+1 berada dalam batas.

Solusi yang sama dapat ditulis dari atas ke bawah menggunakan @lru_cache, yang mungkin lebih intuitif untuk diturunkan selama wawancara. Definisikan solve(i, j) sebagai jumlah koin maksimum dalam rentang terbuka (i, j). Fungsi tersebut mencoba semua k sebagai letusan terakhir dan menyimpan hasilnya dalam memo. Kedua pendekatan memiliki kompleksitas waktu dan ruang yang sama.

Kesalahan umum adalah mendefinisikan dp[i][j] sebagai jumlah koin ketika balon pertama dalam [i,j] diletuskan, bukan balon terakhir. Cara ini gagal karena perhitungan koin untuk letusan pertama bergantung pada balon tetangga yang belum diletuskan — dan keadaan tetangga tersebut berubah seiring algoritma berjalan. Dalam DP interval, selalu pikirkan elemen terakhir ketika batas bergantung pada elemen yang tersisa.

Sentinel bernilai 1 dipilih karena berfungsi sebagai elemen netral untuk perkalian. Ketika balon batas menjadi balon terakhir yang meletus, nilai koinnya adalah boundary * last * boundary = 1 * last * 1 = last. Penggunaan 0 akan menghasilkan 0 koin (salah), sedangkan penggunaan nilai lain akan mengubah hasil perhitungan. Trik sentinel menyatukan semua kasus batas dengan rapi tanpa perlu menangani balon paling kiri dan paling kanan secara khusus.

Dalam DP interval standar (rantai matriks), titik pemisahan k menunjukkan tempat kita membagi masalah menjadi dua submasalah yang diselesaikan secara independen. Dalam masalah Balon Meletus, k adalah balon yang terakhir meletus dalam rentang tersebut, sehingga dua subrentang [i,k] dan [k,j] menjadi independen dengan syarat k masih ada sebagai batas. Perspektif terbalik ini merupakan wawasan kreatif yang membuat masalah balon meletus dapat diselesaikan dengan DP interval.

Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Dalam pelajaran ini Anda mempelajari: simulasi maju gagal karena memecahkan balon mengubah balon tetangga secara tak terduga, gagasan dari arah terbalik mendefinisikan k sebagai balon terakhir yang dipecahkan dalam suatu rentang, sehingga tetangganya menjadi nums[i] dan nums[j], dan relasi rekurensi dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) dengan pengisian menggunakan penanda menghasilkan solusi O(n³). Berikutnya, kita beralih ke DP ransel, dimulai dengan ransel 0/1 klasik dan optimasi ruangnya.