Burst Balloons

+10

Bir balon sırası nums olarak verilmiştir; burada nums[i], i numaralı balonun üzerindeki sayıdır. Tüm balonları, seçtiğin herhangi bir sırayla, teker teker patlatırsın. Bir balonu patlatmak left × nums[i] × right jeton kazandırır; burada left ve right, balonun o anki komşularının, yani sırada hâlâ bulunan her iki taraftaki en yakın balonların üzerindeki sayılardır. Sıranın iki ucundan birinin ötesinde komşu yoksa, bu komşunun değeri 1 kabul edilir. Bir balon patlatıldıktan sonra iki komşusu yan yana gelir. Toplayabileceğin en yüksek jeton sayısını döndür.

Fonksiyon

maxCoins(nums: integer-array) → integer

numsinteger-array: balonların üzerindeki sayılar, soldan sağa
Döndürürinteger: her balonu patlatarak toplayabileceğin en fazla jeton

Kısıtlar

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
Cevap 3 × 10⁸ değerinden küçüktür, bu nedenle 32 bitlik işaretli bir tamsayıya sığar.

Örnekler

Girdi: nums = [2, 4, 3]
Çıktı: 33
Açıklama: İlk 4 balonu patlatarak 2 × 4 × 3 = 24 jeton kazanırsın. 2 ve 3 artık komşu olduğundan, 2'yi patlatmak 1 × 2 × 3 = 6 kazandırır; artık tek başına olan 3 ise 1 × 3 × 1 = 3 kazandırır. Böylece toplam 33 olur ve başka hiçbir sıralama daha iyi sonuç vermez: küçük 2'yi önce patlatmak, kazanabileceğin miktarı zaten 24 ile sınırlar.

Gönderirken +15 gizli test

Ek soru

En çok jeton kazandıran bir patlama sırası da döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her patlama, sıradaki komşulukları değiştirir; bu yüzden şimdi yapılan bir seçim, sonraki her patlamanın maliyetini değiştirir. Tüm sıralamaları denemek, n! dizi demektir. Patlayacak ilk balonu düşünmek de diziyi bölmez, çünkü balonun iki yanındaki balonlar komşu hâle gelir. Bir aralıktaki patlayacak son balonu düşünmek ise diziyi böler: Diğer her şey patlarken o yerinde kalır; böylece solundaki aralık ve sağındaki aralık birbirinden bağımsız olur. Bu aralıklar üzerinde tutulan bir tablo, problemi O(n³) zamanda çözer.

Her patlama sırasını deneyin

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Şimdi patlatmak için herhangi bir balon seç, mevcut komşularıyla birlikte left × value × right değerini topla, balonu sıradan çıkar ve kısalan sırayı aynı şekilde çöz. Her seçim için bunu yap ve en iyi toplamı koru. Özyinelemeli bir burstAll(row) fonksiyonu tam olarak bunu yapar. Olası her sırayı inceler, dolayısıyla yanıt doğrudur.

Gerçek boyutlar için bu yöntem umutsuzdur. İlk patlatma için n seçenek, ikincisi için n-1 seçenek vardır ve böyle devam eder: n! sıra. 12 balon için bu şimdiden 479,001,600 sıra eder ve en büyük testte 120 balon vardır. Hâlâ yerinde duran her balon kümesi için sonuçları hatırlamak da işe yaramaz, çünkü bu tür 2^n küme vardır.

Çözüm, alt problemlerin neden bu kadar çok olduğunu fark etmektir. k balonunu patlattıktan sonra solundaki balonla sağındaki balon birbirine değmeye başlar; dolayısıyla solda olanlar hâlâ sağa bağlıdır. Bir sonraki yaklaşım, iki tarafın birbirini etkilememesini sağlayacak şekilde üzerinde düşüneceğin balonu seçer.

Algoritma

