Coding Interview Prep · Ders

Aralık DP Örüntüsü ve Doldurma Sırası

Q: “Aralık DP Örüntüsü ve Doldurma Sırası” dersi ücretsiz mi?

Evet — “Aralık DP Örüntüsü ve Doldurma Sırası” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Q: Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.

Q: “Aralık DP Örüntüsü ve Doldurma Sırası” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

dp[i][j] aralık DP durumunu tanımlayın, aralıkların neden artan uzunluk sırasına göre doldurulması gerektiğini açıklayın ve örüntüyü matris zinciri çarpımında izleyin.

Aralık DP Örüntüsü ve Doldurma Sırası, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Aralık DP Nedir?

Aralık DP, durumun dp[i][j] indeksler arasında i ile j arasındaki alt problem için en iyi yanıtı temsil ettiği bir dinamik programlama örüntüsüdür. Temel fikir, önce daha küçük aralıkları çözmek ve tüm aralığa doğru ilerlemektir. Bu örüntü; alt problem sınırlarının bir aralığın sol ve sağ uç noktaları olduğu matris zinciri çarpımı, palindrom bölme ve balon patlatma gibi problemleri doğal biçimde modeller.

Durum Tanımı ve Temel Durumlar

Aralık DP'de durum, i <= j koşulunu sağlayan dp[i][j]'dir. Temel durumlar tek elemanlı aralıklardır: dp[i][i]. Bunlar doğrudan çözülür — örneğin tek bir matrisin çarpma maliyeti sıfırdır. İki elemanlı aralıkların dp[i][i+1] yanıtları da çoğu zaman basittir. Tabloyu, uzunluğu 1'den başlayıp n'e kadar artan aralık uzunlukları için doldururuz.

n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
    dp[i][i] = 0  # length-1 intervals

Doldurma Sırası: Artan Uzunluk

Aralık DP'deki kritik ayrıntı doldurma sırasıdır. Daha uzun bir aralık daha kısa alt aralıklara bağlı olduğundan, L uzunluğundaki tüm aralıkları L+1 uzunluğundaki aralıkları hesaplamadan önce hesaplamamız gerekir. Dış döngü, aralık uzunluğu üzerinde 2'den n'e kadar yineler; orta döngü sol sınır olan i'yi belirler ve sağ sınırı j = i + L - 1 olarak türetiriz.

n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0

for length in range(2, n + 1):      # interval length
    for i in range(n - length + 1): # left boundary
        j = i + length - 1          # right boundary
        for k in range(i, j):       # split point
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

Matris Zinciri Çarpımı Kurulumu

Klasik aralık DP problemi matris zinciri çarpımıdır: boyutları dims[0..n] olan matrisler verildiğinde, çarpımı hesaplamak için gereken en az skaler çarpma sayısını bulun. A(p×q) matrisi ile B(q×r) matrisini çarpmak p*q*r işlem maliyetine sahiptir. dp[i][j] = i ile j arasındaki matrisleri çarpmak için gereken minimum maliyet. Bölme noktası k, dizinin iki alt zincire nereden ayrılacağına karar verir.

