Bölüm 8: Dinamik Programlama

8.1Temel kavramlar

8.1.1Dinamik programlama nedir?

Algoritma tasarımında sık kullanılan bir fikir, büyük bir problemi aynı türden daha küçük problemlere bölmektir. Böl ve fethet bu fikri parçalar birbirinden bağımsızken kullanır: birleştirme sıralaması diziyi ikiye böler, iki yarıyı ayrı ayrı sıralar ve birleştirir. İki yarının ortak bir işi yoktur. Bazı problemlerde ise parçalar birbirine karışır. Büyük problemin alt problemleri, kendi alt problemlerini paylaşır. Böyle bir problem düz özyinelemeyle çözülürse aynı küçük soru defalarca sorulur ve her seferinde baştan cevaplanır.

Dinamik programlama (dynamic programming, kısaca DP) bu tekrarı ortadan kaldırır. Her alt problemin çözümü bir tabloya yazılır. Aynı alt problemle yeniden karşılaşıldığında hesap yapılmaz, cevap tablodan okunur. Yöntem özellikle bir şeyin en büyüğünü ya da en küçüğünü arayan optimizasyon problemlerinde kullanılır: en büyük değer, en kısa yol, en az işlem. Ama aynı fikir sayma ve karar problemlerinde de işe yarar: “kaç farklı yol var?”, “böyle bir alt küme var mı?”

Bu tanımın önemli bir sonucu vardır. Her dinamik programlama çözümünün arkasında bir özyinelemeli çözüm durur. DP problemi farklı bir yolla çözmez; aynı özyinelemeyi gereksiz tekrar olmadan çalıştırır. Bu yüzden DP tasarımının ilk ve en zor adımı doğru özyinelemeyi bulmaktır. Tablo, bu özyinelemenin değerlerini saklayan bir araçtır.

Yöntemin adı 1950'lerde Richard Bellman'dan gelir. Adın içindeki “programlama” sözcüğü kod yazmak anlamına gelmez. O yıllarda bu sözcük planlama ve çizelgeleme anlamında kullanılırdı; doğrusal programlama adı da aynı kökten gelir. Dinamik programlamadaki programlama, kararları bir tablo ile adım adım planlamaktır.

8.1.2Örtüşen alt problemler

Bir problemin dinamik programlamadan yarar görmesi için iki özellik gerekir. Birincisi alt problemlerin örtüşmesidir.

En bilinen örnek Fibonacci sayılarıdır. F(n) = F(n − 1) + F(n − 2) tanımı doğrudan koda çevrilirse fib(5) hesaplanırken fib(4) ve fib(3) çağrılır. fib(4) de kendi içinde fib(3)'ü çağırır. Böylece fib(3) iki kez hesaplanır. Aynı şey daha küçük argümanlarda katlanarak büyür: fib(2) üç kez, fib(1) beş kez hesaplanır. Şekil 8.1 bu tekrarları gösterir.

Burada iki sayı arasındaki fark DP'nin kazancını belirler. fib(5) için yalnız altı farklı alt problem vardır: fib(0)'dan fib(5)'e kadar. Ama düz özyineleme toplam 15 çağrı yapar. n büyüdükçe farklı alt problem sayısı n + 1 olarak kalır, çağrı sayısı ise üstel büyür. Saklanacak bir tekrar olduğu sürece tablo bu farkı kapatır.

Alt problemler örtüşmüyorsa tablo işe yaramaz. Birleştirme sıralamasında dizinin iki yarısı ayrık parçalardır. Sol yarıyı sıralamak için yapılan hiçbir iş sağ yarıda yeniden yapılmaz. Bir alt dizi ancak bir kez sıralanır; dolayısıyla tabloya yazılacak bir cevabın ikinci kez okunması da hiç gerçekleşmez. Böyle problemler böl ve fethetin alanıdır.

8.1.3Optimal alt yapı

İkinci özellik, büyük problemin en iyi çözümünün küçük problemlerin en iyi çözümlerinden kurulabilmesidir. Bu özellik olmadan tabloya yazılan alt problem cevapları büyük problemin cevabını kurmaya yetmez.

Bir örnekle açıklık kazanır. Bir dizide en büyük toplamlı alt dizi aranıyor olsun. Burada alt dizi, bitişik öğelerden oluşan bir parçadır. V(i), tam olarak i. öğede biten en büyük toplam olsun. i'de biten en iyi parça ya yalnız a[i]'den oluşur ya da i − 1'de biten bir parçanın sonuna a[i] eklenerek elde edilir. İkinci durumda i − 1'de biten parçanın da en iyisi olması gerekir. Daha iyisi varsa onu kullanmak toplamı büyütürdü. Böylece bağıntı kendiliğinden çıkar:

V(i) = max( a[i],   V(i − 1) + a[i] )

Bu tür bağıntılara Bellman denklemi de denir: bir durumun değeri, bir önceki alt problemin optimal değerinden hesaplanır. Cevap, bütün V(i) değerlerinin en büyüğüdür. Bu yöntemin adı Kadane algoritmasıdır; O(n) sürede çalışır.

Optimal alt yapı her problemde yoktur. Bir çizgede iki düğüm arasındaki en uzun basit yol (düğüm tekrarı olmayan yol) aransın. u'dan w'ye en uzun basit yol bir v düğümünden geçiyorsa, yolun u–v parçasının u'dan v'ye en uzun basit yol olması gerekmez. Daha uzun bir u–v yolu, yolun ikinci yarısındaki düğümleri kullanabilir. İki “en iyi” parça birleştirildiğinde ortaya basit olmayan bir yol çıkar. Alt problemler birbirinden bağımsız çözülemez; bu yüzden bu problem için bilinen verimli bir DP yoktur. En kısa yol probleminde ise durum farklıdır: en kısa yolun her parçası da en kısa yoldur. Bellman–Ford ve Floyd–Warshall bu özelliğe dayanır.

8.1.4Tasarım adımları

Dinamik programlama çözümleri ilk bakışta birbirinden çok farklı görünür: biri iki boyutlu bir tablo doldurur, öteki tek bir diziyle yetinir. Ama hepsi aynı adımlarla tasarlanır. Bu adımlar sırayla izlenirse yeni bir problemin çözümü de çoğu zaman kendiliğinden ortaya çıkar.

1. Optimal çözümün yapısı incelenir. Optimal çözümde son karar nedir? Bu karar verildikten sonra geriye hangi küçük problem kalır?
2. Durum ve bağıntı yazılır. Alt problem, birkaç tam sayıyla tanımlanan bir durum olarak ifade edilir; ör. “ilk i eşya ve c kapasite”. Durumun değeri daha küçük durumlar cinsinden yazılır (özyineleme bağıntısı). Bağıntının dayandığı en küçük durumların değerleri ayrıca verilir (taban durumları).
3. Hesaplama sırası belirlenir. Bir hücre hesaplanırken ihtiyaç duyduğu hücreler hazır olmalıdır.
4. Tablonun boyutu belirlenir. Kaç boyut gerekir, her boyut kaç değer alır? Örneğin sırt çantasında tablo (n + 1) × (W + 1) olur.
5. Tablo doldurulur. Aşağıdan yukarı döngülerle (tablolama) ya da yukarıdan aşağı özyinelemeyle (bellekleme).
6. Çözüm geri okunur. Çoğu problemde yalnız optimal değer değil, o değeri veren seçimler de istenir. Seçimler tablodan geriye doğru okunarak bulunur.

Bu adımların süreyle ilgili basit bir sonucu vardır. Her durum bir kez hesaplanır. Bir durumu hesaplamak için birkaç seçenek denenir. O hâlde toplam süre yaklaşık olarak durum sayısıyla bir durumun hesaplanma süresinin çarpımıdır:

toplam süre ≈ (durum sayısı) × (bir durumun hesaplanma süresi)

Notta geçen bütün karmaşıklıklar bu kuraldan çıkar. Sırt çantasında (n + 1)(W + 1) durum vardır ve her biri iki seçenekle O(1)'de hesaplanır: O(n · W). En uzun artan alt dizide n durum vardır ama her biri önceki bütün öğelere bakar: O(n²). Matris zinciri çarpımında O(n²) durumun her biri O(n) bölme noktası dener: O(n³).

8.1.5Bellekleme ve tablolama

Bir DP bağıntısı iki biçimde çalıştırılabilir. İkisi de her alt problemi bir kez çözer; fark, alt problemlerin hangi sırayla ve hangi araçla çözüldüğündedir.

Bellekleme (memoization) yukarıdan aşağı (top-down) çalışır. Özyinelemeli çözüm olduğu gibi yazılır; yalnız sonuçlar bir önbellekte saklanır. Önbellek bir dizi ya da HashMap olabilir. Her çağrının başında tabloya bakılır: cevap oradaysa hemen döndürülür, yoksa hesaplanır, tabloya yazılır ve öyle döndürülür. Hesap büyük problemden başlar ve gerekli olan küçük problemlere iner. Bu yüzden yalnız gerçekten ihtiyaç duyulan alt problemler çözülür. Bedeli özyinelemedir: her çağrının bir maliyeti vardır ve derin özyineleme yığın taşmasına (StackOverflowError) yol açabilir.

Tablolama (tabulation) aşağıdan yukarı (bottom-up) çalışır. En küçük alt problemden başlanır ve tablo döngülerle sırayla doldurulur. Özyineleme ve çağrı maliyeti yoktur; bu yüzden tablolama pratikte genellikle daha hızlıdır. Bunun karşılığında doldurma sırası önceden doğru belirlenmelidir: bir hücreye gelindiğinde bağlı olduğu hücreler hazır olmalıdır. Tablolamanın bir üstünlüğü daha vardır. Bağıntı yalnız önceki satırı kullanıyorsa bütün tablo yerine tek satır saklanabilir. Sırt çantasında bellek bu yolla O(n · W)'den O(W)'ye iner.

Hangisinin seçileceği probleme bağlıdır. Durum uzayı büyük ama gerçekte kullanılan durumlar azsa bellekleme daha az iş yapar. 0/1 sırt çantası bunun bir örneğidir: bellekleme sürümü, dört eşyalı ve 6 kapasiteli örnekte 28 durumdan yalnız 12'sini hesaplar. Bütün tablo zaten gerekiyorsa ve doldurma sırası belliyse tablolama hem daha hızlı hem daha güvenlidir.

8.1.6DP, böl ve fethet ve açgözlü yaklaşım

Dinamik programlama, iki tanıdık tasarım yöntemiyle birlikte düşünüldüğünde daha iyi anlaşılır. Üçü de problemi küçük parçalara ayırır; farkları, parçalar arasındaki ilişkide ve seçimin nasıl yapıldığındadır.

Açgözlü yaklaşım, her adımda yalnız tek bir seçeneğe bakan bir dinamik programlama gibi düşünülebilir. DP bir durumda bütün seçenekleri dener ve en iyisini tabloya yazar. Açgözlü algoritma ise o anda en iyi görünen seçeneği alır ve öteki seçenekleri hiç incelemez. Bu seçimin her zaman bir optimal çözüme götürdüğü kanıtlanabiliyorsa (açgözlü seçim özelliği) tabloya gerek kalmaz ve algoritma çok daha hızlı çalışır. Kanıtlanamıyorsa açgözlü algoritma yanlış cevap verebilir. 0/1 sırt çantası bunun tipik örneğidir.