Balonlardan en çok parayı kazanmak için burstAll(row) yaz; bu işlev row içindeki balonlardan kazanılabilecek en çok parayı döndürür.
Her k konumu için, her iki ucun bir ötesinde 1 olacak şekilde komşuları oku.
left × row[k] × right kadar kazan ve row[k] olmadan oluşturulan satırın burstAll sonucunu ekle.
Boş bir satır için 0, aksi hâlde tüm k değerleri arasındaki en iyi toplamı döndür.
burstAll(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 balonda özyineleme, bir notla

Sezgi

Önce her iki uca da 1 ekleyin: vals = [1] + nums + [1]. Bu ikisi asla patlamaz ve kenarlarda eksik olan komşuları temsil eder. Şimdi hâlâ yerinde duran left ve right konumları arasındaki boşluğa bakın ve sorun: Boşluğun içindeki hangi balon en son patlar?

Diyelim ki bu k. Boşluktaki diğer balonlar patlarken k hâlâ oradadır; aralarında bir duvar gibi durur. left ile k arasındaki her balonun komşuları yalnızca o aralıktan gelir; sabit sınırlar left ve k'dir. Aynı şey k ile right arasındaki aralık için de geçerlidir. Böylece bu iki aralık, aynı türden bağımsız problemlerdir. k sonunda patladığında sınırların arasındaki her şey yok olmuştur; dolayısıyla komşuları tam olarak left ve right olur ve vals[left] × vals[k] × vals[right] kadar jeton kazandırır. İlk patlayan balonu seçmek böyle bir bölünme sağlamaz, çünkü iki yanı komşu hâle gelir.

Bu, özyinelemeli bir çözüm verir. solve(left, right), left ile right arasındaki balonlardan elde edilebilecek en yüksek jeton sayısını döndürür: boşluk boşsa 0; değilse boşluktaki her k için solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] değerlerinin en büyüğü. Yanıt, iki kenar dolgusunun arasındaki boşluk olan solve(0, m-1) ifadesidir.

Tek başına özyineleme aynı boşluğu tekrar tekrar hesaplar; bu yüzden her sonucu memo[left][right] tablosunda saklayın ve sonraki ziyaretlerde bu sonucu döndürün. Yaklaşık n²/2 boşluk vardır ve her biri en fazla n balonu dener; dolayısıyla işlem miktarı O(n³) olur. Henüz çözülmemiş bir boşluk için -1 kullanın, çünkü 0 geçerli bir yanıttır. Her çağrı daha dar bir boşluk üzerinde çalıştığından özyineleme hiçbir zaman n+1 çağrıdan daha derine inmez.

Algoritma

Her iki uca da 1 ekleyerek vals'i nums olarak oluşturun ve m'yi uzunluğuna eşitleyin.
-1 ile doldurulmuş m × m boyutunda bir memo oluşturun.
solve(left, right) fonksiyonunu yazın: right - left < 2 ise 0, kayıtlı bir değer varsa bu değeri döndürün.
Aksi takdirde, son balon olarak aralarındaki her k değerini deneyin, en büyük solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] değerini seçip kaydedin.
solve(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)
    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 doldurun

Sezgi

Özyineleme yalnızca daha dar aralıkları sorar. Bu nedenle, dar aralıkları geniş olanlardan önce doldurduğun sürece aynı tabloyu özyineleme kullanmadan da doldurabilirsin. best[left][right], left ile right arasındaki balonlardan elde edilebilecek en fazla jeton sayısı olsun; içinde hiçbir şey olmayan bir aralık için 0. 2'den başlayarak her genişlik için ve bu genişlikteki her aralık için, son balon olarak içerideki her k değerini dene. best[left][k] ve best[k][right] daha dar olduklarından sonuçları zaten kesinleşmiştir.

[2, 4, 3] dizisini ele alalım. Kenarlara 1 eklenince, 0'dan 4'e kadar konumlarda vals = [1, 2, 4, 3, 1] elde edilir ve yanıt best[0][4] değeridir. Aralıkları en dardan başlayarak dolduralım:

Genişlik 2, içeride bir balon: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], 2 ve 4 balonları: 2 en son patlatılırsa 0 + 24 + 1 × 2 × 3 = 30; 4 en son patlatılırsa 8 + 0 + 1 × 4 × 3 = 20. Yani 30.
best[1][4], 4 ve 3 balonları: 4 en son patlatılırsa 0 + 12 + 2 × 4 × 1 = 20; 3 en son patlatılırsa 24 + 0 + 2 × 3 × 1 = 30. Yani 30.
best[0][4], üçü de: 2 en son patlatılırsa 0 + 30 + 1 × 2 × 1 = 32; 4 en son patlatılırsa 8 + 12 + 1 × 4 × 1 = 24; 3 en son patlatılırsa 30 + 0 + 1 × 3 × 1 = 33. Yani 33.

En iyi seçimleri geriye doğru izleyince sıralamayı bulursun: 3 en son patlatılır; ondan önce, solundaki aralıktaki son balon 2'dir ve 4 ilk patlatılır. Böylece 24 + 6 + 3 = 33 olur.

İşlem miktarı memo kullanımıyla aynıdır: 300 balon için 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 adım ve 302 × 302 sayılık bir tablo. Basit döngüler, milyonlarca işlev çağrısını önler; bu da bu sürümü Python veya R gibi dillerde özyinelemeden birkaç kat daha hızlı hâle getirir.

Algoritma