def matrix_chain_order(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

print(matrix_chain_order([10, 30, 5, 60]))  # 4500

DP Tablosunu İzleme

[10, 30, 5, 60] boyutlarıyla verilen ve üç matrisi temsil eden matris zinciri örneğini adım adım izleyelim: A(10×30), B(30×5), C(5×60). dp[0][2] için k=0 noktasında bölmeyi deneriz: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000; k=1 noktasında ise: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Dolayısıyla dp[0][2] = 4500 olur; bu değer önce AB çarpılarak elde edilir.

Bu Doldurma Sırası Neden İşe Yarar

dp[i][j] hesaplanırken, [i, j-1] aralığındaki tüm k değerleri için dp[i][k] ve dp[k+1][j] değerlerine başvururuz. Her iki alt aralığın uzunluğu da [i, j] aralığından kesinlikle daha kısadır. Uzunlukları küçükten büyüğe doğru işleyerek gereken tüm alt aralıkların ihtiyaç duyulmadan önce hesaplanmasını sağlarız. Aralık DP'deki doldurma sırasının doğruluğunun temel gerekçesi budur — kısa aralıklar her zaman uzun aralıkların bağımlılıklarıdır.

Belleklemeli Yukarıdan Aşağı Aralık DP

Aralık DP, alternatif olarak yukarıdan aşağı bellekleme ile uygulanabilir. [i, j] aralığı için en iyi maliyeti döndüren solve(i, j) adlı özyinelemeli bir işlev yazar ve sonuçları bir sözlükte önbelleğe alırız. Doldurma sırası özyineleme tarafından otomatik olarak yönetilir. Yukarıdan aşağı yaklaşımın mantığını kurmak çoğu zaman daha kolaydır, ancak işlev çağrısı ek yüküne neden olabilir; aşağıdan yukarı yaklaşım büyük girdilerde pratikte daha hızlıdır.

from functools import lru_cache

def matrix_chain_memo(dims):
    n = len(dims) - 1
    
    @lru_cache(maxsize=None)
    def solve(i, j):
        if i == j:
            return 0
        return min(
            solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
            for k in range(i, j)
        )
    
    return solve(0, n-1)

print(matrix_chain_memo([10, 30, 5, 60]))  # 4500

Zaman ve Alan Karmaşıklığı

Aralık DP'de O(n²) durum vardır (tüm (i, j) çiftleri) ve her durum O(n) bölme noktası üzerinde yinelenir; bu da genel olarak O(n³) time karmaşıklığı verir. DP tablosu için gereken alan O(n²)'dir. 100 matrisli matris zinciri çarpımında bu, 1.000.000 işlem demektir — oldukça uygulanabilirdir. Bu örüntü birçok zor LeetCode probleminde görülür ve belirgin olmayan yapısı nedeniyle FAANG mülakatlarında sıkça tercih edilir.

En İyi solution'ı Yeniden Oluşturma

Yalnızca maliyeti değil, gerçek parantezlemeyi de yeniden oluşturmak için her durumda minimumu sağlayan k değerini kaydeden ayrı bir split[i][j] tablosu tutun. Ardından bölmeleri özyinelemeli olarak okuyun: reconstruct(i, j), [i, split[i][j]] ve [split[i][j]+1, j] aralıkları üzerinde özyineleme yaparak en iyi gruplandırmayı yazdırır. Bu teknik, tüm aralık DP problemlerine uygulanabilir.

def matrix_chain_with_split(dims):
    n = len(dims) - 1
    dp = [[0]*n for _ in range(n)]
    split = [[0]*n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k
    return dp[0][n-1], split

Her Türlü Aralık DP Problemi İçin Şablon

Evrensel aralık DP şablonu üç bölümden oluşur: (1) tek elemanlar için temel durumları başlatın, (2) artan uzunluklar üzerinde döngü kurun ve her uzunluk için geçerli sol sınırlar üzerinde yineleyerek sağ sınırı hesaplayın, (3) her aralık için tüm bölme noktaları üzerinde yineleyin ve probleme özgü bağıntıyı uygulayın. Problemler arasındaki tek değişen kısım, en içteki döngüdeki bağıntı formülüdür.

def interval_dp_template(n, base_cost, split_cost):
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = base_cost(i)  # problem-specific base case
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                # problem-specific recurrence
                candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
                dp[i][j] = min(dp[i][j], candidate)
    
    return dp[0][n-1]

Yaygın Aralık DP Problemleri

Aralık DP kullanan problemler arasında şunlar bulunur: Matris Zinciri Çarpımı (işlemleri en aza indirme), Balon Patlatma (paraları en üst düzeye çıkarma), Tuhaf Yazıcı (yazdırma işlemlerini en aza indirme), Çokgenin Üçgenlenmesinde Minimum Puan ve Palindrom Bölme II. Her biri aynı doldurma sırası iskeletini, ancak farklı bağıntıları kullanır. Bir problem, herhangi bir iç noktadan bölünebilen bir aralık veya dizi üzerinde en iyi değeri istiyorsa bu örüntüyü tanıyın.

Hızlı Kontrol

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

Ders Özeti

Bu derste şunları öğrendiniz: aralık DP'si, bir aralık üzerindeki en iyi yanıtı temsil etmek için dp[i][j] kullanır, alt aralıkların önce hesaplanması için doldurma sırası artan aralık uzunluğu olmalıdır ve evrensel şablon O(n³) time ve O(n²) alan karmaşıklığına sahiptir. Sırada, bu örüntüyü kullanarak en uzun palindromik alt diziyi ve alt dizeyi inceleyeceğiz.

Sıkça Sorulan Sorular