8.1.7Uygulama alanları

Dinamik programlama kuramsal bir araç olmanın ötesinde, her gün kullanılan birçok yazılımın içinde çalışır.

• En kısa yol. Haritalar ve yönlendirme protokolleri: Bellman–Ford, “en çok k kenarlı en kısa yol” durumuyla; Floyd–Warshall, “yalnız ilk k düğümü ara düğüm olarak kullanan en kısa yol” durumuyla çalışır.
• Dizgi karşılaştırma. diff ve git iki dosyanın farkını en uzun ortak alt diziyle bulur; yazım denetleyicileri düzenleme uzaklığıyla öneri üretir.
• Biyoinformatik. DNA ve protein dizilerinin hizalanması (Needleman–Wunsch, Smith–Waterman) ve RNA'nın katlanma yapısının belirlenmesi.
• Kaynak dağıtımı. Sırt çantası, bütçe ve yatırım planlama, üretim hattı çizelgeleme.
• Derleyiciler ve sayısal hesap. Matris zinciri çarpımının sırası, optimal ikili arama ağacı, bağlamdan bağımsız dilbilgileri için CYK ayrıştırması.
• Yapay zekâ. Oyun oynayan programlar, konuşma tanıma ve makine çevirisindeki Viterbi algoritması, pekiştirmeli öğrenmedeki Bellman denklemi.

8.2Fibonacci: bellekleme ve tablolama

Fibonacci dizisinin özyinelemeli tanımı ve bu tanımı doğrudan koda çeviren metot iyi bilinir. Burada amaç özyinelemeyi yeniden anlatmak değildir. Fibonacci, dinamik programlamanın iki biçimini en küçük ölçekte göstermek için kullanılır: aynı bağıntı önce bellekleme, sonra tablolama ile çalıştırılır ve maliyetleri karşılaştırılır.

8.2.1Düz özyinelemenin bedeli

Fibonacci dizisi 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … biçiminde ilerler. Taban durumları F(0) = 0 ve F(1) = 1'dir; n ≥ 2 için F(n) = F(n − 1) + F(n − 2)'dir. Tanımın birebir kopyası olan metot doğrudur ama çok yavaştır.

static long fib(int n) {
  if (n <= 1)
    return n;         // taban durumları
  return fib(n - 1) + fib(n - 2);
}

Metodun yaptığı çağrı sayısı T(n) olsun. Her çağrı kendisi için 1 sayılır ve iki alt çağrı yapar: T(n) = T(n − 1) + T(n − 2) + 1, T(0) = T(1) = 1. Bu bağıntının çözümü T(n) = 2 · F(n + 1) − 1'dir; tümevarımla kolayca doğrulanır. Fibonacci sayıları altın oranın kuvvetleri gibi büyüdüğünden çağrı sayısı Θ(φⁿ)'dir; burada φ ≈ 1,618'dir. Tablo 8.3 farkın ne kadar hızlı açıldığını gösterir.

fib(40) üç yüz otuz milyonu aşkın çağrı yapar. fib(50) için bu sayı yaklaşık 4 · 10¹⁰'a çıkar; sıradan bir bilgisayarda dakikalar sürer. Oysa fib(n) hesaplanırken yalnız n + 1 farklı alt problem vardır: fib(0), fib(1), …, fib(n). Çağrıların ezici çoğunluğu daha önce cevaplanmış bir soruyu yeniden sorar.

Şekil 8.3'teki ağaçta fib(3) iki kez, fib(2) üç kez, fib(1) beş kez, fib(0) üç kez görünür. Bu sayıların kendileri de Fibonacci sayılarıdır: fib(n) ağacında fib(k) (k ≥ 1) tam F(n − k + 1) kez çağrılır. Tekrarın büyüklüğü, hesaplanan sayının büyüklüğüyle aynı hızda artar. Dinamik programlamanın özü bu gözlemdir: farklı alt problem sayısı küçük, ama özyinelemenin onları çağırma sayısı büyükse sonuçları saklamak büyük kazanç sağlar.

8.2.2Bellekleme

Bellekleme, metodun gövdesine iki satır ekler. Hesaplanan her değer bellek dizisine yazılır. Bir çağrı, hesap yapmadan önce diziye bakar; değer oradaysa hemen döner.

static long[] bellek = new long[50];

static long fib(int n) {
  if (n <= 1) return n;          // taban
  if (bellek[n] != 0) return bellek[n];
  long a = fib(n - 1);
  long b = fib(n - 2);
  bellek[n] = a + b;
  return bellek[n];
}

bellek dizisi static tanımlandığı için bütün çağrılar aynı diziyi paylaşır. Java'da yeni bir long dizisinin bütün öğeleri 0'dır. Kod 0'ı “henüz hesaplanmadı” anlamında kullanır. Bu seçim güvenlidir, çünkü n ≥ 2 için F(n) hiçbir zaman 0 değildir; taban durumları ise diziye hiç yazılmaz. Dizinin uzunluğu 50 olduğu için kod en çok fib(49)'u hesaplayabilir. Dönüş türünün long seçilmesi de bilinçlidir: F(47) = 2.971.215.073, int'in en büyük değeri olan 2³¹ − 1 = 2.147.483.647'yi aşar.

Satırlar şöyle çalışır. İlk if taban durumlarını karşılar. İkinci if bellekleme denetimidir: bellek[n] sıfırdan farklıysa değer daha önce hesaplanmıştır ve olduğu gibi döner. Değer yoksa iki alt çağrı yapılır, toplam bellek[n]'e yazılır ve döndürülür. Tablo 8.4, fib(5) çağrısının izlemesini verir.

Şekil 8.4'teki ağaç artık bir zincirdir. Sol kol fib(5)'ten fib(1)'e iner. Her düzeyde sağ çocuk ya bir taban durumudur ya da tablodan hazır okunur. Toplam 9 çağrı yapılır. Genel durumda fib(2)'den fib(n)'ye kadar her değer bir kez hesaplanır. Çağrılar şöyle sayılır: fib(n) ve fib(n − 1) birer kez çağrılır. 1 ≤ k ≤ n − 2 için fib(k) iki kez çağrılır; bir kez açılır, bir kez de tablodan ya da taban durumu olarak hemen cevaplanır. fib(0) ise bir kez çağrılır. Toplam 2 + 2(n − 2) + 1 = 2n − 1'dir. Üstel süre doğrusala inmiştir. Ek bellek O(n)'dir: bellek dizisi ve en derin yerinde n çerçeveli çağrı yığını.

8.2.3Tablolama

Aynı bağıntı döngüyle de çalıştırılabilir. fib(i), yalnız fib(i − 1) ve fib(i − 2)'ye bağlıdır. Dizi soldan sağa doldurulursa her hücreye gelindiğinde ihtiyaç duyduğu iki hücre hazırdır.

static int fibonacci(int n) {
  int[] fib = new int[n + 1];
  fib[0] = 0;   // taban durumları
  fib[1] = 1;
  for (int i = 2; i <= n; i++)
    fib[i] = fib[i - 1] + fib[i - 2];
  return fib[n];
}

Metot önce n + 1 öğeli bir dizi oluşturur; Java'da bütün öğeler 0 ile başlar. Taban durumları yazıldıktan sonra döngü i = 2'den n'ye kadar her hücreyi bir toplama ile doldurur. fibonacci(9) için hücreler sırasıyla 1, 2, 3, 5, 8, 13, 21 ve 34 olur. Son hücre fib[9] = 34 döndürülür. Her hücre bir kez hesaplanır: süre O(n), bellek O(n)'dir.

Bu kod küçük bir ayrıntıda dikkat ister. n = 0 için dizi tek öğelidir ve fib[1] = 1 satırı ArrayIndexOutOfBoundsException fırlatır. Kodun bütün n ≥ 0 için çalışması isteniyorsa başa if (n <= 1) return n; eklenmelidir. Ayrıca dizi int olduğu için fibonacci(47) taşar ve negatif bir sayı döner; Java'da bu sonuç −1.323.752.223'tür.

8.2.4O(1) bellek ve karşılaştırma

Tablolama sürümünde fib[i] hesaplanırken dizinin yalnız son iki hücresi okunur. Daha eski hücrelere bir daha hiç bakılmaz. O hâlde bütün diziyi saklamaya gerek yoktur; son iki değeri tutan iki değişken yeter.

static long fib(int n) {
  if (n <= 1) return n;
  long once = 0, simdi = 1;
  for (int i = 2; i <= n; i++) {
    long yeni = once + simdi;
    once = simdi;
    simdi = yeni;
  }
  return simdi;
}

Döngünün her turunda once ve simdi değişkenleri F(i − 2) ve F(i − 1)'dir. Yeni değer hesaplanır, değişkenler bir adım kaydırılır. Döngü bitince simdi, F(n)'dir. Süre yine O(n), ek bellek ise O(1)'dir. long türü F(92) ≈ 7,5 · 10¹⁸'e kadar yeter; F(93) taşar.

Bellek azaltma fikri genel bir kurala dayanır. Bir tablo hücresi yalnız sınırlı sayıda önceki hücreye bağlıysa, artık kullanılmayacak hücreler atılabilir. Sırt çantası tablosunda her satır yalnız bir önceki satıra bağlıdır; bu yüzden iki boyutlu tablo tek bir satıra indirilebilir. Bu kazancın bir bedeli vardır: atılan hücreler, çözümün geri okunması için gerekebilir. Fibonacci'de geri okunacak bir seçim olmadığı için kayıp yoktur.

8.30/1 sırt çantası

8.3.1Problem

Bir yolcu, taşıyabileceği ağırlık sınırlı bir çantaya eşya yerleştirecektir. Her eşyanın bir ağırlığı ve bir değeri vardır. Amaç, ağırlık sınırını aşmadan çantadaki toplam değeri en büyük yapmaktır. Eşyalar bölünemez: bir eşya ya bütünüyle çantaya girer ya da hiç girmez. Problemin adındaki 0/1 bu iki seçeneği anlatır.

8.3.2Kaba kuvvet ve açgözlü seçim neden yetmez?

Problemin en doğrudan çözümü bütün seçimleri denemektir. Her eşya için iki seçenek vardır; n eşya için 2ⁿ alt küme oluşur. n = 50 için bu sayı 2⁵⁰ ≈ 1,13 · 10¹⁵'tir. Saniyede bir milyar alt küme denense bile on üç günden uzun sürer. Kaba kuvvet ancak çok küçük girdilerde kullanılabilir.

İkinci akla gelen yol açgözlü seçimdir. Eşyalar değer/ağırlık oranına göre sıralanır ve oranı en yüksek olandan başlayarak sığan her eşya alınır. Bu yöntem bazen doğru cevabı verir, ama her zaman vermez.