vals'i, başına ve sonuna birer 1 eklenmiş nums olarak oluştur ve m'yi uzunluğuna eşitle.
0'larla doldurulmuş bir m × m tablosu best oluştur.
2'den m-1'e kadar her genişlik için ve dizi içinde right = left + width koşulunu sağlayan her left için, aralarındaki her k değerini dene.
best[left][right] değerini, best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right] değerlerinin en büyüğü olarak ayarla.
best[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)
    # 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

Yaygın hatalar; açgözlü bir sıralama, ilk patlatılan balon üzerinden özyineleme, hatalı bir memo işaretçisi ve tablonun yanlış sırayla doldurulmasıdır.

Açgözlü sıralamalar başarısız olur. En küçük balonu önce patlatmak [2, 4, 3] için 33 yerine 24 kazandırır; o anda en çok kazandıran balonu patlatmak ise [2, 9, 2] için 42 kazandırırken, önce bir 2'yi patlatmak 18 + 18 + 9 = 45 kazandırır.
İlk patlatılan balonu, ilk komşularıyla birlikte nums[k-1] × nums[k] × nums[k+1] ve iki tarafın sonuçlarını kullanarak ele almak, artık orada olmayabilecek komşuları hesaba katar. [2, 4, 3] için 44 sonucunu verir; bu, gerçek herhangi bir sıranın kazandırabileceğinden fazladır.
Sınırları aralığın bir parçası olarak saymak. Aralık temizlendiğinde left ve right hâlâ yerindedir; yalnızca aralarında bulunan balonlar patlatılır.
Tabloyu satır satır, left değerini artırarak doldurmak. Bu durumda k > left için best[k][right] henüz hesaplanmamıştır ve değeri 0 olarak okunur. Genişliğe göre doldurun veya left değerini azaltarak ilerleyin.
Çözülmemiş bir aralığı memo'da 0 olarak işaretlemek. Sıfır balon içeren bir aralığın değeri gerçekten 0'dır; bu yüzden sonsuza kadar çözülmemiş gibi görünür ve her ziyaret edildiğinde yeniden çözülür. -1 kullanın.
İki dolgu 1'ini unutmak; bu durumda uçlardaki balonların çarpılacak komşusu kalmaz.
Lua ve R'de dolgulu konumlar 1'den m'ye kadar gider; bu nedenle yanıt best[1][m] olur.

Sıkça sorulan sorular4

Why Burst Balloons son balonu seçiyor da ilk balonu seçmiyor?

İlk patlamadan sonra, iki yanındaki balonlar komşu hâle gelir; bu yüzden sol ve sağ kısım birbirini etkilemeye devam eder ve ayrı ayrı çözülemez. Bir aralığın son balonu, diğerleri patlarken yerinde kalır; böylece iki taraf hiçbir zaman birleşmez ve o balon patladığında komşuları aralığın sabit sınırları olur. Bu da her aralığı bağımsız bir alt problem hâline getirir; dinamik programlamanın ihtiyaç duyduğu şey de budur.

Burst Balloons algoritmasının zaman karmaşıklığı nedir?

Aralık tablosunda yaklaşık n²/2 boşluk vardır ve her biri son balon olarak en fazla n balonu dener; bu nedenle zaman karmaşıklığı O(n³), bellek karmaşıklığı ise O(n²) olur. 300 balon için bu yaklaşık 4.5 × 10^6 adımdır. Her sırayı denemek O(n · n!) karmaşıklığındadır.

Balon Patlatma problemi açgözlü bir sırayla çözülebilir mi?

Hayır. Her basit kural, küçük bir dizide başarısız olur. En küçük balonu önce patlatmak, 33'ün mümkün olduğu [2, 4, 3] dizisinde 24 kazandırır. Şu anda en çok kazandıran balonu patlatmak, önce bir 2'yi patlatmanın 45 kazandırdığı [2, 9, 2] dizisinde 42 kazandırır. Bir balonu patlatmak, sonrakilerin değerlerini değiştirir; bu yüzden aralıklar üzerinde dinamik programlamaya ihtiyacın var.

Dizinin her iki ucuna neden 1 eklenir?

Eksik bir komşu 1 olarak sayılır; bu nedenle, hiç patlamayan ve değeri 1 olan iki dolgu balonu, her gerçek balona özel durumlar olmadan iki komşu sağlar. Ayrıca tüm problemin sınırlarını oluştururlar: yanıt, iki dolgu arasındaki aralıktır: best[0][m-1].

Python

def maxCoins(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [2, 4, 3]

Beklenen

Burst Balloons

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her patlama sırasını deneyin

Son balonda özyineleme, bir notla

Aralık tablosunu genişliğe göre doldurun

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler