Balon Patlatma: Ters Aralık DP

Değerleri nums olan n balon verildiğinde, i numaralı balonu patlatmak nums[i-1] * nums[i] * nums[i+1] kadar para kazandırır (balonun kendisiyle o anki komşularının çarpımı). Balon patladıktan sonra komşuları bitişik hâle gelir. Tüm balonları patlatarak toplayabileceğiniz maksimum para miktarını bulunuz. Basit benzetimi yapmak zordur; çünkü balonları patlatmak komşuları değiştirir — ters aralık DP'si bu zorluğu ustaca aşar.

dp[i][j] değerini [i, j] aralığındaki balonları patlatmaktan elde edilebilecek maksimum para olarak tanımlamaya ve önce hangi balonun patlatılacağını düşünmeye çalışırsak bir sorunla karşılaşırız: k numaralı balonu önce patlatmak, nums[k-1] ile nums[k+1] değerlerinin o anki komşular olması demektir; ancak bu balonlar daha sonra patlatılabilir ve komşuları değiştirebilir. Durumu ileri yönde temiz bir şekilde tanımlamak zordur.

Buradaki yöntem, [i, j] aralığında en son hangi balonun patlatılacağını düşünmektir. k numaralı balon [i, j] aralığında en son patlatıldığında, bu aralıktaki diğer tüm balonlar zaten yok olmuştur. Dolayısıyla k numaralı balonun komşuları tam olarak nums[i-1] ve nums[j+1] olur; bunlar aralığın hemen dışındaki sınır balonlarıdır. Böylece son patlatma için para hesabı belirli hâle gelir: daha önceki patlatmaların sırasına bağlı değildir.

Kukla sınır balonları ekleyiniz: nums dizisinin başına ve sonuna 1 ekleyerek nums = [1] + nums + [1] dizisini oluşturunuz. dp[i][j] değerini, i ve j dizinlerinin tam arasında bulunan tüm balonları patlatmaktan elde edilebilecek maksimum para olarak tanımlayınız; bu durumda nums[i] ve nums[j] hayatta kalan sınır balonlarıdır. Bağıntı şöyledir: (i, j) aralığındaki her olası son balon k için dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Diziyi kukla sınırlarla genişletir, DP tablosunu başlangıçta sıfırlarla doldururuz (boş aralık = 0 para) ve tabloyu artan aralık uzunluklarıyla doldururuz. Nihai yanıt dp[0][n+1] değeridir; bu, tüm başlangıçtaki balonları kukla sınırları kalıcı sınırlar olarak kullanarak patlatmaktan elde edilebilecek maksimum parayı temsil eder.

[3, 1, 5, 8] dizisi, [1, 3, 1, 5, 8, 1] biçiminde genişletilir (dizinler 0-5). dp[0][5] değerini istiyoruz. İçinde bir balon bulunan uzunluk=2 aralıkları için: 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. Adım adım ilerlediğimizde en iyi seçim, komşuları önce patlattıktan sonra {3,1,5,8} içindeki 1'i en son patlatmaktır; böylece toplam 167 para elde edilir.

O(n²) aralık bulunur ve her aralık için O(n) bölme noktası denenir; dolayısıyla zaman karmaşıklığı O(n³)'tür. Bellek kullanımı DP tablosu için O(n²)'dir. n = 500 balon için bu, 125 milyon işlem anlamına gelir ve mülakat kısıtları için uygulanabilirdir. Kukla sınırların eklenmesi, sınırların işlenmesini kolaylaştırır: bu yöntem olmadan i-1 ve j+1 değerlerinin sınırlar içinde olup olmadığını açıkça kontrol etmeniz gerekirdi.

Aynı çözüm, mülakat sırasında türetilmesi daha sezgisel olabilen üstten alta bir yaklaşımla @lru_cache kullanılarak da yazılabilir. solve(i, j) işlevini açık (i, j) aralığındaki maksimum para olarak tanımlayınız. İşlev, son patlatılacak balon olarak tüm k değerlerini dener ve sonuçları önbelleğe alır. Her iki yaklaşımın da zaman ve bellek karmaşıklığı aynıdır.

Yaygın bir hata, dp[i][j] değerini [i,j] aralığındaki ilk balon patlatıldığında elde edilen para olarak tanımlamaktır; son balon patlatıldığında elde edilen para olarak değil. Bu yaklaşım başarısız olur; çünkü ilk patlatmanın para hesabı henüz patlatılmamış komşu balonlara bağlıdır ve algoritma ilerledikçe bu komşuların durumu değişir. Sınırlar kalan öğelere bağlı olduğunda, aralık DP'sinde her zaman son öğeyi düşününüz.

Değeri 1 olan kukla sınırlar, çarpma işlemindeki etkisiz elemanlar oldukları için seçilir. Bir sınır balonu en son patlatıldığında para değeri boundary * last * boundary = 1 * last * 1 = last olur. 0 kullanmak 0 para verir (yanlıştır), diğer değerleri kullanmak ise hesabı bozar. Kukla sınır yöntemi, en soldaki ve en sağdaki balonlar için özel durum yazmaya gerek bırakmadan tüm sınır durumlarını düzgün biçimde birleştirir.

Standart aralık DP'sinde (matris zincirinde) bölme noktası k, problemin bağımsız olarak çözülen iki alt probleme ayrıldığı yeri temsil eder. Balon Patlatma probleminde ise k, aralıkta en son patlatılan balondur; bu nedenle k hâlâ sınır olarak mevcut olduğu sürece [i,k] ve [k,j] alt aralıkları bağımsızdır. Bu ters bakış açısı, Balon Patlatma probleminin aralık DP'siyle çözülebilmesini sağlayan yaratıcı fikirdir.

Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayışınızı sınayınız.

Bu derste şunları öğrendiniz: ileri simülasyon, balonları patlatmanın komşuları öngörülemez biçimde değiştirmesi nedeniyle başarısız olur, tersten bakış, k'yi bir aralıktaki son patlatılan balon olarak tanımlar ve komşuları nums[i] ile nums[j] yapar ve dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) yineleme bağıntısı, nöbetçi değerlerle doldurmayla birlikte O(n³) çözümünü sağlar. Sırada, klasik 0/1 sırt çantası ve bellek optimizasyonuyla başlayarak sırt çantası DP'si var.