Açgözlü seçim, eşyalar bölünebiliyorsa optimaldir. Bu probleme kesirli sırt çantası denir. Örnekte üçüncü eşyanın üçte ikisi alınabilseydi açgözlü algoritma 60 + 100 + 80 = 240 ₺ ile optimal sonuca ulaşırdı. 0/1 durumunda ise bir eşyayı almak, sonraki seçenekleri değiştirir. Hangi seçimin daha iyi olduğunu bilmenin tek yolu iki seçeneği de denemektir. Bu deneme her eşyada iki kola ayrılan bir özyineleme demektir; kollar ise aynı alt problemlerde buluşur. Örtüşen alt problemler ve optimal alt yapı birlikte dinamik programlamanın kapısını açar.

8.3.3Durum ve bağıntı

Tasarım adımlarının ilki son karara bakmaktır. Eşyalar 1'den n'ye numaralansın. Optimal çözümde son eşya için yalnız iki seçenek vardır: ya alınmıştır ya alınmamıştır. Alınmamışsa geriye kalan problem, ilk n − 1 eşyayı aynı kapasiteyle en iyi biçimde yerleştirmektir. Alınmışsa değeri vₙ kazanılmıştır ve geriye kalan problem, ilk n − 1 eşyayı W − wₙ kapasiteyle en iyi biçimde yerleştirmektir. İki durumda da geriye kalan problem aynı türdendir. Değişen yalnız iki sayıdır: eşya sayısı ve kapasite. Durum bu iki sayıyla tanımlanır.

Bağıntının iki kolu iki kararın değeridir. Almama kolunda kapasite aynı kalır ve önceki eşyalarla elde edilen en iyi değer kullanılır: K[i − 1][c]. Alma kolunda vᵢ kazanılır, kalan c − wᵢ kapasite önceki eşyalarla en iyi biçimde doldurulur: vᵢ + K[i − 1][c − wᵢ]. Eşya sığmıyorsa alma kolu yoktur. Taban durumları da sezgiyle uyumludur: hiç eşya yoksa ya da kapasite sıfırsa değer 0'dır.

Şekil 8.8 hesaplama sırasını da belirler. Bir hücre yalnız bir üst satıra bakar. O hâlde tablo satır satır, yukarıdan aşağı doldurulursa her hücreye gelindiğinde ihtiyaç duyduğu hücreler hazır olur. Bir satırın içinde sütunların sırası önemli değildir.

8.3.4Tablonun doldurulması

Bağıntı doğrudan iki iç içe döngüye çevrilir. Kod eşyaları 0'dan başlayan dizilerde tutar; tablonun i. satırı ise i. eşyayı, yani dizideki v[i - 1] ve w[i - 1] öğelerini kullanır.

int sirtCantasi(int[] v, int[] w, int W) {
  int n = v.length;
  int[][] K = new int[n + 1][W + 1];
  for (int i = 1; i <= n; i++)
    for (int c = 1; c <= W; c++) {
      int vi = v[i - 1], wi = w[i - 1];
      if (wi > c)            // sığmaz
        K[i][c] = K[i - 1][c];
      else                   // alma / al
        K[i][c] = Math.max(K[i - 1][c],
                    vi + K[i - 1][c - wi]);
    }
  return K[n][W];
}

new int[n + 1][W + 1] bütün hücreleri 0 ile başlatır; böylece 0. satır ve 0. sütun taban durumlarını kendiliğinden sağlar. Döngüler bu yüzden 1'den başlar. İçteki if eşyanın sığıp sığmadığını sınar. Sığmazsa üstteki değer kopyalanır; sığarsa iki kolun büyüğü yazılır.

Örnek olarak dört eşya ve W = 6 alınsın. Eşyalar (değer, ağırlık) biçiminde (5, 4), (4, 3), (3, 2) ve (2, 1)'dir. Tablo (n + 1) × (W + 1) = 5 × 7 boyutludur. Tablo 8.6 doldurulmuş tabloyu verir.

Satırlar tek tek izlensin.

• Satır 1 (5, 4). c = 1, 2, 3 için eşya sığmaz; üstteki 0 kopyalanır. c = 4'te max(0, 5 + K[0][0]) = 5. c = 5 ve 6'da da aynı hesap 5 verir; tek eşya bir kez alınabilir.
• Satır 2 (4, 3). c = 3'te ikinci eşya ilk kez sığar: max(0, 4 + K[1][0]) = 4. c = 4'te almama kolu 5, alma kolu 4 + K[1][1] = 4'tür; 5 kalır. c = 5 ve 6'da da 5 kalır: iki eşya birlikte 7 kg eder, sığmaz.
• Satır 3 (3, 2). c = 2'de 3 yazılır. c = 3'te almama 4, alma 3 + K[2][1] = 3'tür; 4 kalır. c = 5'te alma kolu 3 + K[2][3] = 3 + 4 = 7 olur ve almama kolundaki 5'i geçer. c = 6'da 3 + K[2][4] = 3 + 5 = 8 yazılır.
• Satır 4 (2, 1). En hafif eşya her sütunda sığar. c = 1: max(0, 2) = 2. c = 3: max(4, 2 + K[3][2]) = max(4, 5) = 5. c = 4: max(5, 2 + 4) = 6. c = 5: max(7, 2 + 5) = 7; iki kol eşittir ve almama korunur. c = 6: max(8, 2 + K[3][5]) = max(8, 9) = 9.

Cevap sağ alt hücrededir: K[4][6] = 9. Tablonun her satırı bir soruyu cevaplar: “yalnız ilk i eşya varken her kapasite için en iyi değer nedir?” Örneğin 3. satır, (5, 4), (4, 3) ve (3, 2) eşyalarıyla 5 kg'lık bir çantanın en çok 7 ₺ değer taşıyabileceğini söyler.

8.3.5Geri okuma

Tablo yalnız en büyük değeri verir. Hangi eşyaların seçildiği tablonun içinde saklıdır ve sondan başa doğru okunarak bulunur. Bu işleme geri okuma (traceback) denir.

Kural basittir. K[i][c] ≠ K[i − 1][c] ise değer ancak i. eşyayı alarak artmıştır; eşya alınmıştır ve kapasite c ← c − wᵢ olur. Eşitse eşya alınmadan da aynı değer elde edilebilir; eşya alınmamış sayılır ve c değişmez. Her iki durumda bir üst satıra çıkılır.

Geri okuma her satırda bir karşılaştırma yapar; süresi O(n)'dir. Aynı kural koda kolayca çevrilir. Aşağıdaki metot doldurulmuş tabloyu ve ağırlıkları alır, seçilen eşyaların numaralarını (1'den başlayarak) döndürür.

List<Integer> geriOku(int[][] K, int[] w, int W) {
  List<Integer> secilen = new ArrayList<>();
  int c = W;
  for (int i = K.length - 1; i >= 1; i--)
    if (K[i][c] != K[i - 1][c]) {   // değer arttı: eşya i alındı
      secilen.add(0, i);
      c -= w[i - 1];
    }
  return secilen;
}

Metot örnek tablo için [2, 3, 4] döndürür. Eşitlik durumunda eşyanın alınmamış sayılması, birden çok optimal çözüm varsa bunlardan birinin seçilmesi demektir. Örneğin K[4][5] = 7 hücresinde iki kol eşitti; o hücreden başlayan bir geri okuma 4. eşyayı almaz ve (4, 3) ile (3, 2) eşyalarını bulur.

8.3.6Karmaşıklık ve sözde-polinom süre

Tablo (n + 1)(W + 1) hücrelidir ve her hücre sabit sürede hesaplanır. Süre ve bellek O(n · W)'dir. İlk bakışta bu bir polinom süre gibi görünür. Ama burada önemli bir incelik vardır.

Bir algoritmanın süresi, girdinin boyutuna, yani girdiyi yazmak için gereken bit sayısına göre ölçülür. n eşyayı yazmak için n ile orantılı yer gerekir. Oysa W sayısını yazmak için yalnız log₂ W bit gerekir. W = 10⁹ otuz bitle yazılır, ama tablo 10⁹ sütun ister. W'nin bit sayısı bir artınca W'nin değeri ve tablonun genişliği iki katına çıkar. Süre, girdi uzunluğuna göre üsteldir.

Bu ayrımın pratik bir sonucu vardır. 0/1 sırt çantası NP-zor bir problemdir; bilinen hiçbir algoritma onu her girdide polinom sürede çözemez. DP bu gerçeği değiştirmez. Yalnız W küçükken, örneğin birkaç bin ya da birkaç milyon olduğunda, problemi pratikte çözülebilir kılar. Ağırlıklar gram cinsinden ve kapasite birkaç ton ise tablo milyarlarca sütuna ulaşır ve kurulamaz.

8.3.7Tek boyutlu tablo

i. satır yalnız i − 1. satırı kullanır. Bu gözlem belleği O(W)'ye indirir: tek boyutlu bir dp dizisi tutulur. Eşyalar sırayla işlenir; her eşyada dizi, eski satırdan yeni satıra yerinde güncellenir.

int[] dp = new int[W + 1];
for (int i = 0; i < n; i++)
  for (int c = W; c >= w[i]; c--)
    dp[c] = Math.max(dp[c],
                     v[i] + dp[c - w[i]]);
return dp[W];

Kodun en önemli ayrıntısı iç döngünün yönüdür: kapasite büyükten küçüğe gezilir. Nedeni şudur. dp[c] güncellenirken okunan dp[c - w[i]], eski satırın değeri olmalıdır; yani i. eşya henüz hesaba katılmamış olmalıdır. Büyükten küçüğe gezildiğinde c − wᵢ < c olan hücreler bu turda henüz güncellenmemiştir ve eski değeri taşır. Küçükten büyüğe gezilseydi dp[c - w[i]] bu turda zaten güncellenmiş olurdu; aynı eşya iki kez alınabilirdi. Döngünün alt sınırı c >= w[i], sığmayan kapasiteleri hiç ziyaret etmez. Bu hücrelerde değer değişmez; eski satırdan kopyalanmış sayılır.

Her satır, iki boyutlu tablonun aynı numaralı satırıyla birebir aynıdır. Örneğin eşya 0 işlenirken dp[6], dp[5] ve dp[4] sırayla 5 olur. Bu sırada okunan dp[2], dp[1] ve dp[0] henüz değişmemiştir ve 0'dır; eşya bir kez alınır. Sonuç dp[6] = 9'dur. Kodda eşyalar 0'dan numaralandığı için seçim “eşya 1, 2, 3” diye okunur: 4 + 3 + 2. İki boyutlu tablonun numaralandırmasıyla bu, eşya 2, 3 ve 4'tür.

Tek boyutlu sürümün bir bedeli vardır. Ara satırlar silindiği için geri okuma artık yapılamaz. Seçilen eşyalar gerekiyorsa her eşya ve kapasite için kararı saklayan ayrı bir boolean[][] dahil tablosu tutulur. Bu tablo da n · W boyutludur, ama int yerine boolean sakladığı için daha az yer kaplar.

8.3.8Yukarıdan aşağı çözüm

Aynı bağıntı bellekleme ile de yazılabilir. Burada alt problem “i. eşyadan itibaren, c kapasiteyle elde edilebilecek en büyük değer” olarak tanımlanır; eşyalar baştan sona taranır. Tanım tablolamadakinin aynadaki görüntüsüdür ve aynı cevabı verir.

Integer[][] bellek;   // bellek[i][c]: i. eşyadan itibaren, c kapasiteyle en iyi

