---
title: "Problem Oturumu 8"
subtitle: "Dinamik programlama oturumlarının ilki — SRTBOT ile dört problem: durum izleme, edit distance artı precomputation, LIS-benzeri blok kulesi ve yol sayma"
---
::: {.callout-note title="Oturum bilgisi"}
- **Solomon'un videosu:** [YouTube — Problem Session 8](https://www.youtube.com/watch?v=UuxR0NCkg0k) (≈95 dk)
- **OCW sayfası:** [MIT 6.006 Problem Session 8](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_prob8/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 25 (PS8)
- **Hoca:** Justin Solomon
- **Okuma süresi:** ≈25 dk
- DP problem oturumlarının **İLKİ**; tema: DP bir algoritma değil bir yaşam tarzı (Solomon 2:35).
:::
## Bu Problem Oturumu Ne Hakkında? {#sec-hakkinda-d25}
Sekizinci problem oturumu (Justin Solomon), **dinamik programlama** üzerine iki oturumun ilki; dört problemi **SRTBOT** çerçevesiyle çözer (@fig-concept-map). Tema sabit: DP "bir algoritma değil, bir yaşam tarzı" — recurrence yaz, alt problemleri memoize et.
> *"dynamic programming, it's really more of a way of life than any particular algorithm."* — Solomon, 2:35
> *"when you have a recursive call and you repeat something... you might as well remember what you got the last time you saw that input."* — Solomon, 4:46
Dört problemde yeni kavramlar pekişir: alt problem **durum izleme** (kaç gün üst üste), **edit distance** (precomputation'ın çalışma süresine etkisi), **LIS-benzeri** sıralama-temelli DP, ve **yol sayma** (max yerine toplama). Her problem "İfade → Yaklaşım → Çözüm → Karmaşıklık" akışıyla işlenir.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Problem Oturumu 8'in kavram haritası: kök (PS8) dört probleme dallanır ve ortadaki ortak tema düğümü dördünü birden yönlendirir. Problem 1 Tim'in mutluluğunu suffix-DP ile maksimize eder ve 'kaç gün üst üste' kısıtını alt problem tanımına bir varsayım olarak gömerek durumu izler; Problem 2 Menix'in edit distance'ını suffix-çift DP ile çözer, satır karşılaştırmasının O(k) maliyetini precomputation'la çalışma süresine taşıyıp O(kn + n²)'ye iner; Problem 3 Saggy'nin blok kulesini üç gözlemle (uzun kenarı hizala, yönelim başına bir kez, kesin destek sıralanabilir kılar) LIS-benzeri bir DP'ye indirger; Problem 4 Princess Plum ızgarasını önce max-mushroom DP'siyle, sonra max yerine toplama yapan ikinci bir yol-sayma DP'siyle çözer. Ortak tema — SRTBOT yaz, her alt problemi yerel kaba kuvvetle çöz — Solomon'un dört probleme de aynı kapıdan girmesini sağlar."
flowchart TD
R["Problem Oturumu 8<br/>(DP problem oturumlarının İLKİ)"] --> P1["Problem 1<br/>Tim the Beaver<br/>(suffix-DP + durum izleme)"]
R --> P2["Problem 2<br/>Menix edit distance<br/>(suffix-çift + precomputation)"]
R --> P3["Problem 3<br/>Saggy blok kulesi<br/>(sırala + LIS-benzeri)"]
R --> P4["Problem 4<br/>Princess Plum<br/>(max-mushroom + yol sayma)"]
CORE["Ortak tema:<br/>SRTBOT yaz, her alt problemi<br/>YEREL KABA KUVVETLE çöz<br/>(DP = bir yaşam tarzı)"]
CORE -.-> P1
CORE -.-> P2
CORE -.-> P3
CORE -.-> P4
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef prob fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef core fill:#fcd34d,stroke:#b45309,stroke-width:2px,color:#1f2937
class R root
class P1,P2,P3,P4 prob
class CORE core
```
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 25 (PS8) motoru (_engine_PS8.py) + _engine.py'den INF /
# dijkstra bağımlılığı + Slate+Amber sabitleri (_viz.py). Bu hücre gizlidir
# (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede tanımlanan
# fonksiyonları (tim_happiness, tim_plan, brute_tim, block_orientations,
# tower_height, brute_tower, plum_max_mushroom, plum_count_paths, brute_plum ...)
# + COL_* globallerini IMPORT ETMEDEN kullanır. Notion'daki öğretim içeriği
# (görünür display python blokları) bu motorun tarif seviyesidir; burada tam,
# deterministik, test edilmiş sürüm yaşar (_smoke_PS8: 11/11 PASS).
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir). Standalone testte savefig
# kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
#
# Dosyadan import YOK: tüm DP motoru + INF/dijkstra (P2 grid-DAG tanığı için)
# burada self-contained INLINE → render dizininden bağımsız (kurs paritesi:
# PS6 emsali, düz INLINE).
# ============================================================================
from collections import deque
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch, Circle
# ---------------------------------------------------------------------------
# _viz.py — Slate + Amber stil sabitleri (HEX birebir)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu (aktif seçenek / kazanan zincir)
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / callout / kutu dolgusu
# Türev amber tonları
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
# Türev slate tonları
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# ===========================================================================
# _engine.py altyapısı (P2 grid-DAG tanığı için): INF + Dijkstra (L13/D19).
# ===========================================================================
INF = float("inf")
class _ChangeablePQ:
"""Değiştirilebilir min-öncelik kuyruğu (L13 §5): binary min-heap +
id→konum sözlüğü. Dijkstra için yeterli (build O(n), delete_min/
decrease_key O(log n))."""
def __init__(self, items=()):
self.a = [(k, i) for i, k in items]
self.pos = {item[1]: idx for idx, item in enumerate(self.a)}
for j in range(len(self.a) // 2 - 1, -1, -1):
self._sift_down(j)
def __len__(self):
return len(self.a)
def _swap(self, i, j):
self.a[i], self.a[j] = self.a[j], self.a[i]
self.pos[self.a[i][1]] = i
self.pos[self.a[j][1]] = j
def _sift_up(self, j):
while j > 0:
p = (j - 1) // 2
if self.a[p][0] <= self.a[j][0]:
break
self._swap(p, j)
j = p
def _sift_down(self, j):
n = len(self.a)
while True:
l, r, small = 2 * j + 1, 2 * j + 2, j
if l < n and self.a[l][0] < self.a[small][0]:
small = l
if r < n and self.a[r][0] < self.a[small][0]:
small = r
if small == j:
return
self._swap(j, small)
j = small
def delete_min(self):
top_key, top_id = self.a[0]
last = self.a.pop()
del self.pos[top_id]
if self.a:
self.a[0] = last
self.pos[last[1]] = 0
self._sift_down(0)
return top_id, top_key
def decrease_key(self, vid, new_key):
j = self.pos[vid]
self.a[j] = (new_key, vid)
self._sift_up(j)
def dijkstra(adj, weight, s):
"""Dijkstra (L13 §6 / D19): en yakını çıkar, kenarlarını gevşet,
decrease_key ile güncelle. Ağırlıklar ≥ 0 ŞART. P2'de DP = en kısa yol
köprüsünün BAĞIMSIZ tanığıdır (grid-DAG üzerinde 0/1-ağırlıklı kenarlar)."""
d = {v: INF for v in adj}
d[s] = 0
Q = _ChangeablePQ((v, d[v]) for v in adj)
while len(Q):
u, _ = Q.delete_min()
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d
# ===========================================================================
# _engine_PS8.py — PS8 problem motoru (4 problem, hepsi SRTBOT; INLINE).
# ===========================================================================
# --- Problem 1: Tim the Beaver — durum izlemeli suffix DP ---
def tim_happiness(t):
"""x(i) = 'gün i'de dışarı çıkma İZNİ varken' i..n−1 max mutluluk. Üç
yerel seçenek (en fazla 2 gün üst üste). Taban x(n)=x(n+1)=x(n+2)=0. O(n)."""
n = len(t)
x = [0] * (n + 3)
for i in range(n - 1, -1, -1):
x[i] = max(x[i + 1], t[i] + x[i + 2])
if i + 1 < n:
x[i] = max(x[i], t[i] + t[i + 1] + x[i + 3])
return x
def tim_plan(t):
"""Plan geri-kurma: öncelik çift > tek > içeride. [(gün, eylem)] döndürür."""
x = tim_happiness(t)
n = len(t)
plan, i = [], 0
while i < n:
if i + 1 < n and x[i] == t[i] + t[i + 1] + x[i + 3]:
plan.append((i, "çift"))
i += 3
elif x[i] == t[i] + x[i + 2]:
plan.append((i, "tek"))
i += 2
else:
plan.append((i, "içeride"))
i += 1
return plan
def brute_tim(t):
"""Bağımsız tanık (bitmask, recurrence'sız): dışarı-çıkılan günlerin TÜM
alt kümeleri; 3 ardışık 1 içerenler geçersiz; max Σt. Üstel."""
n = len(t)
best = 0
for mask in range(1 << n):
if mask & (mask >> 1) & (mask >> 2):
continue
best = max(best, sum(t[i] for i in range(n) if mask >> i & 1))
return best
def build_tim_example():
return [5, -2, 8, 6, -4, 7, 3]
# --- Problem 3: Saggy'nin blok kulesi — sırala + LIS-benzeri ---
def block_orientations(blocks):
"""Her bloğu sıralı 3 yönelime aç (taban_a, taban_b, dikey); taban azalan
lexicographic SIRALI, tekrarlar çıkarılmış."""
cand = set()
for dims in blocks:
w, h, l = sorted(dims)
cand.add((h, l, w))
cand.add((w, l, h))
cand.add((w, h, l))
return sorted(cand, reverse=True)
def tower_height(blocks):
"""LIS-benzeri DP: x(i) = yönelim i TEPE; R: x(i) = vᵢ + max({x(j): j<i,
a_i<a_j ∧ b_i<b_j} ∪ {0}); O = max_i x(i). O(n²).
Döndürür: (yükseklik, yönelim listesi, x tablosu)."""
ori = block_orientations(blocks)
n = len(ori)
x = [0] * n
for i in range(n):
a, b, v = ori[i]
best = 0
for j in range(i):
aj, bj, _ = ori[j]
if a < aj and b < bj:
best = max(best, x[j])
x[i] = v + best
return (max(x) if x else 0), ori, x
def brute_tower(blocks):
"""Bağımsız tanık (zincir-DFS, DP'siz): 'üstüne sığar' DAG'ında TÜM
zincirleri gez, max Σdikey. Üstel; yalnız küçük test."""
ori = block_orientations(blocks)
def rec(top_a, top_b):
best = 0
for a, b, v in ori:
if a < top_a and b < top_b:
best = max(best, v + rec(a, b))
return best
return rec(float("inf"), float("inf"))
def build_tower_example():
return [(1, 2, 3), (2, 3, 4)]
# --- Problem 4: Princess Plum — max-mushroom + yol sayma DP ---
def plum_max_mushroom(grid):
"""(a) k(i,j) = (i,j)'de biten hızlı yolun max mushroom'u; ağaç → −∞;
k(i,j) = χ + max(k(i−1,j), k(i,j−1)). O(n²). Sözlük döndürür."""
n, m = len(grid), len(grid[0])
k = {}
for i in range(n):
for j in range(m):
if grid[i][j] == "T":
k[(i, j)] = -INF
continue
chi = 1 if grid[i][j] == "m" else 0
if i == 0 and j == 0:
k[(i, j)] = chi
continue
up = k[(i - 1, j)] if i > 0 else -INF
left = k[(i, j - 1)] if j > 0 else -INF
k[(i, j)] = chi + max(up, left)
return k
def plum_count_paths(grid):
"""(b) x(i,j) = k(i,j) mushroom toplayan hızlı yol SAYISI. Komşudan
k(komşu)+χ == k(i,j) ise x += x(komşu) — MAX DEĞİL TOPLAMA. Taban
x(0,0)=1. O(n²). Döndürür: (k_hedef, yol_sayısı, x tablosu)."""
n, m = len(grid), len(grid[0])
k = plum_max_mushroom(grid)
x = {}
for i in range(n):
for j in range(m):
if grid[i][j] == "T" or k[(i, j)] == -INF:
x[(i, j)] = 0
continue
if i == 0 and j == 0:
x[(i, j)] = 1
continue
chi = 1 if grid[i][j] == "m" else 0
cnt = 0
if i > 0 and k[(i - 1, j)] + chi == k[(i, j)]:
cnt += x[(i - 1, j)]
if j > 0 and k[(i, j - 1)] + chi == k[(i, j)]:
cnt += x[(i, j - 1)]
x[(i, j)] = cnt
goal = (n - 1, m - 1)
return k[goal], x[goal], x
def brute_plum(grid):
"""Bağımsız tanık (tüm monoton yollar, DP'siz): (0,0)→(n−1,m−1) yalnız
aşağı/sağ TÜM yolları DFS ile say; ağaçlılar elenir; (max, sayı)."""
n, m = len(grid), len(grid[0])
results = []
def rec(i, j, count):
if grid[i][j] == "T":
return
count += 1 if grid[i][j] == "m" else 0
if (i, j) == (n - 1, m - 1):
results.append(count)
return
if i + 1 < n:
rec(i + 1, j, count)
if j + 1 < m:
rec(i, j + 1, count)
rec(0, 0, 0)
if not results:
return -INF, 0
best = max(results)
return best, results.count(best)
def build_plum_example():
return [".m..",
".Tm.",
"m..T",
".m.."]
```
::: {.callout-tip title="Yaklaşım — ortak strateji: SRTBOT yaz, her alt problemi yerel kaba kuvvetle çöz"}
Dört problemin tamamı aynı refleksle başlar: önce alt problemi (Subproblem) tanımla — tek dizide prefix/suffix, iki dizide sonek çifti, ızgarada hücre. Sonra "bu alt problemde hangi yerel kararı versem geri kalanı bir küçük alt probleme iner?" diye **yerel kaba kuvvet** uygula; bu recurrence'ı (Relation) verir. Kısıt varsa (Tim'in "kaç gün üst üste", Saggy'nin "kesin destek") onu ya alt problem tanımına bir varsayım olarak göm, ya da bir sıralama doğurup LIS'e in. "Kaç yol" sorulduğunda max yerine topla. Bu oturum, DP kasını bu dört SRTBOT'la çalıştırır — Solomon'un deyimiyle DP bir algoritma değil bir yaşam tarzıdır.
:::
## Problem 1: Tim the Beaver — Mutluluk DP {#sec-problem-1-d25}
**İfade.** $n$ gün, gün $i$ sıcaklığı $t(i)$. Dışarı çık → mutluluk $+t(i)$; içeride kal → değişmez. **En fazla 2 gün üst üste** dışarı çıkılır. Mutluluğu maksimize et (ve planı kurtart).
::: {.callout-tip title="Yaklaşım — durum izleme: kısıtı alt problem tanımına bir varsayım olarak göm"}
Tek indeks (gün) → **suffix DP**. Kilit incelik: "kaç gün üst üste dışarı çıktım" durumunu açıkça izlemek yerine, alt problemi *"i'de dışarı çıkma izni var"* varsayımıyla tanımla. Böylece "en fazla 2 gün üst üste" kısıtı recurrence'a değil, alt problemin TANIMINA gömülür; üç yerel seçeneğin (içeride / tek gün çık / iki gün çık) her biri ileriyi taze-izinli bir güne devreder, durum bilgisi $i$'de saklı kalır.
:::
@fig-tim-plan bu suffix-DP'yi motordan **gerçek** verilerle gösterir: örnek $t = [5, -2, 8, 6, -4, 7, 3]$ için optimal plan gün 0'da tek (çık $+5$), gün 1 içeride (soğuk $-2$ atla), gün 2-3 çift ($8 + 6 = 14$), gün 4 içeride ($-4$ atla), gün 5-6 çift ($7 + 3 = 10$) → toplam $5 + 14 + 10 = 29$. Bağımsız bitmask tanığı (3 ardışık günü yasaklayan kaba kuvvet) de aynı $29$'u verir.
**Çözüm.** **S:** $x(i) = $ $i$'de dışarı çıkma izniyle gün $i \dots n$ maksimum mutluluk. **R:** üç seçenek:
- içeride kal → $x(i+1)$ (yarın tam serbest);
- bugün çık, yarın içeride → $t(i) + x(i+2)$;
- bugün + yarın çık, ertesi içeride → $t(i) + t(i+1) + x(i+3)$.
$x(i)$ bu üç seçeneğin maksimumudur. **T:** $i$ azalan. **B:** $x(n+1) = x(n+2) = 0$. **O:** $x(1)$. Planı kurtarmak için her gün hangi seçeneği aldığını sakla, sonra izle.
*(İndeks köprüsü: prose, kaynaktaki gibi 1-indekslidir — günler $1 \dots n$, cevap $x(1)$. Aşağıdaki kod ve figür 0-indekslidir: cevap $x(0)$, günler $0 \dots n-1$; motor dizisi güvenlik payıyla üç sıfır taban tutar, 1-indeksli gösterimde $x(n+1) = x(n+2) = 0$ yeterlidir.)*
```python
def tim_happiness(t): # O(n) — suffix DP
n = len(t)
x = [0] * (n + 3) # taban: x(n)=x(n+1)=x(n+2)=0
for i in range(n - 1, -1, -1): # i azalan (suffix sırası)
x[i] = max(x[i + 1], t[i] + x[i + 2]) # içeride / bugün çık
if i + 1 < n:
x[i] = max(x[i], t[i] + t[i + 1] + x[i + 3]) # bugün + yarın çık
return x # x[0] = cevap
```
**Karmaşıklık.** $n$ alt problem $\times\ O(1) = O(n)$.
```{python}
#| label: fig-tim-plan
#| fig-cap: "Tim'in suffix-DP optimali — Problem 1 İMZA. Veri MOTORDAN (t=[5,−2,8,6,−4,7,3], x[0..6]=[29,24,24,16,10,10,3], plan [tek@0, çift@2, çift@5], bitmask brute = 29). ÜST: 7 gün şeridi — negatif sıcaklıklar slate dolgulu (soğuk, zorunlu mola), çıkılan günler amber çerçeveli; gün 0 TEK (dışarı +5), gün 2-3 ve 5-6 ÇİFT amber kemerleri (8+6=14, 7+3=10), gün 1 ve 4 içeride; 'en fazla 2 gün üst üste' kural rozeti; sağ toplam kutusu 5+14+10 = 29. ALT: x(i) suffix tablosu i=6→0 (sağdan sola çöz, soldan oku); her hücrede kazanan seçenek (içeride x(i+1) / tek t+x(i+2) / çift t+t'+x(i+3)) + amber ebeveyn okları; üç-seçenek lejantı; taban x(n)=x(n+1)=x(n+2)=0; 'izin VAR varsayımı kısıtı alt-probleme göm' notu. Alt not: Solomon 2:35 'way of life' — kısıtı durum değişkenine taşı, recurrence yerel kalsın; O(n)."
#| fig-width: 11.5
#| fig-height: 6.8
# fig-tim-plan — PS8 Problem 1 İMZA: suffix-DP + durum izleme.
# Veri MOTORDAN (elle kopya YOK): build_tim_example / tim_happiness / tim_plan /
# brute_tim. Setup globalleri: plt, FancyBboxPatch, FancyArrowPatch, Circle, COL_*.
T = build_tim_example() # [5, -2, 8, 6, -4, 7, 3]
X = tim_happiness(T) # x[0..6] = [29,24,24,16,10,10,3]
PLAN = tim_plan(T) # [(0,'tek'), (2,'çift'), (5,'çift')]
BRUTE = brute_tim(T) # 29
N = len(T)
# Plan eyleminden her güne bir "rol" türet (figür izini motordan kur).
DAY_ROLE = ["?"] * N
ARCS = []
for (i, act) in PLAN:
if act == "tek":
DAY_ROLE[i] = "tek-out"
if i + 1 < N:
DAY_ROLE[i + 1] = "inside"
elif act == "çift":
DAY_ROLE[i] = "cift-out"
DAY_ROLE[i + 1] = "cift-out"
ARCS.append((i, i + 1))
if i + 2 < N:
DAY_ROLE[i + 2] = "inside"
else:
DAY_ROLE[i] = "inside"
CONTRIB = []
for (i, act) in PLAN:
if act == "çift":
CONTRIB.append(T[i] + T[i + 1])
elif act == "tek":
CONTRIB.append(T[i])
else:
CONTRIB.append(0)
TOTAL = sum(CONTRIB)
# --- ASSERT: motor değerleri sabit (uydurma sayı yasak) ---
assert T == [5, -2, 8, 6, -4, 7, 3], T
assert X[0:7] == [29, 24, 24, 16, 10, 10, 3], X[0:7]
assert PLAN == [(0, "tek"), (2, "çift"), (5, "çift")], PLAN
assert BRUTE == 29 and X[0] == BRUTE
assert CONTRIB == [5, 14, 10] and TOTAL == 29
def _draw_day_strip(ax, ox, oy):
cw, ch = 1.12, 0.92
gap = 0.18
pitch = cw + gap
centers = []
for k in range(N):
x = ox + k * pitch
val = T[k]
role = DAY_ROLE[k]
neg = val < 0
if neg:
fc, ec, lw = COL_SLATE_400, COL_PRIMARY, 1.6
txt_col = COL_WHITE
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.7
txt_col = COL_TEXT
if role in ("tek-out", "cift-out"):
ec, lw = COL_ACCENT, 2.6
if not neg:
fc = COL_AMBER_100
ax.add_patch(FancyBboxPatch(
(x, oy), cw, ch, boxstyle="round,pad=0.02,rounding_size=0.07",
fc=fc, ec=ec, linewidth=lw, zorder=3))
cx, cy = x + cw * 0.5, oy + ch * 0.5
centers.append((cx, cy))
ax.text(cx, cy + 0.06, f"{val:+d}", ha="center", va="center",
fontsize=13, color=txt_col, weight="bold", zorder=5)
ax.text(cx, oy - 0.22, f"gün {k}", ha="center", va="center",
fontsize=8.2, color=COL_SLATE_500, zorder=5)
for k in range(N):
if DAY_ROLE[k] != "inside":
continue
cx, cy = centers[k]
ax.add_patch(FancyBboxPatch(
(cx - cw * 0.5, oy), cw, ch,
boxstyle="round,pad=0.02,rounding_size=0.07",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.3, zorder=4, alpha=0.55))
ax.text(cx, oy + ch + 0.30, "içeride", ha="center", va="center",
fontsize=8.4, color=COL_SLATE_500, weight="bold", zorder=6)
ax.add_patch(Circle((cx, oy + ch + 0.62), 0.10, facecolor=COL_BG,
edgecolor=COL_SLATE_500, linewidth=1.4, zorder=6))
ax.text(cx, oy + ch + 0.62, "✕", ha="center", va="center",
fontsize=8.0, color=COL_SLATE_500, weight="bold", zorder=7)
ax.text(cx, oy + ch + 0.92, "zorunlu mola", ha="center", va="center",
fontsize=7.0, color=COL_SLATE_500, style="italic", zorder=6)
for (i, act) in PLAN:
if act != "tek":
continue
cx, cy = centers[i]
ax.add_patch(FancyArrowPatch(
(cx, oy + ch + 0.02), (cx, oy + ch + 0.30),
arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_700,
linewidth=2.0, zorder=6))
ax.text(cx, oy + ch + 0.50, f"TEK · dışarı +{T[i]}", ha="center",
va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold",
zorder=6)
for (i, j) in ARCS:
cxi, cy = centers[i]
cxj, _ = centers[j]
mid = (cxi + cxj) / 2
top = oy + ch + 0.66
ax.add_patch(FancyArrowPatch(
(cxi, oy + ch + 0.02), (cxj, oy + ch + 0.02),
arrowstyle="-", mutation_scale=1, color=COL_ACCENT,
linewidth=2.8, zorder=6, connectionstyle="arc3,rad=-0.45"))
s = T[i] + T[j]
ax.add_patch(FancyBboxPatch(
(mid - 0.62, top), 1.24, 0.40,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=7))
ax.text(mid, top + 0.20, f"ÇİFT · {T[i]}+{T[j]} = {s}", ha="center",
va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold",
zorder=8)
ax.add_patch(FancyBboxPatch(
(ox - 0.05, oy + ch + 1.32), 3.05, 0.46,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_AMBER_700, linewidth=1.8, zorder=5))
ax.text(ox + 1.475, oy + ch + 1.55,
"kural: en fazla 2 gün ÜST ÜSTE dışarı", ha="center", va="center",
fontsize=9.0, color=COL_AMBER_700, weight="bold", zorder=6)
sum_str = " + ".join(str(c) for c in CONTRIB)
tx = ox + N * pitch + 0.18
ax.add_patch(FancyBboxPatch(
(tx, oy + 0.02), 2.55, ch - 0.04,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=5))
ax.text(tx + 1.275, oy + ch * 0.66, f"{sum_str}", ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(tx + 1.275, oy + ch * 0.30, f"= {TOTAL}", ha="center", va="center",
fontsize=14, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(tx + 1.275, oy - 0.22, "max mutluluk x(0)", ha="center",
va="center", fontsize=7.6, color=COL_SLATE_500, style="italic",
zorder=6)
ax.text(ox + (N * pitch) / 2 - 0.1, oy + ch + 2.10,
"① 7 günlük plan izi — Tim'in suffix-DP optimali",
ha="center", va="center", fontsize=12, color=COL_TEXT,
weight="bold", zorder=6)
def _winning_choice(i):
if i + 1 < N and X[i] == T[i] + T[i + 1] + X[i + 3]:
return "çift", f"t[{i}]+t[{i+1}]+x({i+3})"
elif X[i] == T[i] + X[i + 2]:
return "tek", f"t[{i}]+x({i+2})"
else:
return "içeride", f"x({i+1})"
def _draw_x_table(ax, ox, oy):
cw, ch = 1.30, 0.86
gap = 0.34
pitch = cw + gap
order = list(range(N - 1, -1, -1)) # [6,5,4,3,2,1,0]
centers = {}
col_of = {}
for col, i in enumerate(order):
col_of[i] = col
for col, i in enumerate(order):
choice, _ = _winning_choice(i)
if choice == "içeride":
deps = [i + 1]
elif choice == "tek":
deps = [i + 2]
else:
deps = [i + 3]
cx0 = ox + col * pitch + cw * 0.5
for d in deps:
hot = (choice != "içeride") and any(pi == i for (pi, _) in PLAN)
if d not in col_of:
ax.add_patch(FancyArrowPatch(
(cx0 + cw * 0.30, oy + ch + 0.06),
(cx0 + pitch * 0.55, oy + ch + 0.34),
arrowstyle="-|>", mutation_scale=10,
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.0 if hot else 1.1, zorder=2,
connectionstyle="arc3,rad=0.30"))
continue
cx1 = ox + col_of[d] * pitch + cw * 0.5
span = abs(col_of[d] - col)
rad = -0.16 - 0.10 * span
ax.add_patch(FancyArrowPatch(
(cx0, oy + ch + 0.04), (cx1, oy + ch + 0.04),
arrowstyle="-|>", mutation_scale=11,
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.2 if hot else 1.1, zorder=2,
connectionstyle=f"arc3,rad={rad}"))
for col, i in enumerate(order):
x = ox + col * pitch
choice, formula = _winning_choice(i)
on_plan = any(pi == i for (pi, _) in PLAN)
if on_plan:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.8
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.6
ax.add_patch(FancyBboxPatch(
(x, oy), cw, ch, boxstyle="round,pad=0.02,rounding_size=0.07",
fc=fc, ec=ec, linewidth=lw, zorder=5))
cx, cy = x + cw * 0.5, oy + ch * 0.5
centers[i] = (cx, cy)
ax.text(cx, cy + 0.13, f"x({i})={X[i]}", ha="center", va="center",
fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6)
ccol = COL_AMBER_700 if choice != "içeride" else COL_SLATE_500
ax.text(cx, cy - 0.20, choice, ha="center", va="center",
fontsize=8.8, color=ccol, weight="bold", zorder=6)
ax.text(cx, oy - 0.20, formula, ha="center", va="center",
fontsize=7.2, color=COL_SLATE_500, zorder=6)
bx = ox + N * pitch + 0.10
cy = oy + ch * 0.5
ax.add_patch(FancyBboxPatch(
(bx, oy + 0.06), 1.85, ch - 0.12,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.5, zorder=3))
ax.text(bx + 0.925, cy + 0.10, "taban", ha="center", va="center",
fontsize=9.0, color=COL_SLATE_500, weight="bold", zorder=5)
ax.text(bx + 0.925, cy - 0.18, "x(n)=x(n+1)=x(n+2)=0", ha="center",
va="center", fontsize=7.4, color=COL_SLATE_500, zorder=5)
lx = ox + N * pitch + 0.12
ly = oy + ch + 1.18
legend = [
("içeride →", "x(i+1)", COL_SLATE_500),
("tek →", "t[i] + x(i+2)", COL_AMBER_700),
("çift →", "t[i] + t[i+1] + x(i+3)", COL_AMBER_700),
]
ax.add_patch(FancyBboxPatch(
(lx - 0.08, ly - 0.78), 3.05, 1.32,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.2, zorder=4))
ax.text(lx + 0.05, ly + 0.38, "üç yerel seçenek (max):", ha="left",
va="center", fontsize=8.6, color=COL_TEXT, weight="bold", zorder=6)
for r, (name, frm, col) in enumerate(legend):
yy = ly + 0.10 - r * 0.30
ax.text(lx + 0.05, yy, name, ha="left", va="center", fontsize=8.2,
color=col, weight="bold", zorder=6)
ax.text(lx + 1.02, yy, frm, ha="left", va="center", fontsize=8.0,
color=COL_SLATE_500, zorder=6)
ax.text(ox + (N * pitch) / 2 - 0.1, oy + ch + 1.92,
"② suffix tablosu x(i) — i = 6 → 0 (sağdan sola çöz, soldan oku)",
ha="center", va="center", fontsize=12, color=COL_TEXT,
weight="bold", zorder=6)
ax.text(ox + (N * pitch) / 2 - 0.1, oy - 0.70,
"x(i) tanımı 'gün i'de dışarı çıkma İZNİ var' varsayar → "
"'en fazla 2 üst üste' kısıtı alt-problem TANIMINA gömülü "
"(durum bilgisi i'de saklı, recurrence yerel kalır)",
ha="center", va="center", fontsize=8.3, color=COL_AMBER_700,
weight="bold", zorder=6)
fig, (ax_top, ax_bot) = plt.subplots(
2, 1, figsize=(11.5, 6.8),
gridspec_kw={"height_ratios": [1.0, 0.92]})
fig.patch.set_facecolor(COL_WHITE)
ax_top.set_facecolor(COL_WHITE)
_draw_day_strip(ax_top, 0.55, 0.0)
ax_top.set_xlim(-0.4, 14.9)
ax_top.set_ylim(-0.55, 3.30)
ax_top.set_aspect("equal")
ax_top.axis("off")
ax_bot.set_facecolor(COL_WHITE)
_draw_x_table(ax_bot, 0.0, 0.0)
ax_bot.set_xlim(-0.4, 14.9)
ax_bot.set_ylim(-1.05, 2.95)
ax_bot.set_aspect("equal")
ax_bot.axis("off")
fig.suptitle(
"Tim the Beaver (PS8 P1): suffix-DP + durum izleme — "
"'izin var' varsayımını alt-problem tanımına göm",
color=COL_TEXT, fontsize=13, weight="bold", y=0.995)
fig.text(
0.5, 0.012,
"Solomon PS8 2:35 — \"way of life\": kısıtı durum değişkenine taşı, "
"recurrence yerel kalsın · x(i) = max( x(i+1), t[i]+x(i+2), "
"t[i]+t[i+1]+x(i+3) ) · O(n)",
ha="center", va="bottom", fontsize=8.4, color=COL_SLATE_500,
style="italic")
plt.tight_layout(rect=(0, 0.03, 1, 0.96))
plt.show()
```
## Problem 2: Menix Edit Distance — Precomputation {#sec-problem-2-d25}
**İfade.** İki dosya $A, B$ ($n$ satır; her satır uzunluğu $\le k$). Satır **ekle/sil** pahalı ($1$), bitişik **takas (swap)** bedava (yalnız faydalıysa). Yalnız $A$ düzenlenir. $A$'yı $B$'ye çeviren minimum **takas-dışı** işlem sayısı; hedef $O(kn + n^2)$.
::: {.callout-tip title="Yaklaşım — klasik edit distance artı bir satır: precomputation'ı çalışma süresine taşı"}
Klasik **edit distance** DP'si suffix çiftiyle kurulur, üstüne küçük bir ek. Dosyayı *satır satır, sırayla* düzenle (atlamadan) → iki uçtan değil, suffix çift. Asıl incelik karmaşıklıkta: her $A[i] = B[j]$ karşılaştırması iki satırın string eşitliğidir, yani $O(k)$. Naif DP $n^2$ alt problemin her birinde $O(k)$ iş yapar. Hile: satırları önce $O(k)$ ile bir kimliğe (hash) **ön-işle** (toplam $kn$), sonra DP'de $O(1)$ karşılaştır ($n^2$) → $O(kn + n^2)$. Çalışma süresindeki $k$, satır karşılaştırmasının ipucudur.
:::
> *"the way that I would edit a file... would be linearly."* — Solomon, 39:33
**Çözüm.** **S:** $x(i, j) = A[i:] \to B[j:]$ minimum iş. **R** (min, dört durum): $A[i] = B[j] \to x(i+1, j+1)$; $A[i]$ sil $\to 1 + x(i+1, j)$; satır ekle ($B[j]$ eşle) $\to 1 + x(i, j+1)$; takas ($A[i+1] = B[j] \wedge A[i] = B[j+1]$) $\to x(i+2, j+2)$. **T:** $i+j$ artan (2B tabloda sağ-aşağı). **B:** $x(n+1, j) = n+1-j$; $x(i, n+1) = n+1-i$. **O:** $x(1, 1)$.
Örnek $A = [\alpha, \beta, \gamma, \delta]$, $B = [\beta, \alpha, \gamma, \varepsilon]$ için cevap $2$: takas ($\alpha, \beta$) bedava + $\gamma$ eşle + $\delta$ sil + $\varepsilon$ ekle. Bu DP'nin doğruluğunu **ikinci bir çerçeve** teyit eder: edit distance, durum $(i, j)$'leri düğüm, eşle/takas kenarları $0$-ağırlık, sil/ekle kenarları $1$-ağırlık olan bir **grid-DAG üzerinde en kısa yoldur** (bu, [Ders 24'ün LCS-grid'inin](24-dp2-lcs-lis-oyunlar.qmd#sec-4-lcs-recurrence) ve Ders 23'te kurulan "her DP bir DAG'da en kısa yola indirgenebilir" köprüsünün doğrudan akrabasıdır). Motorda bu grid-DAG'ı $(0,0) \to (n, n)$ koşan bağımsız tanık bir **Dijkstra**'dır; aynı örnekte o da $2$ verir, ve önce kimliklenmiş satırlarla koşulan precomputation sürümü de aynı cevabı üretir.
```python
def edit_distance_swaps(A, B): # O(n²) alt problem; precompute → O(kn + n²)
na, nb = len(A), len(B)
x = {}
for j in range(nb + 1): x[(na, j)] = nb - j # taban: kalanı ekle
for i in range(na + 1): x[(i, nb)] = na - i # taban: kalanı sil
for i in range(na - 1, -1, -1):
for j in range(nb - 1, -1, -1):
best = min(1 + x[(i + 1, j)], 1 + x[(i, j + 1)]) # sil / ekle
if A[i] == B[j]: # eşle (bedava)
best = min(best, x[(i + 1, j + 1)])
if i + 1 < na and j + 1 < nb \
and A[i + 1] == B[j] and A[i] == B[j + 1]: # takas (bedava)
best = min(best, x[(i + 2, j + 2)])
x[(i, j)] = best
return x[(0, 0)]
```
**Karmaşıklık.** $n^2$ alt problem $\times\ O(1)$ — *ama* her $A[i] = B[j]$ satır karşılaştırması $O(k)$. Satırları önce $O(k)$ ile bir kimliğe ön-işle (toplam $kn$), sonra DP'de $O(1)$ karşılaştır ($n^2$) → $O(kn + n^2)$. (Bu, "alt problem $\times$ iş" formülüne ön-işlemenin eklendiği nadir bir durumdur.)
## Problem 3: Saggy'nin Blok Kulesi — LIS-benzeri {#sec-problem-3-d25}
**İfade.** $n$ blok, her biri $w \times h \times l$ (istenildiği gibi döndürülebilir; her tipten $\ge 3$ adet). Maksimum kule yüksekliği; her blok altındakinde **kesin (strict) destekli** olmalı.
::: {.callout-tip title="Yaklaşım — kesin destek bir sıralama doğurur: sırala, sonra LIS-benzeri DP koş"}
$2^n$ olası alt küme gibi görünür; ama üç gözlemle **LIS'e** indirger. (1) Uzun-kenarı uzun-kenara hizala → her taban sıralı bir (küçük, büyük) çifti. (2) Kesin destek → her **yönelim** (hangi eksen yukarı) en fazla **bir kez** kullanılır → her bloktan en fazla 3 yönelim. (3) Destek koşulu, taban kenarlarını her katta **azaltır** → liste **sıralanabilir**. Sıraladıktan sonra "alt blok daha büyük taban" zinciri tam olarak en uzun artan alt-dizilim kalıbıdır; yerel kaba kuvvetle her yönelimi tepe yapıp altına gelebilecek en yüksek alt-kuleyi ara.
:::
> *"we can sort by the edge lengths because we know that we have this support condition."* — Solomon, 1:03:09
@fig-tower-lis bu indirgemeyi motordan **gerçek** verilerle gösterir: iki blok tipi $\{1 \times 2 \times 3,\ 2 \times 3 \times 4\}$ altı yönelime açılır, taban azalan lexicographic sıralanır; LIS-benzeri DP en yüksek kuleyi $9$ bulur — taban $(3, 4)$ dikey $2$, üstüne $(2, 3)$ dikey $4$, üstüne $(1, 2)$ dikey $3$ ($2 + 4 + 3 = 9$). Bağımsız zincir-DFS tanığı da $9$ verir.
**Çözüm.** Her bloğu sıralı ($w \le h \le l$) 3 yönelime aç, listeyi lexicographic sırala, tekrarları çıkar. **S:** $x(i) = $ blok $i$'yi **tepe** yaparak ilk $i$ blokla kurulabilen maksimum yükseklik. **R:** $x(i) = v_i + \max(\{x(j) : j < i,\ a_i < a_j,\ b_i < b_j\} \cup \{0\})$, burada $(a_i, b_i)$ yönelim $i$'nin tabanı ve $v_i$ dikey kenarıdır; koşul $a_i < a_j \wedge b_i < b_j$, blok $i$'nin blok $j$'nin üstüne kesin destekle sığması demektir. **O:** $\max_i x(i)$. **B:** $x(1) = v_1$.
```python
def tower_height(blocks): # O(n log n) + n×O(n) = O(n²)
ori = block_orientations(blocks) # sıralı 3 yönelim/blok, lex sıralı
n = len(ori)
x = [0] * n
for i in range(n):
a, b, v = ori[i]
best = 0
for j in range(i): # LIS-benzeri tarama
aj, bj, _ = ori[j]
if a < aj and b < bj: # kesin destek: İKİ kenar da küçük
best = max(best, x[j])
x[i] = v + best
return max(x), ori, x
```
**Karmaşıklık.** Ön sıralama $O(n \log n)$ + $n$ alt problem $\times\ O(n)$ iş = $O(n^2)$.
```{python}
#| label: fig-tower-lis
#| fig-cap: "Saggy'nin blok kulesi: sırala + LIS-benzeri DP — Problem 3. Veri MOTORDAN ({1×2×3, 2×3×4} → 6 yönelim, kule = 9, zincir [0,2,5], zincir-DFS brute = 9). SOL: kazanan 3-katlı kule kesiti (yandan) — taban (3,4) dikey 2 (en geniş), üstüne (2,3) dikey 4, üstüne (1,2) dikey 3; genişlikler taban-a ile orantılı KESİN küçülür ((3,4)⊃(2,3)⊃(1,2)); sağda yükseklik ölçek çubuğu toplam = 9; sol kenarda 'kesin destek: iki taban kenarı da küçük' notu. SAĞ: 6 yönelimin azalan-lex tablosu (taban-a, taban-b, dikey v, x(i)); kazanan satırlar (i=0,2,5) amber; sola yaylı LIS-zinciri okları 0→2→5 (2+4+3=9); altta üç gözlem + Solomon 1:03:09. Alt başlık: yükseklik = 9."
#| fig-width: 11.5
#| fig-height: 6.2
# fig-tower-lis — PS8 Problem 3: blok kulesi → sırala + LIS-benzeri DP.
# Veri MOTORDAN: build_tower_example / block_orientations / tower_height /
# brute_tower. Setup globalleri: plt, FancyBboxPatch, FancyArrowPatch, COL_*.
blocks = build_tower_example()
assert blocks == [(1, 2, 3), (2, 3, 4)], blocks
ori = block_orientations(blocks)
assert len(ori) == 6, len(ori)
assert ori == [(3, 4, 2), (2, 4, 3), (2, 3, 4),
(2, 3, 1), (1, 3, 2), (1, 2, 3)], ori
h, ori2, x = tower_height(blocks)
assert h == 9 and ori2 == ori
assert x == [2, 3, 6, 3, 5, 9], x
assert brute_tower(blocks) == 9
# Kazanan zincir (LIS-benzeri geri-kurma): tepe = max(x) indeksi, geriye git.
chain = []
i = x.index(max(x)) # tepe = 5
while i is not None:
chain.append(i)
a, b, v = ori[i]
nxt = None
for j in range(i):
aj, bj, _ = ori[j]
if a < aj and b < bj and v + x[j] == x[i]:
nxt = j
i = nxt
chain.reverse() # tabandan tepeye: [0, 2, 5]
assert chain == [0, 2, 5], chain
assert sum(ori[k][2] for k in chain) == h
chain_set = set(chain)
layers = [ori[k] for k in chain]
assert layers == [(3, 4, 2), (2, 3, 4), (1, 2, 3)], layers
fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.5, 6.2))
fig.patch.set_facecolor(COL_WHITE)
# --- SOL PANEL: 3-katlı kule kesiti ---
axL.set_facecolor(COL_WHITE)
WIDTH_BASE = 1.7
WIDTH_SCALE = 0.85
x_center = 0.0
y_cursor = 0.0
layer_fcs = [COL_AMBER_100, COL_AMBER_300, COL_AMBER_600]
layer_txt = [COL_TEXT, COL_TEXT, COL_WHITE]
widths = [WIDTH_BASE + a * WIDTH_SCALE for (a, b, v) in layers]
assert widths[0] > widths[1] > widths[2], widths
for li, (a, b, v) in enumerate(layers):
w = widths[li]
axL.add_patch(FancyBboxPatch(
(x_center - w / 2, y_cursor), w, v, boxstyle="square,pad=0.0",
fc=layer_fcs[li], ec=COL_AMBER_700, linewidth=2.4, zorder=3))
axL.text(x_center, y_cursor + v / 2,
f"taban {a}×{b}\ndikey = {v}",
ha="center", va="center", fontsize=10,
color=layer_txt[li], weight="bold", zorder=5)
y_cursor += v
assert abs(y_cursor - h) < 1e-9, y_cursor
bar_x = widths[0] / 2 + 0.55
axL.add_patch(FancyArrowPatch(
(bar_x, 0.0), (bar_x, h), arrowstyle="<|-|>", mutation_scale=14,
color=COL_PRIMARY, linewidth=1.8, zorder=4))
for yt in range(0, h + 1):
axL.plot([bar_x - 0.06, bar_x + 0.06], [yt, yt],
color=COL_SLATE_400, linewidth=1.0, zorder=4)
axL.text(bar_x + 0.18, h / 2, f"toplam\nyükseklik\n= {h}",
ha="left", va="center", fontsize=10.5, color=COL_PRIMARY,
weight="bold", zorder=5)
y_b1 = layers[0][2]
left_w0 = widths[0]
axL.annotate(
"kesin destek:\niki taban kenarı da KÜÇÜK\n(3,4) ⊃ (2,3) ⊃ (1,2)",
xy=(-left_w0 / 2, y_b1), xytext=(-left_w0 / 2 - 1.9, h * 0.55),
fontsize=9, color=COL_AMBER_700, weight="bold", ha="center", va="center",
arrowprops=dict(arrowstyle="-|>", color=COL_AMBER_700, linewidth=1.6),
zorder=6)
axL.set_title("Kazanan kule kesiti (yandan)", color=COL_TEXT,
fontsize=12.5, weight="bold")
axL.set_xlim(-left_w0 / 2 - 2.9, bar_x + 1.7)
axL.set_ylim(-0.7, h + 0.9)
axL.set_aspect("equal")
axL.axis("off")
# --- SAĞ PANEL: 6 yönelim azalan-lex tablo + LIS zinciri ---
axR.set_facecolor(COL_WHITE)
col_a_x = 0.0
col_b_x = 1.35
col_v_x = 2.70
col_x_x = 4.35
row_h = 1.0
top_y = 0.0
cell_w = 1.05
hdr_y = top_y + row_h
for cx, htxt in [(col_a_x, "taban-a"), (col_b_x, "taban-b"),
(col_v_x, "dikey v"), (col_x_x, "x(i)")]:
axR.text(cx, hdr_y, htxt, ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold")
axR.text(-1.05, hdr_y, "i", ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold")
row_centers = []
for ri, (a, b, v) in enumerate(ori):
y = top_y - ri * row_h
row_centers.append(y)
win = ri in chain_set
fc = COL_AMBER_100 if win else COL_BG
ec = COL_ACCENT if win else COL_SLATE_400
lw = 2.6 if win else 1.4
axR.text(-1.05, y, str(ri), ha="center", va="center",
fontsize=10, color=(COL_AMBER_700 if win else COL_SLATE_500),
weight="bold")
for cx, val in [(col_a_x, a), (col_b_x, b), (col_v_x, v)]:
axR.add_patch(FancyBboxPatch(
(cx - cell_w / 2, y - row_h * 0.42), cell_w, row_h * 0.84,
boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=2))
axR.text(cx, y, str(val), ha="center", va="center",
fontsize=11, color=COL_TEXT, weight="bold", zorder=4)
axR.text(col_x_x, y, f"x({ri}) = {x[ri]}", ha="center", va="center",
fontsize=10.5, color=(COL_AMBER_700 if win else COL_SLATE_500),
weight="bold", zorder=4)
arrow_x = col_a_x - cell_w / 2 - 0.18
for lower, upper in zip(chain, chain[1:]):
y_lo = row_centers[lower]
y_up = row_centers[upper]
axR.add_patch(FancyArrowPatch(
(arrow_x, y_lo), (arrow_x, y_up), arrowstyle="-|>", mutation_scale=15,
color=COL_ACCENT, linewidth=2.4, zorder=6,
connectionstyle="arc3,rad=-0.45"))
mid_y = (row_centers[chain[0]] + row_centers[chain[-1]]) / 2
axR.text(arrow_x - 1.05, mid_y,
f"LIS zinciri\n0 → 2 → 5\n2+4+3 = {h}",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=6)
axR.set_title("6 yönelim (azalan-lex) + kazanan LIS zinciri",
color=COL_TEXT, fontsize=12.5, weight="bold")
note_y = top_y - len(ori) * row_h - 0.25
axR.text(col_a_x - 1.0, note_y,
"Gözlemler:\n"
"• uzun kenarı hizala → taban = (küçük, büyük) çift\n"
"• her yönelim ≤ 1 kez kullanılır → blok başına 3 yönelim\n"
"• kesin destek (iki kenar < ) → kuleyi SIRALANABİLİR kılar\n"
" Solomon 1:03:09 → sırala + LIS-benzeri DP = O(n²)",
ha="left", va="top", fontsize=8.6, color=COL_SLATE_500, zorder=4)
axR.set_xlim(arrow_x - 1.75, col_x_x + 1.25)
axR.set_ylim(note_y - 1.55, hdr_y + 0.7)
axR.set_aspect("equal")
axR.axis("off")
fig.suptitle(
"PS8 P3 — Saggy'nin blok kulesi: sırala + LIS-benzeri DP (yükseklik = 9)",
fontsize=13.5, color=COL_TEXT, weight="bold", y=0.99)
fig.tight_layout(rect=(0, 0, 1, 0.96))
plt.show()
```
## Problem 4: Princess Plum Izgarası — Yol Sayma {#sec-problem-4-d25}
**İfade.** $n \times n$ ızgara; her hücre mushroom / ağaç / boş. Sol-üstten sağ-alta **hızlı yol** ($2n - 1$ hücre — yalnız aşağı/sağ; ağaca girilmez). (a) Toplanabilecek **maksimum mushroom** $k$; (b) $k$ mushroom toplayan **hızlı yol sayısı**.
::: {.callout-tip title="Yaklaşım — iki ardışık DP: önce hedefi hesapla, sonra max yerine toplayarak say"}
"Hızlı" = tam $2n - 1$ hücre → yalnız **aşağı ve sağ** (yukarı/sol path'i uzatır). Izgara zaten bir DAG (sağ-aşağı). İki ardışık DP gerekir. (a) max mushroom için klasik ızgara DP: her hücreye gelen iki komşudan en iyisini al. (b) "kaç yol" sorusu kritik bir değişiklik ister: recurrence'da **max yerine toplama** — bir komşu optimal mushroom sayısına ulaşıyorsa onun yol sayısını ekle. Pozitif sayılar yalnız **taban durumdan** doğar; $1$'lerin kaynağı $x(0, 0) = 1$'dir.
:::
> *"she can only move down and to the right because if she moved up or to the left, her path would no longer be called quick."* — Solomon, 1:21:32
@fig-plum-grid bu iki DP'yi motordan **gerçek** verilerle gösterir: $4 \times 4$ örnekte max mushroom $k = 2$ ve onu toplayan **tam 3** hızlı yol vardır. Bağımsız tüm-monoton-yollar tanığı da $(2, 3)$ verir; ek bir kontrol olarak tamamen kapalı bir $2 \times 2$ ızgara $k = -\infty$ ve yol sayısı $0$ döndürür (taban dışında pozitif sayı doğmaz).
**Çözüm.** **(a) max mushroom:** $k(i, j) = \chi(i, j) + \max(k(i-1, j),\ k(i, j-1))$; ağaç $\to -\infty$. ($\chi = $ hücrede mushroom varsa $1$, yoksa $0$.) Base: $k(1, 1) = 0$. **(b) yol sayısı:** $x(i, j) = (i, j)$'de biten, $k(i, j)$ mushroom toplayan hızlı yol sayısı. Soldan ve/veya yukarıdan gelen bir komşu için, o komşunun $k$ değeri artı $\chi(i, j)$ tam olarak $k(i, j)$'ye eşitse, o komşunun yol sayısını $x(i, j)$'ye **ekle** (**max değil, toplama** — yol sayıyoruz). Base: $x(1, 1) = 1$. **O:** $x(n, n)$. Pozitif sayılar yalnız **taban durumdan** doğar.
> *"all of the reason why the positive numbers appear in this problem is from the base case."* — Solomon, 1:33:02
```python
def plum_count_paths(grid): # (b) yol-sayma DP
n, m = len(grid), len(grid[0])
k = plum_max_mushroom(grid) # (a) önce max mushroom (ayrı DP)
x = {}
for i in range(n):
for j in range(m):
if grid[i][j] == "T" or k[(i, j)] == -INF:
x[(i, j)] = 0; continue
if i == 0 and j == 0:
x[(i, j)] = 1; continue # taban: pozitiflerin TEK kaynağı
chi = 1 if grid[i][j] == "m" else 0
cnt = 0
if i > 0 and k[(i - 1, j)] + chi == k[(i, j)]: cnt += x[(i - 1, j)] # TOPLA
if j > 0 and k[(i, j - 1)] + chi == k[(i, j)]: cnt += x[(i, j - 1)] # max DEĞİL
x[(i, j)] = cnt
goal = (n - 1, m - 1)
return k[goal], x[goal], x
```
**Karmaşıklık.** İki DP, her biri $n^2$ hücre $\times\ O(1)$ → $O(n^2)$.
```{python}
#| label: fig-plum-grid
#| fig-cap: "Princess Plum: max-mushroom DP → yol-sayma DP — Problem 4 İMZA. Veri MOTORDAN (4×4 grid, max k=2, TAM 3 yol, tüm-monoton-yollar brute = (2,3)). SOL: 4×4 ızgara — mushroom (amber m), ağaç (koyu T, geçilmez), boş (beyaz); S başlangıç, H hedef; ÜÇ optimal yol farklı çizgi stiliyle (her biri 2 mushroom: üst m-çifti 1 rota + sol-alt m-çifti 2 rota). SAĞ-ÜST: k(i,j) max-mushroom DP tablosu (k = χ + max(yukarı, sol); ağaç → −∞). SAĞ-ALT: x(i,j) yol-sayma DP tablosu (k eşleşirse TOPLA, max DEĞİL); pozitif sayılar amber, taban x(0,0)=1 amber çerçeveli — pozitiflerin TEK kaynağı (Solomon 1:33:02). Alt: iki ardışık DP, her biri O(n²)."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-plum-grid — PS8 Problem 4 İMZA: max-mushroom + yol sayma (iki ardışık DP).
# Veri MOTORDAN: build_plum_example / plum_count_paths / brute_plum /
# plum_max_mushroom + INF. Setup globalleri: plt, FancyBboxPatch, COL_*, INF.
grid = build_plum_example()
assert grid == [".m..", ".Tm.", "m..T", ".m.."], grid
n, m = len(grid), len(grid[0])
assert (n, m) == (4, 4), (n, m)
k_goal, cnt, xtab = plum_count_paths(grid)
assert k_goal == 2 and cnt == 3
assert brute_plum(grid) == (2, 3), brute_plum(grid)
kmap = plum_max_mushroom(grid)
# Üç optimal yolu KENDİM üret (DFS) + assert tam 3 yol, her biri 2 mushroom
_opt = []
def _enum(i, j, count, path):
if grid[i][j] == "T":
return
count2 = count + (1 if grid[i][j] == "m" else 0)
path2 = path + [(i, j)]
if (i, j) == (n - 1, m - 1):
_opt.append((count2, path2))
return
if i + 1 < n:
_enum(i + 1, j, count2, path2)
if j + 1 < m:
_enum(i, j + 1, count2, path2)
_enum(0, 0, 0, [])
_best = max(c for c, _ in _opt)
optimal_paths = [p for c, p in _opt if c == _best]
assert _best == 2 and len(optimal_paths) == 3
for _p in optimal_paths:
assert sum(1 for (i, j) in _p if grid[i][j] == "m") == 2
_top_mushrooms = {(0, 1), (1, 2)}
_botleft_mushrooms = {(2, 0), (3, 1)}
_top_routes = [p for p in optimal_paths if _top_mushrooms.issubset(set(p))]
_botleft_routes = [p for p in optimal_paths if _botleft_mushrooms.issubset(set(p))]
assert len(_top_routes) == 1 and len(_botleft_routes) == 2
fig = plt.figure(figsize=(12, 6))
gs = fig.add_gridspec(2, 2, width_ratios=[1.0, 1.0], height_ratios=[1.0, 1.0],
hspace=0.42, wspace=0.18,
left=0.04, right=0.97, top=0.90, bottom=0.06)
ax_grid = fig.add_subplot(gs[:, 0])
ax_k = fig.add_subplot(gs[0, 1])
ax_x = fig.add_subplot(gs[1, 1])
CELL = 1.0
def _cell_xy(i, j):
return j * CELL, (n - 1 - i) * CELL
def _cell_center(i, j):
x, y = _cell_xy(i, j)
return x + CELL * 0.5, y + CELL * 0.5
for i in range(n):
for j in range(m):
x, y = _cell_xy(i, j)
ch = grid[i][j]
if ch == "T":
fc, ec = COL_PRIMARY, COL_PRIMARY
elif ch == "m":
fc, ec = COL_AMBER_100, COL_AMBER_600
else:
fc, ec = COL_WHITE, COL_SLATE_400
ax_grid.add_patch(FancyBboxPatch(
(x + 0.02, y + 0.02), CELL * 0.96, CELL * 0.96,
boxstyle="square,pad=0.0", fc=fc, ec=ec,
linewidth=2.0 if ch != "." else 1.3, zorder=2))
cx, cy = _cell_center(i, j)
if ch == "m":
ax_grid.text(cx, cy, "m", ha="center", va="center",
fontsize=20, color=COL_AMBER_700, weight="bold", zorder=4)
elif ch == "T":
ax_grid.text(cx, cy, "T", ha="center", va="center",
fontsize=20, color=COL_WHITE, weight="bold", zorder=4)
path_styles = [
dict(color=COL_ACCENT, linestyle="-", lw=3.0, off=(-0.10, +0.10),
label="sol-alt m-çifti · rota A"),
dict(color=COL_AMBER_700, linestyle="--", lw=2.6, off=(+0.12, -0.12),
label="sol-alt m-çifti · rota B"),
dict(color=COL_PRIMARY, linestyle=":", lw=3.0, off=(+0.00, +0.00),
label="üst m-çifti · rota C"),
]
ordered_paths = _botleft_routes + _top_routes
for p, st in zip(ordered_paths, path_styles):
ox, oy = st["off"]
xs = [_cell_center(i, j)[0] + ox for (i, j) in p]
ys = [_cell_center(i, j)[1] + oy for (i, j) in p]
ax_grid.plot(xs, ys, color=st["color"], linestyle=st["linestyle"],
linewidth=st["lw"], zorder=5, label=st["label"],
solid_capstyle="round", alpha=0.95)
sx, sy = _cell_center(0, 0)
gx, gy = _cell_center(n - 1, m - 1)
ax_grid.text(sx, sy, "S", ha="center", va="center", fontsize=11,
color=COL_TEXT, weight="bold", zorder=6,
bbox=dict(boxstyle="circle,pad=0.18", fc=COL_BG, ec=COL_PRIMARY, lw=1.4))
ax_grid.text(gx, gy, "H", ha="center", va="center", fontsize=11,
color=COL_TEXT, weight="bold", zorder=6,
bbox=dict(boxstyle="circle,pad=0.18", fc=COL_BG, ec=COL_PRIMARY, lw=1.4))
ax_grid.set_xlim(-0.15, m * CELL + 0.15)
ax_grid.set_ylim(-0.15, n * CELL + 0.15)
ax_grid.set_aspect("equal")
ax_grid.axis("off")
ax_grid.set_title("max k = 2 mushroom, TAM 3 hızlı yol",
color=COL_TEXT, fontsize=13, weight="bold", pad=10)
ax_grid.legend(loc="upper center", bbox_to_anchor=(0.5, -0.02),
fontsize=8.5, framealpha=0.95, ncol=1)
def _draw_dp_table(ax, get_text, get_style, title, footer, footer_col):
tw, th = 1.0, 1.0
for i in range(n):
for j in range(m):
x = j * tw
y = (n - 1 - i) * th
fc, ec, txtcol, lw = get_style(i, j)
ax.add_patch(FancyBboxPatch(
(x + 0.03, y + 0.03), tw * 0.94, th * 0.94,
boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=2))
ax.text(x + tw * 0.5, y + th * 0.5, get_text(i, j),
ha="center", va="center", fontsize=13,
color=txtcol, weight="bold", zorder=4)
ax.set_xlim(-0.1, m * tw + 0.1)
ax.set_ylim(-0.55, n * th + 0.55)
ax.set_aspect("equal")
ax.axis("off")
ax.set_title(title, color=COL_TEXT, fontsize=12, weight="bold", pad=6)
ax.text(m * tw * 0.5, -0.40, footer, ha="center", va="center",
fontsize=9, color=footer_col, style="italic")
def _k_text(i, j):
v = kmap[(i, j)]
return "−∞" if v == -INF else str(v)
def _k_style(i, j):
v = kmap[(i, j)]
if v == -INF:
return COL_PRIMARY, COL_PRIMARY, COL_WHITE, 2.0
return COL_BG, COL_PRIMARY, COL_TEXT, 1.5
_draw_dp_table(
ax_k, _k_text, _k_style,
"k(i,j) — max-mushroom DP · k = χ + max(yukarı, sol)",
"ağaç → −∞ (geçilmez); O(n²)", COL_SLATE_500)
def _x_text(i, j):
return str(xtab[(i, j)])
def _x_style(i, j):
v = xtab[(i, j)]
if grid[i][j] == "T" or kmap[(i, j)] == -INF:
return COL_PRIMARY, COL_PRIMARY, COL_WHITE, 2.0
if v > 0:
return COL_AMBER_100, COL_AMBER_600, COL_AMBER_700, 1.8
return COL_WHITE, COL_SLATE_400, COL_SLATE_500, 1.3
_draw_dp_table(
ax_x, _x_text, _x_style,
"x(i,j) — yol-sayma DP · k eşleşirse TOPLA (max DEĞİL)",
"pozitif sayılar taban x(0,0)=1'den doğar (Solomon 1:33:02)", COL_AMBER_700)
_bx, _by = 0 * 1.0, (n - 1) * 1.0
ax_x.add_patch(FancyBboxPatch(
(_bx + 0.03, _by + 0.03), 0.94, 0.94, boxstyle="square,pad=0.0",
fc="none", ec=COL_ACCENT, linewidth=3.0, zorder=5))
fig.text(0.74, 0.495, "iki ardışık DP — her biri O(n²)",
ha="center", va="center", fontsize=9.5, color=COL_TEXT,
style="italic", weight="bold")
fig.suptitle("Princess Plum (PS8 P4) — max-mushroom DP → yol-sayma DP",
color=COL_TEXT, fontsize=14, weight="bold", y=0.975)
plt.show()
```
## Ne Öğrendik? {#sec-ne-ogrendik-d25}
::: {.callout-important title="Altı Taşınabilir Araç"}
Bu oturum, DP problem oturumlarının ilkiydi ve SRTBOT çerçevesini dört somut problemde uyguladı:
1. **Durum izleme (Tim):** "kaç gün üst üste" gibi bir kısıtı, alt problem tanımına bir varsayım ("i'de izin var") gömerek izle.
2. **Edit distance:** suffix-çift DP; ekle/sil/eşle/takas durumları min ile; $O(n^2)$.
3. **Precomputation runtime'a girer:** satır karşılaştırması $O(k)$ → önce hash ($kn$), sonra DP ($n^2$) = $O(kn + n^2)$; "alt problem $\times$ iş" formülüne ön-işleme eklenir.
4. **Sıralama-temelli DP (blok):** kısıt bir sıralama doğuruyorsa, sırala → problem LIS'e iner.
5. **Yol sayma (Plum):** "kaç yol" sorulduğunda recurrence'da **max yerine toplama**; pozitiflik taban durumdan gelir.
6. **İki ardışık DP:** önce hedefi (max mushroom $k$) hesapla, sonra onu kullanan ikinci DP (yol sayısı).
:::
## Sonraki {#sec-sonraki-d25}
::: {.callout-warning title="Ders 26 (L17): Dinamik Programlama 3 — Demaine"}
Sırada **Ders 26 (L17): Dinamik Programlama 3** var — Erik Demaine ile, DP'yi **ağaç** ve daha karmaşık alt problemlere taşıyoruz. Bu oturumda gördüğümüz subproblem expansion ve durum izleme, ağaç alt problemlerinde ve pseudopolinom örneklerde derinleşir.
:::
