Burst Balloons
Sederet balon diberikan dalam nums, dengan nums[i] sebagai angka pada balon i. Kamu meletuskan semuanya, satu per satu, dalam urutan apa pun. Meletuskan sebuah balon menghasilkan left × nums[i] × right koin, dengan left dan right sebagai angka pada tetangganya saat itu, yaitu balon terdekat di setiap sisi yang masih berada dalam deretan. Tetangga yang tidak ada dihitung sebagai 1. Setelah sebuah balon meletus, kedua tetangganya menjadi bersebelahan. Kembalikan jumlah koin terbanyak yang bisa kamu kumpulkan.
Fungsi
- numsinteger-array
- angka pada balon, dari kiri ke kanan
- Mengembalikaninteger
- jumlah koin terbanyak yang bisa kamu kumpulkan dengan meletuskan setiap balon
Batasan
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- Jawabannya kurang dari 3 × 108, jadi muat dalam bilangan bulat bertanda 32-bit.
Contoh
- Input
- nums = [2, 4, 3]
- Output
- 33
- Penjelasan
- Uraikan 4 untuk 2 × 4 × 3 = 24. Angka 2, yang kini berada di sebelah 3, menghasilkan 1 × 2 × 3 = 6, dan angka 3 menghasilkan 3: totalnya 33.
- Input
- nums = [6, 1, 2, 5]
- Output
- 108
- Penjelasan
- Kalikan 1 (6 × 1 × 2 = 12), lalu 2, yang sekarang berada di antara 6 dan 5 (6 × 2 × 5 = 60), lalu 5 untuk mendapatkan 30 dan 6 untuk mendapatkan 6: totalnya 108.
- Input
- nums = [8]
- Output
- 8
- Penjelasan
- Balon satu-satunya tidak memiliki tetangga, dan setiap tetangga yang tidak ada dihitung sebagai 1, jadi balon itu mendapat 1 × 8 × 1 = 8.
Pertanyaan lanjutan
Bisakah kamu juga mengembalikan satu urutan bursting yang menghasilkan koin terbanyak?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Misalkan kamu menentukan balon mana yang akan dipecahkan terlebih dahulu. Dua balon tetangganya menjadi bersebelahan, sehingga balon di sebelah kiri dan balon di sebelah kanan tetap saling memengaruhi. Bisakah kamu membagi masalah ini menjadi dua masalah yang lebih kecil dengan cara itu?
Balikkan pertanyaannya dan pilih balon yang meletus terakhir dalam suatu rentang. Sampai saat itu, balon tersebut tetap diam seperti dinding, sehingga balon di sebelah kiri dan kanannya tidak pernah menjadi tetangga. Saat balon itu akhirnya meletus, tetangganya adalah dua balon yang berbatasan dengan rentang tersebut.
Tambahkan 1 di kedua ujung
nums. Misalkanbest[left][right]adalah jumlah koin terbanyak dari balon yang berada tepat di antara posisileftdanright. Coba setiap balonkdi antara keduanya sebagai balon terakhir: balon itu menghasilkanbest[left][k] + best[k][right]ditambahvals[left] × vals[k] × vals[right]. Isi celah pendek sebelum celah panjang.
Solusi
Setiap letusan mengubah siapa yang berada di sebelah siapa, jadi balon pertama yang kamu pecahkan tidak membagi barisan: kedua sisinya menjadi tetangga. Balon terakhir yang dipecahkan dalam suatu rentanglah yang membaginya. Balon itu tetap ada sementara yang lainnya hilang, sehingga rentang di kedua sisinya saling independen, dan tabel interval untuk rentang menyelesaikan masalah dalam O(n³).
Cobalah setiap urutan ledakan
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Pilih satu balon, kumpulkan left × value × right, keluarkan balon itu, lalu selesaikan barisan yang lebih pendek dengan cara yang sama, sambil mempertahankan total terbaik dari semua pilihan. Cara ini mencoba setiap urutan, jadi hasilnya benar.
Pilihan untuk letusan pertama ada n, berikutnya n-1, dan seterusnya: ada n! urutan, jumlahnya sudah mencapai 479,001,600 untuk 12 balon. Mengingat hasil untuk setiap kumpulan balon yang masih berdiri tidak membantu, karena ada 2^n kumpulan.
Algoritma
- Tulis
burstAll(row), jumlah koin terbanyak dari balon-balon dirow, 0 untuk baris kosong. - Untuk setiap posisi
k, dapatkanleft × row[k] × right, gunakan 1 jika melewati salah satu ujung, lalu tambahkan hasilburstAlldari baris tanparow[k]. - Kembalikan total terbaik untuk semua
k, lalu panggilburstAll(nums).
def maxCoins(nums):
# Most coins you can still collect from the balloons in row
def burst_all(row):
top = 0
for k in range(len(row)):
left = row[k - 1] if k > 0 else 1
right = row[k + 1] if k + 1 < len(row) else 1
# Burst row[k] now, then do as well as possible with the rest
coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
top = max(top, coins)
return top
return burst_all(nums)Rekursi pada balon terakhir, dengan memo
Intuisi
Tambahkan angka 1 di setiap ujung baris: vals = [1] + nums + [1]. Bantalan ini tidak pernah meletus dan menggantikan tetangga yang hilang. Misalkan solve(left, right) adalah jumlah koin terbanyak dari balon yang berada tepat di antara dua posisi yang masih ada.
Misalkan k adalah balon terakhir yang meletus di celah itu. Semua balon lain di celah tersebut meletus saat k masih berdiri seperti dinding, sehingga bagian antara left dan k hanya melihat balonnya sendiri dan dua batas tetap, begitu pula bagian antara k dan right. Saat k meletus, tetangganya adalah left dan right. Jadi, hasil terbaik untuk celah tersebut adalah, untuk setiap k, hasil terbaik dari kedua bagian ditambah vals[left] × vals[k] × vals[right]. Jawabannya adalah celah di antara kedua bantalan. Ada sekitar n²/2 celah, dan masing-masing mencoba hingga n balon, jadi memo membuat kompleksitasnya O(n³).
Algoritma
- Buat
valssebagainumsdengan menambahkan 1 di setiap ujung, lalu tetapkanmke panjangnya. - Buat memo berukuran
m × myang diisi dengan -1. - Tulis
solve(left, right): kembalikan 0 jikaright - left < 2, dan nilai yang tersimpan jika ada. - Jika tidak, coba setiap
kyang berada di antara keduanya sebagai balon terakhir, simpan nilai terbesar darisolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right], lalu simpan nilainya. - Kembalikan
solve(0, m-1).
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
memo = [[-1] * m for _ in range(m)]
# Most coins from the balloons strictly between left and right
def solve(left, right):
if right - left < 2:
return 0
if memo[left][right] >= 0:
return memo[left][right]
top = 0
for last in range(left + 1, right):
# last bursts after every other balloon in the gap
coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
top = max(top, coins)
memo[left][right] = top
return top
return solve(0, m - 1)Isi tabel interval berdasarkan lebar
Intuisi
Rekursi hanya menanyakan celah yang lebih sempit, jadi isi tabel yang sama dengan perulangan, dari celah sempit ke celah lebar. Dengan begitu, best[left][k] dan best[k][right] sudah final saat celah yang lebih lebar membutuhkannya.
Untuk [2, 4, 3], yang diberi bantalan menjadi [1, 2, 4, 3, 1], best[0][4] mencoba setiap balon sebagai balon terakhir. Jika 3 menjadi yang terakhir, hasilnya adalah best[0][3] = 30 ditambah 1 × 3 × 1, sehingga totalnya 33, yang terbaik dari ketiganya.
Jumlah pengerjaannya sama dengan versi memo, tetapi perulangan biasa melewati jutaan pemanggilan fungsi, sehingga versi ini beberapa kali lebih cepat dalam bahasa seperti Python atau R.
Algoritma
- Buat
valsdarinumsdengan menambahkan 1 di setiap ujung, lalu tetapkanmsebagai panjangnya. - Buat tabel
m × mbernamabestyang diisi dengan 0. - Untuk setiap lebar dari 2 hingga
m-1, dan setiapleftdenganright = left + widthdi dalam array, coba setiapkyang berada tepat di antaranya. - Tetapkan
best[left][right]ke nilai terbesar daribest[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]. - Kembalikan
best[0][m-1].
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
# best[left][right]: most coins from the balloons strictly between left and right
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
edge = vals[left] * vals[right]
top = 0
for last in range(left + 1, right):
# last goes after every other balloon in the gap,
# so left and right are its neighbours when it bursts
coins = best[left][last] + best[last][right] + edge * vals[last]
if coins > top:
top = coins
best[left][right] = top
return best[0][m - 1]
Jebakan dan kasus tepi
- Membagi berdasarkan balon pertama yang dipecahkan, dengan tetangga aslinya,
nums[k-1] × nums[k] × nums[k+1]ditambah kedua sisi. Tetangga itu mungkin sudah tidak ada: pada[2, 4, 3], hasilnya 44, lebih besar daripada hasil yang bisa diperoleh dari urutan mana pun yang benar-benar dilakukan. - Mengisi baris tabel satu per satu dengan
leftyang terus bertambah. Dengan begitu,best[k][right]untukk > leftbelum dihitung dan nilainya terbaca sebagai 0. Isi tabel berdasarkan lebar, atau telusurileftsecara menurun. - Menandai celah yang belum diselesaikan dalam memo dengan 0. Celah yang berisi balon bernilai nol memang bernilai 0, jadi celah itu akan dihitung ulang setiap kali dikunjungi. Gunakan -1.
- Di Lua dan R, posisi tambahan berjalan dari 1 hingga
m, jadi jawabannya adalahbest[1][m].
Pertanyaan yang sering diajukan3
Mengapa Burst Balloons memilih balon terakhir, bukan yang pertama?
Setelah balon pertama meletus, kedua sisi di sebelahnya menjadi bertetangga, sehingga keduanya tetap saling memengaruhi. Balon terakhir dalam suatu rentang tetap utuh sementara balon lainnya meletus, sehingga kedua sisinya tidak pernah bertemu dan masing-masing menjadi submasalah yang independen. Saat balon itu meletus, balon-balon tetangganya menjadi batas rentang tersebut.
Berapa kompleksitas waktu Burst Balloons?
Waktu O(n³) dan memori O(n²): sekitar n²/2 celah, masing-masing mencoba hingga n balon sebagai balon terakhir. Untuk 300 balon, jumlahnya sekitar 4.5 × 10^6 langkah. Mencoba setiap urutan membutuhkan O(n · n!).
Apakah Burst Balloons dapat diselesaikan dengan urutan greedy?
Tidak. Memecahkan balon terkecil terlebih dahulu menghasilkan 24 pada [2, 4, 3], padahal 33 bisa diperoleh. Memecahkan balon yang memberi hasil paling besar saat ini menghasilkan 42 pada [2, 9, 2], padahal memecahkan balon bernilai 2 terlebih dahulu menghasilkan 18 + 18 + 9 = 45. Setiap balon yang dipecahkan mengubah harga balon berikutnya.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def maxCoins(nums):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [2, 4, 3]
Output yang diharapkan
33