int f(int[] v, int[] w, int i, int c) {
  if (i == v.length) return 0;              // eşya kalmadı
  if (bellek[i][c] != null) return bellek[i][c];
  int sonuc = f(v, w, i + 1, c);            // alma
  if (w[i] <= c)                            // al
    sonuc = Math.max(sonuc, v[i] + f(v, w, i + 1, c - w[i]));
  bellek[i][c] = sonuc;
  return sonuc;
}

int sirtCantasiBellek(int[] v, int[] w, int W) {
  bellek = new Integer[v.length][W + 1];
  return f(v, w, 0, W);
}

Önbellek Integer[][] türündedir. Integer nesneleri null ile başlar ve null “henüz hesaplanmadı” anlamına gelir. int[][] kullanılsaydı 0 değeri hem “hesaplanmadı” hem de “gerçek cevap 0” anlamına gelirdi; cevabı 0 olan durumlar tekrar tekrar hesaplanırdı. Metot önce taban durumuna bakar: eşya kalmadıysa değer 0'dır. Sonra önbelleğe bakar. Değer yoksa almama kolunu hesaplar, eşya sığıyorsa alma kolunu da hesaplar ve büyüğünü saklar.

Örnekte sirtCantasiBellek(v, w, 6) 9 döndürür. Önbellek 4 × 7 = 28 hücrelidir, ama bunlardan yalnız 12'si doldurulur. Kökten başlayan özyineleme yalnız gerçekten ulaşılabilen kapasitelere iner: 0. eşyada yalnız c = 6; 1. eşyada c = 6 ve 2; 2. eşyada 6, 3 ve 2; 3. eşyada 6, 4, 3, 1, 2 ve 0. Ağırlıklar büyük ve az sayıdaysa bu fark daha da büyür. Örneğin bütün ağırlıklar 1000'in katıysa yalnız 1000'in katı olan kapasitelere inilir.

8.4Sınırsız sırt çantası

8.4.1Problem ve bağıntı

Bazı problemlerde eşyalar tek tek değil, türler hâlinde verilir ve her türden istenildiği kadar alınabilir. Bir kargo firması aynı boyutta istediği kadar koli yükleyebilir; bir kesme makinesi aynı uzunlukta istediği kadar parça kesebilir. Bu probleme sınırsız sırt çantası (unbounded knapsack) denir. Geri kalan her şey 0/1 sırt çantasıyla aynıdır: kapasite aşılmadan toplam kâr en büyük yapılır.

Durum yine iki sayıyla tanımlanır, ama bu kez eşya türleri 0'dan numaralanır: dp[i][c], 0'dan i'ye kadar olan eşya türleri ve c kapasite ile elde edilebilecek en büyük kârdır. Son kararın yapısı da benzer. i. türden hiç alınmazsa cevap dp[i − 1][c]'dir. En az bir tane alınırsa kârᵢ kazanılır ve geriye c − ağırlıkᵢ kapasite kalır. Bu kalan kapasitede aynı türden yine alınabilir. Bu yüzden kalan problem i − 1. satırda değil, yine i. satırdadır.

dp[i][c] = max( dp[i − 1][c],   kârᵢ + dp[i][c − ağırlıkᵢ] )    (ağırlıkᵢ ≤ c ise)

Eşya sığmıyorsa yalnız ilk kol kalır. Satır indisi 0'dan başladığı için dp[−1][c] = 0 kabul edilir: hiç eşya türü yokken kâr 0'dır. 0/1 sırt çantasıyla tek fark, “alırsam” kolunun baktığı satırdır.

Bu fark, hesaplama sırasını da etkiler. Hücre artık aynı satırda soldaki bir hücreye bağlıdır. Satır soldan sağa doldurulursa o hücre hazırdır. Satırlar yine yukarıdan aşağı gezilir.

8.4.2Tablonun doldurulması

Örnek olarak dört eşya türü alınsın: kârlar [15, 50, 60, 90], ağırlıklar [1, 3, 4, 5], kapasite 8. Tablo 4 × 9 boyutludur. İlk satırda yalnız 0. tür (15 kâr, 1 kg) kullanılabilir.

Satırların hesabı şöyle ilerler.

• Satır 0. Kapasite 0 sütunu 0'dır. c = 1'de tek seçenek 0. türü almaktır: 15 + dp[0][0] = 15. c = 2'de 15 + dp[0][1] = 30: aynı satır tekrar kullanıldı, yani 0. türden iki tane alındı. Satır böylece 15'in katlarıyla dolar: dp[0][c] = 15c.
• Satır 1 (50, 3 kg). c = 1, 2'de eşya sığmaz, üst satır kopyalanır. c = 3: max(45, 50 + dp[1][0]) = 50. c = 4: max(60, 50 + dp[1][1]) = 65. c = 6: max(90, 50 + dp[1][3]) = max(90, 100) = 100; burada dp[1][3], kendisi de 1. türü içeren bir hücredir. 100, iki tane 50'lik eşyadır. c = 8: max(120, 50 + dp[1][5]) = 130.
• Satır 2 (60, 4 kg). 60'lık eşya hiçbir sütunda üst satırı geçemez. Örneğin c = 8'de 60 + dp[2][4] = 60 + 65 = 125 < 130. Satır, üst satırın kopyasıdır.
• Satır 3 (90, 5 kg). c = 5: max(80, 90 + 0) = 90. c = 6: max(100, 90 + dp[3][1]) = 105. c = 7: max(115, 90 + 30) = 120. c = 8: max(130, 90 + dp[3][3]) = max(130, 140) = 140.

Cevap dp[3][8] = 140'tır. Geri okuma 0/1'deki gibi yapılır, tek farkla: bir tür alındığında aynı satırda kalınır. dp[3][8] = 140 ≠ dp[2][8] = 130 olduğu için 3. türden bir tane alınmıştır ve c = 3 olur. dp[3][3] = dp[2][3] = 50 olduğundan yukarı çıkılır. dp[2][3] = dp[1][3] yine yukarı. dp[1][3] = 50 ≠ dp[0][3] = 45: 1. türden bir tane alınmıştır ve c = 0 olur. Çözüm, bir tane 90'lık (5 kg) ve bir tane 50'lik (3 kg) eşyadır.

8.4.3Tek boyutlu çözüm ve döngü yönü

Sınırsız sırt çantasında satırlar tamamen birleştirilebilir. Her türden istenildiği kadar alınabildiğine göre, c kapasitenin en iyi değeri son alınan eşyaya bakılarak yazılabilir. Son alınan eşya j ise kalan kapasite c − wⱼ'dir ve orada da bütün türler serbesttir:

dp[c] = max { dp[c − wⱼ] + vⱼ : wⱼ ≤ c },    dp[0] = 0

static int sinirsizSirtCantasi(int[] w, int[] v, int W) {
  int[] dp = new int[W + 1];       // dp[c]: c kapasiteyle en iyi
  for (int c = 1; c <= W; c++)
    for (int j = 0; j < w.length; j++)
      if (w[j] <= c)
        dp[c] = Math.max(dp[c], dp[c - w[j]] + v[j]);
  return dp[W];
}

Dış döngü kapasiteyi 1'den W'ye kadar artırır, iç döngü her türü dener. dp[c] hesaplanırken daha küçük bütün kapasiteler hazırdır. Örnek için sonuç dizisi dp = [0, 15, 30, 50, 65, 90, 105, 120, 140]'tır; iki boyutlu tablonun son satırının aynısıdır. Süre O(n · W), bellek O(W)'dir.

Tek boyutlu 0/1 sırt çantasıyla bu kod arasındaki ilişki öğreticidir. İkisi de tek bir dizide şu güncellemeyi yapar: dp[c] = max(dp[c], v + dp[c - w]). Fark, döngü yönündedir. Kapasite küçükten büyüğe gezilirse dp[c - w] bu turda zaten güncellenmiştir ve eşyayı içerebilir; eşya tekrar alınabilir, sonuç sınırsız sırt çantasıdır. Kapasite büyükten küçüğe gezilirse dp[c - w] eski değeri taşır; eşya en çok bir kez alınır, sonuç 0/1'dir. Aynı tek satırlık güncelleme, yalnız döngünün yönüyle iki farklı problemi çözer.

8.4.4Kod izleme

Tek boyutlu kodun izlemesi her kapasitede hangi seçeneğin kazandığını gösterir. Aşağıdaki sürüm sunumdaki izleme kodudur ve yukarıdakiyle aynı işi yapar.

static int sinirsizSirtCantasi(
    int[] w, int[] v, int W) {
  int[] dp = new int[W + 1];  // dp[c]
  for (int c = 1; c <= W; c++)
    for (int j = 0; j < w.length; j++)
      if (w[j] <= c)
        dp[c] = Math.max(dp[c],
                  dp[c - w[j]] + v[j]);
  return dp[W];
}

c = 2 satırı sınırsızlığın kaynağını gösterir: dp[1] bu turda güncellenmişti ve 0. türü bir kez içeriyordu; ona yine 15 eklenince aynı türden iki tane alınmış olur. Son satırda iki aday 140'a ulaşır: dp[5] + 50 ve dp[3] + 90. İkisi de aynı seçimi anlatır: bir tane 50'lik (3 kg) ve bir tane 90'lık (5 kg). Aynı 140'ı veren 15 + 15 + 50 + 60 seçimi ise 9 kg'dır ve çantaya sığmaz. Tablo bütün birleşimleri tek tek saymadan, O(n · W) sürede denemiş olur.

8.5Alt küme toplamı

8.5.1Problem ve bağıntı

Bir dizi tam sayı ve bir hedef değer verilsin. Toplamı tam olarak hedefe eşit olan bir alt küme var mıdır? Bu soru bir optimizasyon değil, karar problemidir: cevap evet ya da hayırdır. Problemin adı alt küme toplamıdır (subset sum).

Son karar yine bir öğenin seçilip seçilmediğidir. Son öğe seçilmezse soru, ilk n − 1 öğeyle aynı hedefin elde edilip edilemeyeceğidir. Seçilirse hedef öğe kadar azalır. Durum iki sayıyla tanımlanır ve değeri bir mantıksal değerdir.

Sütun 0 her satırda doğrudur, çünkü boş küme toplam 0'ı verir. Satır 0'da sıfırdan büyük hiçbir toplam elde edilemez. Bağıntı, 0/1 sırt çantasının bağıntısıyla aynı biçimdedir: sırt çantasındaki max yerine mantıksal veya, değerin toplanması yerine de yalnız ulaşılabilirlik vardır. Alt küme toplamı, sırt çantasının “değer = ağırlık” özel durumu olarak da görülebilir. Her öğenin değeri ağırlığına eşit olsun ve kapasite hedef olsun. Sırt çantasının cevabı hedefe eşitse istenen alt küme vardır.

8.5.2Tablo ve geri okuma

Dizi a = 10, 0, 5, 8, 6, 2, 4 ve hedef 15 olsun. Tablo 8 × 16 boyutludur. Her satırı bütün hücreleriyle yazmak yerine, o satırda ulaşılabilen toplamları listelemek daha okunaklıdır. Bir satır, bir önceki satırın bütün toplamlarını korur; ayrıca o toplamların her birine aᵢ eklenerek yeni toplamlar ekler (hedefi aşanlar dışarıda kalır).

2. satır ilginçtir: 0 eklemek hiçbir toplamı değiştirmez, satır üst satırın kopyasıdır. Hedef 15 ilk kez 3. satırda ulaşılabilir olur: 10 ve 5 birlikte. Son hücre dp[7][15] doğrudur; cevap evettir.

Geri okuma son hücreden başlar. dp[i − 1][j] doğruysa aᵢ olmadan da toplam j kurulabilir; öğe seçilmez ve yukarı çıkılır. Yanlışsa toplam ancak aᵢ ile kurulabilir; öğe seçilir ve j ← j − aᵢ olur.

• dp[7][15] = dp[6][15] = doğru: 4 seçilmez. Aynı gerekçeyle 2, 6 ve 8 de seçilmez; 4. satıra kadar çıkılır.
• dp[3][15] doğru ama dp[2][15] yanlış: 5 seçilir; j = 15 − 5 = 10.
• dp[2][10] = dp[1][10] = doğru: 0 seçilmez.
• dp[1][10] doğru ama dp[0][10] yanlış: 10 seçilir; j = 0 ve okuma biter.

Bu dizide toplamı 15 olan altı alt küme vardır: {10, 5}, {5, 8, 2}, {5, 6, 4} ve bunların her birine 0 eklenmiş hâlleri. Geri okuma yalnız birini verir. Hangisini vereceği, eşitlik kuralına bağlıdır. Buradaki kural “öğe olmadan da olabiliyorsa seçme” olduğu için okuma, dizinin başındaki öğeleri kullanan çözüme yönelir.

8.5.3Kod ve analiz

boolean altKume(int[] a, int hedef) {
  int n = a.length;
  boolean[][] dp = new boolean[n + 1][hedef + 1];
  for (int i = 0; i <= n; i++)
    dp[i][0] = true;           // boş küme
  for (int i = 1; i <= n; i++) {
    int x = a[i - 1];
    for (int j = 1; j <= hedef; j++)
      dp[i][j] = dp[i - 1][j]  // x alınmaz
        || (x <= j && dp[i - 1][j - x]);
  }
  return dp[n][hedef];
}

Java'da yeni bir boolean dizisi false ile başlar. İlk döngü sütun 0'ı doğru yapar. İç döngüdeki ifade bağıntının birebir karşılığıdır. || işlecinin kısa devre davranışı burada işe yarar: dp[i - 1][j] doğruysa sağ taraf hiç hesaplanmaz. Sağ taraftaki x <= j sınaması da &&'nin kısa devresi sayesinde j - x negatifken diziye erişilmesini önler.

Süre ve bellek O(n · hedef)'tir. Bu da sözde-polinom bir süredir: hedef büyükse tablo kurulamaz. Alt küme toplamı NP-tam bir problemdir; DP onu yalnız hedef küçükken pratik kılar. Bellek, 0/1 sırt çantasındaki gibi tek boyuta indirilebilir. Bunun için j büyükten küçüğe gezilir ki her öğe en çok bir kez kullanılsın.

8.5.4Kod izleme

Kodun satır satır davranışı daha küçük bir örnekte izlensin: altKume({3, 34, 4, 12, 5, 2}, 9). Tablo (n + 1) × (hedef + 1) = 7 × 10 = 70 hücrelidir.

Metot true döndürür. Toplamı 9 olan iki alt küme vardır: {4, 5} ve {3, 4, 2}. Geri okuma dp[6][9]'dan başlar; dp[5][9] doğru olduğu için 2 seçilmez. dp[4][9] yanlış olduğu için 5 seçilir ve j = 4 olur. 12 seçilmez; dp[2][4] yanlış olduğu için 4 seçilir ve j = 0 olur. Bulunan alt küme {4, 5}'tir. Aynı dizide hedef 30 sorulsaydı cevap hayır olurdu: 34 hiçbir zaman kullanılamaz, öteki öğelerin toplamı ise 3 + 4 + 12 + 5 + 2 = 26 < 30'dur.

8.6En uzun artan alt dizi

8.6.1Alt dizi ve alt dizgi

Notun geri kalanındaki üç problem, bir dizinin parçalarıyla ilgilidir. Parça sözcüğü iki farklı anlamda kullanılır ve bu iki anlamın karıştırılması bu konudaki hataların başında gelir.

“GXTXAYB” dizgisinde G, T, A, B öğeleri sırasıyla 0, 2, 4 ve 6. konumlarda geçer. Göreli sıraları korunduğu için “GTAB” bir alt dizidir. Öğeler bitişik olmadığı için alt dizgi değildir. Buna karşılık “XAY” 3, 4 ve 5. konumlarda bitişik geçer; hem alt dizgi hem alt dizidir. Her alt dizgi aynı zamanda bir alt dizidir; tersi doğru değildir. n uzunluklu bir dizinin 2ⁿ alt dizisi, ama yalnız n(n + 1)/2 boş olmayan bitişik parçası vardır.

Örnek olarak 0'dan 15'e kadar sayıların şu dizilişi alınsın: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. Bu dizinin bir LIS'i 0, 2, 6, 9, 11, 15'tir ve uzunluğu 6'dır.

Aynı dizinin başka LIS'leri de vardır. Örneğin 0, 4, 6, 9, 13, 15 ve 0, 2, 6, 9, 13, 15 de 6 uzunlukta artan alt dizilerdir; bu dizide toplam dört farklı LIS vardır. LIS tek olmak zorunda değildir, ama uzunluğu tektir. DP önce bu uzunluğu bulur; dizinin kendisi gerekiyorsa ek bilgiyle geri okunur.

8.6.2O(n²) dinamik programlama

Doğru durumu seçmek bu problemin anahtarıdır. “İlk i öğenin LIS uzunluğu” iyi bir durum değildir: bu değeri bilmek, i + 1. öğenin o diziyi uzatıp uzatamayacağını söylemez, çünkü dizinin hangi sayıyla bittiği bilinmez. Durum, bitiş noktasını sabitlemelidir.

Bağıntının anlamı şudur. a[i]'de biten artan bir alt dizide a[i]'den önceki öğe, solda yer alan ve a[i]'den küçük bir a[j]'dir. O öğede biten en uzun dizinin sonuna a[i] eklenir. Bütün adaylar denenir ve en uzunu seçilir. Önünde daha küçük öğe yoksa a[i] tek başına 1 uzunluklu bir dizidir. Cevap son hücre değildir: LIS dizinin herhangi bir yerinde bitebilir.

Tablo 8.13 16 öğeli örneğin bütün dp değerlerini verir. “Önceki” satırı, en büyük dp[j]'yi veren j'dir; eşitlikte soldaki ilk j seçilmiştir.

Birkaç hücrenin hesabı ayrıntılı yazılsın. i = 3'te a[3] = 12'dir; soldaki adaylar 0, 8 ve 4'tür ve dp değerleri 1, 2, 2'dir. En büyüğü j = 1'deki 2'dir: dp[3] = 3 (0, 8, 12). i = 9'da a[9] = 9'dur; adaylar 0, 8, 4, 2, 6 ve 1'dir. Bunlardan en uzun diziyle biteni 6'dır (dp[6] = 3): dp[9] = 4 (0, 4, 6, 9). i = 15'te a[15] = 15 bütün öğelerden büyüktür; adayların en büyük dp değeri 5'tir ve ilk kez j = 11'de görülür: dp[15] = 6.

Dizinin kendisi önceki indislerden geri okunur. En büyük dp değerinin bulunduğu indisten başlanır ve önceki indislere atlanır: 15 → 11 → 9 → 6 → 2 → 0. Bu indislerdeki öğeler sondan başa 15, 13, 9, 6, 4, 0'dır; ters çevrilince 0, 4, 6, 9, 13, 15 elde edilir. Bu, Şekil 8.18'deki LIS'ten farklıdır ama aynı uzunluktadır. Farkın nedeni eşitlik kuralıdır: i = 15'te hem j = 11 hem j = 13 dp değeri 5 olan adaylardır ve ilk görülen seçilir.

8.6.3Kod ve izleme

static int lis(int[] a) {
  int n = a.length, enUzun = 0;
  int[] dp = new int[n];
  for (int i = 0; i < n; i++) {
    dp[i] = 1;               // tek başına
    for (int j = 0; j < i; j++)
      if (a[j] < a[i] && dp[j] + 1 > dp[i])
        dp[i] = dp[j] + 1;   // uzat
    enUzun = Math.max(enUzun, dp[i]);
  }
  return enUzun;
}

Dış döngü her i için önce dp[i] = 1 yazar: öğe tek başına bir dizidir. İç döngü soldaki her j'yi dener. a[j] < a[i] koşulu dizinin artan olmasını, dp[j] + 1 > dp[i] koşulu ise yalnız daha uzun bir dizinin kabul edilmesini sağlar. Kesin büyüktür işareti eşitlikte ilk j'yi korur. Her turun sonunda enUzun güncellenir. İç döngü toplam 0 + 1 + … + (n − 1) = n(n − 1)/2 kez döner; süre O(n²), bellek O(n)'dir.

Kodu daha kısa bir dizide izlemek, satırların etkisini açıkça gösterir: lis({5, 2, 8, 6, 3, 6, 9, 7}).

i = 5 satırı durumun neden “a[i]'de biten” diye tanımlandığını gösterir. a[5] = 6'dan küçük üç öğe vardır: 5, 2 ve 3. 5 ve 2 tek başına birer dizinin sonudur (dp = 1). 3 ise 2, 3 dizisinin sonudur (dp = 2). 6, en uzun zinciri uzatır: 2, 3, 6. Son öğe 7'nin dp değeri 4'tür ve enUzun ile eşittir; bu bir rastlantıdır. Dizinin sonuna 1 eklenseydi son hücre 1, cevap yine 4 olurdu.

Diziyi kurmak için her öğenin önceki indisi saklanır. Aşağıdaki metot lis'e bir onceki dizisi ekler ve en uzun dizinin bittiği yerden geriye doğru zinciri izler.

List<Integer> lisDizi(int[] a) {
  int n = a.length, enSon = 0;
  int[] dp = new int[n], onceki = new int[n];
  for (int i = 0; i < n; i++) {
    dp[i] = 1; onceki[i] = -1;
    for (int j = 0; j < i; j++)
      if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1; onceki[i] = j;
      }
    if (dp[i] > dp[enSon]) enSon = i;
  }
  LinkedList<Integer> lis = new LinkedList<>();
  for (int i = enSon; i != -1; i = onceki[i])
    lis.addFirst(a[i]);
  return lis;
}

Metot örnek dizi için [2, 3, 6, 9], 16 öğeli dizi için [0, 4, 6, 9, 13, 15] döndürür. LinkedList.addFirst, geri okumanın sondan başa ilerlemesini dengeler: öğeler başa eklendiği için liste doğru sırada oluşur.

8.6.4Aktif listeler

O(n²) algoritma her öğede soldaki bütün öğelere bakar. Daha hızlı bir yöntem için şu gözlem kullanılır: aynı uzunlukta iki artan dizi varsa, sonu küçük olan her zaman daha iyidir. Gelecekte gelecek bir sayı, sonu büyük olanı uzatabiliyorsa sonu küçük olanı da uzatabilir; tersi doğru değildir. O hâlde her uzunluk için yalnız bir liste saklamak yeter: o uzunluktaki artan listeler arasında sonu en küçük olan. Bu listelere aktif listeler denir.

Yeni bir x öğesi geldiğinde üç durum vardır:

1. x bütün aktif listelerin sonlarından küçükse 1 uzunluklu yeni bir liste [x] başlar ve eski 1 uzunluklu listenin yerini alır.
2. x bütün sonlardan büyükse en uzun liste kopyalanır, sonuna x eklenir; liste sayısı bir artar.
3. Aksi hâlde sonu x'ten küçük olan en uzun liste bulunur, kopyalanıp sonuna x eklenir. Yeni liste, aynı uzunluktaki eski listenin yerini alır; eski listenin sonu daha büyük olduğu için artık gereksizdir.

Dizi bittiğinde liste sayısı LIS uzunluğudur ve en uzun aktif liste bir LIS'tir. Yöntemin doğruluğu aşağıdaki değişmeze dayanır.

Teoremin iki önemli sonucu vardır. Birincisi, yeni öğenin hangi listeyi uzatacağı sıralı bir dizide arama yapılarak bulunabilir: sonlar dizisi artandır ve aranan yer, sonu x'ten büyük ya da eşit olan ilk listedir. Bu ikili aramayla O(log n) sürede bulunur. İkincisi, listelerin kendilerini saklamaya gerek yoktur; yalnız sonlarını saklamak yeter.

8.6.5O(n log n) kod

Aşağıdaki kod aktif listelerin yalnız sonlarını saklar. son[k], uzunluğu k + 1 olan artan alt diziler arasında en küçük son öğedir. son[0..uz − 1] her zaman artandır; başta uz = 0'dır.

static int lisHizli(int[] a) {
  int[] son = new int[a.length];
  int uz = 0;                // aktif liste sayısı
  for (int x : a) {
    int alt = 0, ust = uz;   // son[alt] >= x ilk yer
    while (alt < ust) {
      int orta = (alt + ust) / 2;
      if (son[orta] < x) alt = orta + 1;
      else ust = orta;
    }
    son[alt] = x;            // yerine koy / uzat
    if (alt == uz) uz++;
  }
  return uz;
}

Her x için while döngüsü, son[alt] >= x koşulunu sağlayan ilk konumu ikili aramayla bulur. Arama aralığı [alt, ust) yarı açıktır; ust başlangıçta uz'dur. son[orta] < x ise aranan yer ortanın sağındadır; değilse orta da aday olabilir ve aralık sola daraltılır. Döngü bittiğinde alt, x'in yazılacağı yerdir. alt == uz ise x bütün sonlardan büyüktür ve liste sayısı artar; aksi hâlde x daha büyük bir sonun yerini alır. Bu son durum, aktif listeler yönteminin üçüncü kuralıdır: aynı uzunluktaki liste artık daha küçük bir sayıyla biter.

Metot 4 döndürür; O(n²) algoritmayla aynı sonuçtur. Her öğe için ikili arama en çok ⌈log₂(uz + 1)⌉ karşılaştırma yapar. Toplam süre O(n log n), ek bellek O(n)'dir. Bir milyon öğelik bir dizide O(n²) algoritma yaklaşık 5 · 10¹¹ karşılaştırma yaparken bu yöntem yirmi milyon civarında karşılaştırmayla biter.

son dizisinin içeriği konusunda dikkatli olmak gerekir. Bu dizi bir LIS olmak zorunda değildir. 16 öğeli örnekte işlem bitince son = [0, 1, 3, 7, 11, 15] olur. Uzunluk doğrudur (6), ama bu sayılar dizide bu sırayla geçmez: 7, 14. konumdadır, 11 ise 13. konumda, yani 7'den öncedir. Dizinin kendisi gerekiyorsa her öğe son'a yazıldığında, solundaki konumda (alt − 1) bulunan öğenin indisi önceki indis olarak saklanır; geri okuma O(n²) sürümdeki gibi yapılır.

8.7En uzun ortak alt dizgi

8.7.1Problem ve bağıntı

İki dizgi verilsin. İkisinde de bitişik olarak geçen en uzun parça hangisidir? Bu probleme en uzun ortak alt dizgi (longest common substring) denir. İntihal denetiminde iki metnin birebir aynı olan en uzun bölümü, sürüm karşılaştırmada iki dosyanın ortak bloğu bu soruyla bulunur.

Örnek olarak “abdca” ve “cbda” dizgileri alınsın. Ortak alt dizgiler “a”, “b”, “d”, “c” ve “bd”'dir. En uzunu “bd”'dir ve uzunluğu 2'dir.

Kaba kuvvet yöntemi, birinci dizginin bütün alt dizgilerini ikinci dizgide arar. m uzunluklu bir dizginin O(m²) alt dizgisi vardır; her biri n uzunluklu dizgide aranırsa süre O(m² · n) ya da daha kötü olur. DP aynı soruyu O(m · n) sürede cevaplar.

Durumun seçimi LIS'tekine benzer. Ortak parçanın nerede bittiği sabitlenmelidir. Dizgiler X (uzunluk m, tablonun sütunları) ve Y (uzunluk n, tablonun satırları) olsun.

İki karakter eşitse, bir önceki karakterlerde biten ortak parça bir karakter uzar: bu çapraz hücreye 1 eklemektir. Karakterler farklıysa bu iki konumda biten hiçbir ortak parça yoktur; bitişiklik bozulur ve sayaç sıfırlanır. Cevap son hücre değildir, çünkü ortak parça dizgilerin herhangi bir yerinde bitebilir.

8.7.2Tablonun doldurulması

Sütunlar X = “abdca”, satırlar Y = “cbda” olsun. Tablo 5 × 6'dır ve satır satır doldurulur.

Tablonun çoğu sıfırdır; yalnız eşleşen karakterlerin kesiştiği hücreler doludur. 1. satırda 'c' yalnız X[3] = 'c' ile eşleşir: L[1][4] = L[0][3] + 1 = 1. 2. satırda 'b', X[1] ile eşleşir: L[2][2] = 1. 3. satırda 'd', X[2] ile eşleşir ve çaprazındaki L[2][2] = 1'i uzatır: L[3][3] = 2. Bu, “b” ile başlayıp “d” ile biten ortak parçadır. 4. satırda 'a' iki yerde eşleşir. L[4][1] = L[3][0] + 1 = 1'dir. L[4][5] = L[3][4] + 1 = 0 + 1 = 1'dir; çaprazdaki 'd' ile 'c' eşleşmediği için parça uzamaz.

Parçanın kendisi en büyük hücreden okunur. En büyük değer L[3][3] = 2'dir; parça X'te 3. karakterde biter ve 2 uzunluktadır. O hâlde parça X[1..2] = “bd”'dir. Burada ayrıca geri yürümeye gerek yoktur: bitiş konumu ve uzunluk parçayı tek başına belirler.

8.7.3Kod

Sunumda bu problemin yalnız bağıntısı ve tablosu vardır. Aşağıdaki kod aynı bağıntıyı Java'ya çevirir. Kod, en büyük değeri ve onun X'teki bitiş konumunu tablo doldurulurken izler; sonunda parçayı substring ile döndürür.

String ortakAltDizgi(String x, String y) {
  int m = x.length(), n = y.length();
  int[][] L = new int[n + 1][m + 1];
  int enIyi = 0, bitis = 0;            // bitis: X'te parçanın bittiği yer
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (y.charAt(i - 1) == x.charAt(j - 1)) {
        L[i][j] = L[i - 1][j - 1] + 1;
        if (L[i][j] > enIyi) { enIyi = L[i][j]; bitis = j; }
      }                                // eşleşmezse L[i][j] = 0 kalır
  return x.substring(bitis - enIyi, bitis);
}

Eşleşmeyen hücrelere bir şey yazılmaz; Java'nın başlangıç değeri olan 0 orada kalır. L[i][j] > enIyi koşulu kesin büyüktür; eşit uzunlukta bir parça daha bulunursa ilk bulunan korunur. Metot “abdca” ve “cbda” için “bd”, “ababc” ve “babca” için “babc” döndürür. Süre ve bellek O(m · n)'dir. Her hücre yalnız çaprazındaki hücreye bağlı olduğu için bellek iki satıra, dolayısıyla O(min(m, n))'ye indirilebilir.

8.8En uzun ortak alt dizi

8.8.1Problem ve bağıntı

Bitişiklik koşulu kaldırılınca problem değişir. İki dizide de aynı göreli sırayla geçen en uzun dizi aranır; aradaki karakterler atlanabilir. Bu probleme en uzun ortak alt dizi (longest common subsequence, LCS) denir. diff ve git iki dosyanın değişmeyen satırlarını LCS ile bulur; değişen satırlar LCS'nin dışında kalanlardır. DNA dizilerinin benzerliği ve intihal tespiti de LCS'nin uygulamalarıdır.

“abdca” ve “cbda” için LCS “bda”'dır ve uzunluğu 3'tür; ortak alt dizgi yalnız 2'ydi. Bir başka örnek: “AGGTAB” ve “GXTXAYB” dizilerinin LCS'si “GTAB”'dir ve uzunluğu 4'tür. “GTAB” iki dizide de alt dizidir, ama hiçbirinde alt dizgi değildir. LCS tek olmak zorunda değildir; uzunluğu ise tektir. “ABCBDAB” ve “BDCABA” dizilerinin üç farklı LCS'si vardır: “BCBA”, “BDAB” ve “BCAB”.

Bağıntı, iki dizinin son karakterlerine bakılarak bulunur. Durum ortak alt dizgidekiyle aynı biçimde tanımlanır, ama anlamı farklıdır: L[i][j], Y'nin ilk i ve X'in ilk j karakterinin LCS uzunluğudur. Bu kez parçanın sonda bitmesi gerekmez.

İki problemin bağıntıları yalnız eşleşmeme durumunda ayrılır. Tablo 8.18 farkları özetler.

Eşleşmeme durumundaki fark, iki problemin özünü yansıtır. Ortak alt dizgide eşleşmeyen bir karakter zinciri koparır; sayaç sıfırlanır. LCS'de eşleşmeyen karakter yalnız atlanır; o ana kadar bulunan ortak alt dizi kaybolmaz ve üstten ya da soldan taşınır. Bu yüzden LCS tablosunun değerleri sağa ve aşağı doğru hiç azalmaz; son hücre en büyük değerdir.

8.8.2Kod ve izleme

static int lcs(String x, String y) {
  int m = x.length(), n = y.length();
  int[][] L = new int[n + 1][m + 1];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (y.charAt(i - 1) == x.charAt(j - 1))
        L[i][j] = L[i - 1][j - 1] + 1;
      else
        L[i][j] = Math.max(L[i - 1][j],
                           L[i][j - 1]);
  return L[n][m];
}

Kod, bağıntıyı iç içe iki döngüyle uygular. Dizgilerin karakterlerine charAt(i - 1) ve charAt(j - 1) ile erişilir, çünkü tablonun i. satırı Y'nin i. karakterini, yani 0 tabanlı i − 1 indisli karakterini temsil eder. Aynı “abdca” ve “cbda” örneği için tablo şöyle dolar:

