Burst Balloons
Bir sıra balon nums olarak verilmiştir; burada nums[i], i balonunun üzerindeki sayıdır. Hepsini istediğin sırayla, teker teker patlatırsın. Bir balonu patlatmak, left × nums[i] × right kadar coin kazandırır; burada left ve right, sırada hâlâ bulunan ve balonun her iki yanındaki en yakın komşularının üzerindeki sayılardır. Eksik bir komşu 1 kabul edilir. Bir balon patlatıldıktan sonra, iki komşusu bitişik hâle gelir. Toplayabileceğin en fazla coin miktarını döndür.
Fonksiyon
- numsinteger-array
- balonlardaki sayılar, soldan sağa
- Döndürürinteger
- her balonu patlatarak toplayabileceğin en fazla jeton
Kısıtlar
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- Cevap 3 × 108'den küçüktür, bu nedenle 32 bitlik işaretli bir tamsayıya sığar.
Örnekler
- Girdi
- nums = [2, 4, 3]
- Çıktı
- 33
- Açıklama
- 2 × 4 × 3 = 24 için 4'ü patlat. Şimdi 3'ün yanındaki 2, 1 × 2 × 3 = 6 puan kazandırır ve 3 de 3 puan kazandırır: toplam 33.
- Girdi
- nums = [6, 1, 2, 5]
- Çıktı
- 108
- Açıklama
- 1'i patlat (6 × 1 × 2 = 12), ardından 2'yi, şimdi 6 ile 5 arasındakini (6 × 2 × 5 = 60), sonra 30 için 5'i ve 6 için 6'yı: toplam 108.
- Girdi
- nums = [8]
- Çıktı
- 8
- Açıklama
- Tek balonun komşusu yoktur ve her eksik komşu 1 sayıldığından 1 × 8 × 1 = 8 puan kazanır.
Ek soru
En çok jeton kazandıran patlatma sırasını da verebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Hangi balonu önce patlatacağına karar verdiğini varsayalım. İki komşusu yan yana gelir, böylece solundaki balonlar ve sağındaki balonlar hâlâ birbirini etkiler. Bu şekilde problemi iki küçük probleme bölebilir misin?
Soruyu tersine çevir ve bir aralıktaki en son patlayan balonu seç. O zamana kadar bir duvar gibi hareketsiz kalır; bu yüzden solundaki ve sağındaki balonlar hiçbir zaman komşu olmaz. Sonunda patladığında, komşuları aralığın sınırındaki iki balondur.
numsdizisinin her iki ucuna da 1 ekle.best[left][right],leftverightkonumları arasındaki balonlardan elde edilebilecek en fazla jeton sayısı olsun. Aralarındaki herkbalonunu son patlatılan balon olarak dene:best[left][k] + best[k][right]değerine ek olarakvals[left] × vals[k] × vals[right]jeton kazandırır. Kısa aralıkları uzun olanlardan önce doldur.
Çözüm
Her patlatma, kimin kimin yanında olduğunu değiştirir; bu nedenle patlattığın ilk balon sırayı bölmez: iki tarafı komşu hâle gelir. Bir aralıktaki son patlatılan balon ise sırayı böler. Diğer her şey yok olurken o ayakta kalır; bu nedenle iki yanındaki aralıklar birbirinden bağımsızdır ve aralıklar üzerinde tutulan bir tablo, problemi O(n³) zamanda çözer.
Her patlama sırasını dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir balon seç, left × value × right kadar puan topla, onu kaldır ve en iyi toplamı her seçim için saklayarak kısalan sırayı aynı şekilde çöz. Her sırayı dener; bu yüzden doğrudur.
İlk patlatmada n seçenek, sonraki patlatmada n-1 seçenek vardır ve böyle devam eder: n! sıra; 12 balonda bile bu sayı 479,001,600’dür. Ayakta kalan balon kümeleri için sonuçları hatırlamak işe yaramaz, çünkü 2^n küme vardır.
Algoritma
burstAll(row)fonksiyonunu yaz:rowsatırındaki balonlardan kazanılabilecek en çok jetonu döndür; boş bir satır için 0.- Her
kkonumu için, uçların ötesinde 1 kullanarakleft × row[k] × rightkadar kazan; ayrıcarow[k]olmadan satır içinburstAlldeğerini ekle. - Tüm
kdeğerleri arasındaki en iyi toplamı döndür veburstAll(nums)çağrısını yap.
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)Son balon üzerinde özyineleme, bir notla
Sezgi
Satırı her iki uca da birer 1 ekleyerek doldurun: vals = [1] + nums + [1]. Eklenen uçlar asla patlamaz ve eksik komşuların yerini tutar. solve(left, right), ayakta duran iki konumun arasındaki balonlardan kazanılabilecek en fazla jeton sayısı olsun.
k'nın bu aralıkta son patlayan balon olduğunu varsayalım. Aralıktaki diğer tüm balonlar, k bir duvar gibi dururken patlar; böylece left ile k arasındaki kısımda yalnızca kendi balonları ve iki sabit sınır bulunur; k ile right arasındaki kısım için de aynısı geçerlidir. k patladığında komşuları tam olarak left ve right olur. Bu nedenle aralık için en iyi sonuç, tüm k değerleri arasından iki kısmın en iyi sonuçları toplamına vals[left] × vals[k] × vals[right] eklenerek bulunur. Yanıt, iki ekleme arasındaki aralıktır. Yaklaşık n²/2 aralığın her biri en fazla n balonu dener; dolayısıyla önbelleğe alma bunu O(n³) yapar.
Algoritma
valsdeğerini, her iki ucuna da 1 eklenmişnumsolarak oluştur vemdeğerini uzunluğuna ayarla.- -1 ile doldurulmuş bir
m × mmemo oluştur. solve(left, right)fonksiyonunu yaz:right - left < 2ise 0 döndür; kayıtlı bir değer varsa onu döndür.- Aksi takdirde son balon olarak, kesinlikle bu ikisinin arasında bulunan her
kdeğerini dene; en büyüksolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]değerini tut ve kaydet. solve(0, m-1)değerini döndür.
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)Aralık tablosunu genişliğe göre doldur
Sezgi
Özyineleme yalnızca daha dar aralıkları sorgular; bu yüzden aynı tabloyu döngülerle, dar aralıklardan geniş olanlara doğru doldur. Böylece daha geniş bir aralık onlara ihtiyaç duyduğunda best[left][k] ve best[k][right] son değerlerini almış olur.
[2, 4, 3] dizisi [1, 2, 4, 3, 1] olacak şekilde doldurulduğunda, best[0][4] her balonu son patlatma seçeneği olarak dener. En son 3'ü patlatmak, best[0][3] = 30 değerine 1 × 3 × 1 ekler ve 33 eder; bu, üç seçenek arasındaki en iyi sonuçtur.
İşlem miktarı özyinelemeli belleğe alma sürümüyle aynıdır, ancak düz döngüler milyonlarca işlev çağrısını atlar; bu da bu sürümü Python veya R gibi bir dilde birkaç kat daha hızlı hâle getirir.
Algoritma
nums'a her iki uca da 1 ekleyerekvals'ı oluşturun vem'yi uzunluğuna ayarlayın.- 0 değerleriyle doldurulmuş
m × mboyutunda birbesttablosu oluşturun. - 2'den
m-1'e kadar her genişlik için ve dizinin içinderight = left + widtholacak herleftiçin, aralarında kalan herkdeğerini deneyin. best[left][right]değerinibest[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]değerlerinin en büyüğüne ayarlayın.best[0][m-1]değerini döndürün.
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]
Tuzaklar ve uç durumlar
- İlk balonu, özgün komşularıyla birlikte patlatmak:
nums[k-1] × nums[k] × nums[k+1]ve iki tarafın katkısı. Bu komşular çoktan yok olmuş olabilir:[2, 4, 3]dizisinde 44 sonucu verir; bu, gerçek sıralamalardan herhangi birinin kazandıracağından fazladır. - Tabloyu satır satır doldururken
leftdeğerini artırmak. Bu durumdak > leftiçinbest[k][right]henüz hesaplanmamıştır ve 0 olarak okunur. Genişliğe göre doldurun ya daleftdeğerini azaltarak ilerleyin. - Çözülmemiş bir aralığı önbellekte 0 olarak işaretlemek. Değeri sıfır olan balonlardan oluşan bir aralığın değeri gerçekten 0'dır; bu yüzden her ziyaret edildiğinde yeniden çözülür. -1 kullanın.
- Lua ve R'de dolgulu konumlar 1'den
m'ye kadar gider; bu nedenle yanıtbest[1][m]'dir.
Sıkça sorulan sorular3
Burst Balloons neden ilk balon yerine son balonu seçiyor?
İlk patlamadan sonra iki yanı komşu hâle gelir, dolayısıyla birbirlerini etkilemeye devam ederler. Bir aralığın son balonu, diğerleri patlarken yerinde kalır; bu nedenle iki yanı hiçbir zaman buluşmaz ve her biri bağımsız bir alt problemdir. O patladığında komşuları aralığın sınırları olur.
Burst Balloons algoritmasının zaman karmaşıklığı nedir?
O(n³) zaman ve O(n²) bellek: yaklaşık n²/2 aralık, her biri son balon olarak en fazla n balonu dener. 300 balon için bu yaklaşık 4.5 × 10^6 adımdır. Her sıralamayı denemek O(n · n!) zaman alır.
Balon Patlatma problemi açgözlü bir sırayla çözülebilir mi?
Hayır. Önce en küçük balonu patlatmak, 33 puanın mümkün olduğu [2, 4, 3] dizisinde 24 puan kazandırır. O anda en çok puan kazandıranı patlatmak, önce 2’yi patlatmanın 18 + 18 + 9 = 45 puan kazandırdığı [2, 9, 2] dizisinde 42 puan kazandırır. Her patlatma, sonrakilerin değerini değiştirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def maxCoins(nums):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
nums = [2, 4, 3]
Beklenen Çıktı
33