Bazı hücrelerin hesabı şöyledir. L[1][5]: 'c' ≠ 'a'; üst 0, sol 1; değer 1'dir. 'c' karakterinin bulduğu ortak alt dizi sağa taşınmıştır. L[3][3]: 'd' = 'd'; çapraz L[2][2] = 1'e 1 eklenir ve 2 olur (“bd”). L[4][3]: 'a' ≠ 'd'; üst 2, sol 1; değer 2'dir. L[4][5]: 'a' = 'a'; çapraz L[3][4] = 2'ye 1 eklenir: 3. Ortak alt dizgi tablosunda bu çapraz hücre 0'dı; LCS'de ise “bd” sağa taşınarak 2 olmuştu. Bitişiklik koşulu kalkınca 'a', “bd”nin sonuna eklenebilmiştir.

Süre ve bellek O(m · n)'dir. Yalnız uzunluk gerekiyorsa iki satır yeter ve bellek O(min(m, n))'ye iner. Dizinin kendisi de isteniyorsa bütün tablo saklanmalıdır.

8.8.3Geri okuma

LCS'nin kendisi son hücreden başlayarak geri okunur. Her hücrede bağıntının hangi kolunun kullanıldığına bakılır:

• Karakterler eşitse karakter LCS'ye eklenir ve çapraz hücreye geçilir.
• Eşit değilse değerin geldiği yöne gidilir: sol hücre üstten büyükse sola, değilse yukarı.
• 0. satıra ya da 0. sütuna ulaşınca durulur. Karakterler sondan başa bulunduğu için sonuç ters çevrilir.

Her adımda ya satır ya sütun ya da ikisi birden bir azalır; geri okuma en çok m + n adım sürer. Aşağıdaki metot tabloyu doldurur ve LCS'nin kendisini döndürür.

String lcsDizgi(String x, String y) {
  int m = x.length(), n = y.length();
  int[][] L = new int[n + 1][m + 1];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      L[i][j] = y.charAt(i - 1) == x.charAt(j - 1) ? L[i - 1][j - 1] + 1
              : Math.max(L[i - 1][j], L[i][j - 1]);
  StringBuilder sb = new StringBuilder();
  int i = n, j = m;
  while (i > 0 && j > 0)
    if (y.charAt(i - 1) == x.charAt(j - 1)) {   // eşleşme: çapraz
      sb.append(x.charAt(j - 1)); i--; j--;
    } else if (L[i][j - 1] > L[i - 1][j]) j--;  // sol büyükse sola
    else i--;                                   // değilse yukarı
  return sb.reverse().toString();
}

Metot “abdca” ve “cbda” için “bda”, “AGGTAB” ve “GXTXAYB” için “GTAB” döndürür. Eşitlikte yukarı gitme kuralı, birden çok LCS varsa hangisinin bulunacağını belirler. “ABCBDAB” (sütunlar) ve “BDCABA” (satırlar) için metot “BDAB”'yi bulur; kural değiştirilip eşitlikte sola gidilirse başka bir LCS bulunabilir.

8.8.4DNA örneği

Biyoinformatikte iki DNA dizisinin ne kadar benzediği LCS'nin uzunluğuyla ölçülebilir. Şekil 8.27'deki diziler ACCGGTGGACAATTCA ve GGAAAGAGATATGCAC'tir. Her ikisi de 16 bazdan oluşur.

Şekildeki çizgiler bir ortak alt dizinin görsel karşılığıdır. Eşleşen karakterleri birleştiren çizgiler kesişmez, çünkü göreli sıra iki dizide de korunur. Kesişmeyen çizgilerle kurulan her eşleştirme bir ortak alt dizidir. LCS, bu biçimde çizilebilecek en çok çizgili eşleştirmedir. DP sonucu GGAAATTCA'dır ve uzunluğu 9'dur. Diziler yer değiştirince geri okuma GGGGAATCA gibi başka bir LCS bulabilir; uzunluk yine 9'dur.

Göz kararı eşleştirme yanıltıcıdır. Örneğin AAAATTCA da geçerli bir ortak alt dizidir: ilk dizide A'lar 0, 8, 10, 11. konumlarda, ardından T, T, C, A gelir; ikinci dizide de aynı sıra bulunur. Ama uzunluğu 8'dir ve en uzun değildir. Doğru cevabı ancak bütün seçenekleri dolaylı olarak deneyen DP tablosu verir. 16 × 16 bir tablo 256 hücreyle bu işi bitirir; olası bütün alt dizileri denemek ise 2¹⁶ = 65.536 alt diziyi öteki dizide aramak demektir.

8.9Diğer klasik DP problemleri

Notta incelenen problemler bir kalıp izler: durum birkaç tam sayıyla tanımlanır, bağıntı son kararın seçeneklerini dener, tablo uygun sırayla doldurulur. Aynı kalıp başka birçok klasik problemi çözer. Tablo 8.21 bunlardan yedisini özetler; ardından dördü küçük örneklerle ele alınır.

8.9.1Düzenleme uzaklığı

İki dizgi arasındaki düzenleme uzaklığı (Levenshtein uzaklığı), birini ötekine çevirmek için gereken en az tek karakterlik işlem sayısıdır. İşlemler üç türlüdür: bir karakter silmek, bir karakter eklemek ve bir karakteri başka bir karakterle değiştirmek. Yazım denetleyicisi yanlış yazılmış bir kelimeye uzaklığı küçük olan sözlük kelimelerini önerir.

D[i][j], a'nın ilk i karakterini b'nin ilk j karakterine çevirmenin en az maliyetidir. Son karakter için üç seçenek vardır. a'nın son karakteri silinir: D[i − 1][j] + 1. b'nin son karakteri eklenir: D[i][j − 1] + 1. Son karakterler eşleştirilir: eşitlerse ücretsiz, değilse bir değiştirme ile, D[i − 1][j − 1] + [aᵢ ≠ bⱼ]. Köşeli ayraç, koşul doğruysa 1, yanlışsa 0 demektir. Taban durumları açıktır: boş dizgiden j karakterlik dizgiye j eklemeyle, i karakterlik dizgiden boş dizgiye i silmeyle varılır.

int duzenlemeUzakligi(String a, String b) {
  int m = a.length(), n = b.length();
  int[][] D = new int[m + 1][n + 1];
  for (int i = 0; i <= m; i++) D[i][0] = i;     // i silme
  for (int j = 0; j <= n; j++) D[0][j] = j;     // j ekleme
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++) {
      int fark = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
      D[i][j] = Math.min(Math.min(D[i - 1][j] + 1,   // sil
                                  D[i][j - 1] + 1),  // ekle
                         D[i - 1][j - 1] + fark);    // değiştir / aynı
    }
  return D[m][n];
}

Düzenleme uzaklığı ile LCS yakından ilişkilidir. Yalnız ekleme ve silmeye izin verilirse en az işlem sayısı m + n − 2 · LCS olur: LCS'de olmayan karakterler bir dizgiden silinir, ötekinden eklenir.

8.9.2Para üstü

Para birimleri c₁, …, cₖ ve bir X tutarı verilsin. Bu problemin iki ünlü sorusu vardır: tutar en az kaç parayla ödenir ve kaç farklı biçimde ödenebilir? Her paradan sınırsız sayıda bulunduğu için ikisi de sınırsız sırt çantasının akrabasıdır.

En az para. P[x], x tutarını ödemek için en az para sayısıdır. Son verilen para c ise geriye x − c kalır: P[x] = 1 + min P[x − c] (c ≤ x), P[0] = 0. Küçük tutarlar önce hazır olmalıdır; x 1'den X'e doldurulur. Tablo X + 1 hücrelidir, her hücrede k para denenir: O(k · X) süre, O(X) bellek. Bu da sözde-polinom bir süredir.

int enAzPara(int[] para, int X) {
  int[] P = new int[X + 1];            // P[0] = 0
  for (int x = 1; x <= X; x++) {
    P[x] = Integer.MAX_VALUE;
    for (int c : para)
      if (c <= x && P[x - c] != Integer.MAX_VALUE)
        P[x] = Math.min(P[x], P[x - c] + 1);
  }
  return P[X];                         // MAX_VALUE: ödenemez
}

long yolSayisi(int[] para, int X) {
  long[] d = new long[X + 1];
  d[0] = 1;                            // 0 tutarının tek yolu: hiç para
  for (int c : para)                   // dış döngü paralar üzerinde
    for (int x = c; x <= X; x++)
      d[x] += d[x - c];
  return d[X];
}

Yol sayısı. d[x], x tutarını ödemenin farklı biçimlerinin sayısıdır; d[0] = 1'dir (hiç para vermemek). Burada döngülerin sırası belirleyicidir. Dış döngü paralar, iç döngü tutarlar üzerinde olursa her biçim bir kez sayılır: paralar sabit bir sırayla eklenir ve “2 + 1” ile “1 + 2” aynı kabul edilir. Döngüler yer değiştirirse sıralı diziler sayılır. {1, 2, 5} ile 5 tutarı için doğru cevap 4'tür: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 ve 1 + 1 + 1 + 1 + 1. Döngüler ters kurulsa sonuç 9 olurdu.

8.9.3En büyük toplamlı alt dizi

Bir dizide toplamı en büyük olan bitişik parça aranır. Bağıntı optimal alt yapı tartışılırken yazılmıştı: V(i) = max(a[i], V(i − 1) + a[i]). Her adımda iki seçenek vardır: önceki parçayı uzatmak ya da a[i] ile yeniden başlamak. Önceki parçanın toplamı negatifse onu taşımak zarardır; yeniden başlamak daha iyidir. V(i) yalnız V(i − 1)'e bağlı olduğu için tek değişken yeter.

int kadane(int[] a) {
  int V = a[0], enIyi = a[0];
  for (int i = 1; i < a.length; i++) {
    V = Math.max(a[i], V + a[i]);   // yeniden başla ya da uzat
    enIyi = Math.max(enIyi, V);
  }
  return enIyi;
}

8.9.4Matris zinciri çarpımı

p × q boyutlu bir matrisle q × r boyutlu bir matrisin olağan çarpımı p · q · r skaler çarpma ister. Matris çarpımı birleşmelidir: (AB)C = A(BC). Sonuç aynıdır, ama maliyet parantezlemeye göre çok farklı olabilir. Problem, bir matris zincirini en az skaler çarpmayla hesaplayan parantezlemeyi bulmaktır.

Aᵢ matrisi pᵢ₋₁ × pᵢ boyutlu olsun. M[i][j], Aᵢ … Aⱼ zincirinin en az maliyetidir. Bu zincirin son çarpımı bir k noktasında ikiye ayrılır: önce Aᵢ … Aₖ ve Aₖ₊₁ … Aⱼ hesaplanır, sonra pᵢ₋₁ × pₖ ve pₖ × pⱼ boyutlu iki sonuç çarpılır. Bütün k'ler denenir. Burada durumlar zincir uzunluğuna göre doldurulur: kısa zincirler önce hazır olmalıdır.

long matrisZinciri(int[] p) {          // A_i matrisi p[i-1] × p[i]
  int n = p.length - 1;
  long[][] M = new long[n + 1][n + 1];
  for (int uz = 2; uz <= n; uz++)      // zincir uzunluğu
    for (int i = 1; i + uz - 1 <= n; i++) {
      int j = i + uz - 1;
      M[i][j] = Long.MAX_VALUE;
      for (int k = i; k < j; k++)
        M[i][j] = Math.min(M[i][j],
            M[i][k] + M[k + 1][j] + (long) p[i - 1] * p[k] * p[j]);
    }
  return M[1][n];
}

Durum sayısı O(n²)'dir (i ≤ j çiftleri); her durumda O(n) bölme noktası denenir. Süre O(n³)'tür. Bütün parantezlemeleri tek tek denemek ise Catalan sayıları kadar seçenek demektir: 10 matris için 4862, 20 matris için 1,7 milyardan fazla.

8.9.5Gezgin satıcı, Bellman–Ford ve optimal ikili arama ağacı

Tablodaki son üç problem, durumun her zaman bir ya da iki indisten oluşmadığını gösterir.

• Gezgin satıcı (Held–Karp). Durum bir küme ve bir düğümdür: dp[S][i], başlangıçtan çıkıp S kümesindeki düğümlerin hepsini gezen ve i'de biten en kısa yoldur. Küme bir bit maskesiyle saklanır. 2ⁿ · n durum vardır, her biri O(n) önceki düğüm dener: O(n² · 2ⁿ). Bu süre hâlâ üsteldir, ama bütün turları denemenin (n − 1)!'inden çok daha küçüktür. 20 düğüm için 20² · 2²⁰ ≈ 4,2 · 10⁸'e karşılık 19! ≈ 1,2 · 10¹⁷.
• Bellman–Ford. Durum bir düğüm ve bir kenar sayısıdır: dₖ(v), en çok k kenar kullanan en kısa yoldur. Her turda bütün kenarlar gevşetilir; V − 1 tur yeter. Tablo tek boyuta indirilir ve süre O(V · E) olur.
• Optimal ikili arama ağacı. Anahtarların erişim olasılıkları biliniyorsa beklenen arama maliyeti en küçük olan ağaç aranır. Durum bir anahtar aralığıdır; bağıntı aralık için bütün kök seçeneklerini dener. Yapı matris zinciriyle aynıdır ve süre O(n³)'tür.

8.10Sık yapılan hatalar

Dinamik programlama hataları çoğunlukla derleme hatası vermez. Kod çalışır, bir sayı döndürür ve sayı yanlıştır. Aşağıdaki hatalar, sunumdaki listeyle birlikte not boyunca karşılaşılanları toplar.

8.11Özet

• Dinamik programlama = örtüşen alt problemler + optimal alt yapı. Her alt problem bir kez çözülür, sonucu tabloda saklanır.
• Tasarım adımları: optimal çözümün yapısı, durum ve bağıntı (taban durumlarıyla), hesaplama sırası, tablo boyutu, tablonun doldurulması, çözümün geri okunması.
• Toplam süre ≈ durum sayısı × durum başına iş. Bu kural notta geçen bütün karmaşıklıkları açıklar.
• Bellekleme yukarıdan aşağı çalışır ve yalnız gereken durumları çözer; tablolama aşağıdan yukarı çalışır, çağrı maliyeti yoktur ve bellek azaltmaya uygundur. Asimptotik süreleri aynıdır.
• Açgözlü yaklaşım her adımda tek seçeneğe bakar; ancak açgözlü seçim özelliği kanıtlanmışsa doğrudur. Böl ve fethette alt problemler bağımsızdır ve tablo gerekmez.

• 0/1 sırt çantası, alt küme toplamı ve para üstü sözde-polinomdur: süre girdideki sayının değerine bağlıdır, bit uzunluğuna değil.
• Tek boyutlu tabloda döngü yönü problemi belirler: büyükten küçüğe 0/1, küçükten büyüğe sınırsız.
• Çözümün kendisi tablodan geri okunur: sırt çantasında değer değişen satırlar, LCS'de çapraz adımlar, LIS'te önceki indis zinciri.

8.12Kavram listesi

• dinamik programlama dynamic programming (DP)
• alt problem subproblem
• örtüşen alt problemler overlapping subproblems
• optimal alt yapı optimal substructure
• bellekleme memoization
• tablolama tabulation
• yukarıdan aşağı / aşağıdan yukarı top-down / bottom-up
• geri okuma traceback
• açgözlü seçim özelliği greedy-choice property
• 0/1 sırt çantası 0/1 knapsack
• kesirli sırt çantası fractional knapsack
• sınırsız sırt çantası unbounded knapsack
• sözde-polinom pseudo-polynomial
• alt küme toplamı subset sum
• en uzun artan alt dizi longest increasing subsequence (LIS)
• en uzun ortak alt dizgi longest common substring
• en uzun ortak alt dizi longest common subsequence (LCS)
• düzenleme uzaklığı edit distance
• para üstü coin change
• matris zinciri çarpımı matrix chain multiplication

8.13Kendini Dene

Sorular 2 ve 3 aynı eşyaları kullanır: (değer, ağırlık) biçiminde (12, 2), (17, 3), (30, 5); kapasite 6.

1. Düz özyinelemeli fib(6) çağrısında fib(2) kaç kez çağrılır? Bellekleme ile fib(2) kaç kez hesaplanır, toplam çağrı sayısı kaçtır?

   Cevap

   fib(n) ağacında fib(k), F(n − k + 1) kez çağrılır: fib(2) için F(5) = 5 kez. Düz özyineleme toplam 2 · F(7) − 1 = 25 çağrı yapar. Bellekleme ile fib(2) bir kez hesaplanır, ikinci çağrısı tablodan döner; toplam çağrı 2 · 6 − 1 = 11'dir.

2. 0/1 sırt çantası tablosunun son satırı nedir? En büyük değer kaçtır, hangi eşyalar seçilir?

   Cevap

   Satırlar: [0, 0, 12, 12, 12, 12, 12], [0, 0, 12, 17, 17, 29, 29], [0, 0, 12, 17, 17, 30, 30]. Cevap K[3][6] = 30'dur. Geri okuma: 30 ≠ K[2][6] = 29, 3. eşya alınır ve c = 1 olur; 1 kg'a başka eşya sığmaz. Yalnız 30'luk eşya seçilir. 12 + 17 = 29 bir eksik kalır.

3. Aynı eşyalardan sınırsız sayıda alınabilseydi cevap ne olurdu? Tek boyutlu 0/1 kodunda iç döngü küçükten büyüğe yazılsaydı hangi sayı dönerdi?

   Cevap

   Sınırsız: dp = [0, 0, 12, 17, 24, 30, 36]; cevap 36'dır, üç tane 12'lik (2 kg) eşya. Küçükten büyüğe gezilen tek boyutlu 0/1 kodu da 36 döndürür, çünkü o kod artık sınırsız sırt çantasını çözer.

4. 0/1 sırt çantası DP'sinde W iki katına çıkarsa süre nasıl değişir? W'nin ikili gösterimine bir bit eklenirse ne olur?

   Cevap

   İki durumda da tablo genişliği yaklaşık iki katına çıkar, süre de iki katına çıkar. Bir bitlik artış girdinin boyutunu yalnız bir bit büyütür; süre ise iki katına çıkar. b bitlik bir W için süre O(n · 2ᵇ)'dir; sözde-polinom bu anlamdadır.

5. {2, 3, 7, 8, 10} kümesinde toplamı 11 olan bir alt küme var mıdır? Tablonun son satırında hangi toplamlar ulaşılabilirdir?

   Cevap

   Evet: {3, 8}; bu tek çözümdür. Son satırda ulaşılabilir toplamlar 0, 2, 3, 5, 7, 8, 9, 10 ve 11'dir (1, 4 ve 6 elde edilemez). Geri okuma dp[5][11]'den başlar: 10 olmadan da 11 kurulabildiği için 10 seçilmez; 8 seçilir (j = 3); 7 seçilmez; 3 seçilir (j = 0).

6. [3, 10, 2, 1, 20, 4, 6, 7] dizisinde O(n²) algoritmanın dp dizisi nedir? lisHizli bitince son dizisi nedir?

   Cevap

   dp = [1, 2, 1, 1, 3, 2, 3, 4]; LIS uzunluğu 4'tür, örneğin 3, 4, 6, 7. son sırasıyla [3], [3, 10], [2, 10], [1, 10], [1, 10, 20], [1, 4, 20], [1, 4, 6], [1, 4, 6, 7] olur. Bu örnekte son dizi bir LIS'tir (1, 4, 6, 7), ama bu bir rastlantıdır; dizinin LIS olması gerekmez.

7. “kalem” ve “kelam” için en uzun ortak alt dizgi ve LCS uzunlukları kaçtır?

   Cevap

   Ortak alt dizgi 1'dir: iki harfli parçaların (ka, al, le, em ile ke, el, la, am) hiçbiri ortak değildir. LCS 3'tür; “kam”, “kem” ve “klm” üç farklı LCS'dir. Bitişiklik koşulunun kalkması uzunluğu üç katına çıkarır.

8. “kedi” ile “kadın” arasındaki düzenleme uzaklığı kaçtır?

   Cevap

   3'tür: e → a ve i → ı değiştirilir, sona n eklenir. Tablonun son satırı [4, 3, 3, 2, 2, 3]'tür; D[4][5] = 3.

9. Paralar {1, 5, 6, 9}, tutar 11. En az kaç para gerekir? Açgözlü yöntem kaç para kullanır?

   Cevap

   DP: 2 para (5 + 6). Açgözlü: 9 + 1 + 1, 3 para. Bu para sisteminde de açgözlü seçim optimal değildir.

10. A₁ 5 × 10, A₂ 10 × 3, A₃ 3 × 12 boyutludur. En az kaç skaler çarpma gerekir?

    Cevap

    (A₁A₂)A₃ = 5 · 10 · 3 + 5 · 3 · 12 = 150 + 180 = 330. A₁(A₂A₃) = 10 · 3 · 12 + 5 · 10 · 12 = 360 + 600 = 960. En az 330'dur.

8.14İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 14: çubuk kesme, matris zinciri, LCS ve optimal ikili arama ağacı üzerinden DP'nin ilkelerini kanıtlarıyla verir.
• J. Kleinberg ve É. Tardos, Algorithm Design (2005), Bölüm 6: ağırlıklı aralık çizelgeleme, sırt çantası, dizi hizalama ve Bellman–Ford örnekleriyle durum seçimini adım adım tartışır.
• S. Dasgupta, C. Papadimitriou ve U. Vazirani, Algorithms (2006), Bölüm 6: DP'yi yönlü çevrimsiz çizgede en kısa yol olarak yorumlar; LIS, düzenleme uzaklığı, sırt çantası ve gezgin satıcıyı kısa ve açık biçimde işler.
• R. Bellman, Dynamic Programming (1957): yöntemin ve optimallik ilkesinin ilk kapsamlı anlatımıdır.

8.15Kaynaklar

1. R. Bellman, Dynamic Programming, Princeton University Press, 1957.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 14: Dynamic Programming).
3. S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2006 (Bölüm 6).
4. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2005 (Bölüm 6).

İlgili sayfalar: Bölüm 8 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.