Dinamik Programlama II: Klasik Problemler

package main

import (
	"fmt"
	"strings"
)

// lcs: uzunluk + tablo + alt dizinin kendisi
func lcs(a, b string) (int, string, [][]int) {
	ra, rb := []rune(a), []rune(b)
	m, n := len(ra), len(rb)

	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if ra[i-1] == rb[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}

	// Geri oluşturma: tablodan sağ alttan sol üste yürü
	var sb []rune
	i, j := m, n
	for i > 0 && j > 0 {
		switch {
		case ra[i-1] == rb[j-1]:
			sb = append(sb, ra[i-1])
			i--
			j--
		case dp[i-1][j] >= dp[i][j-1]:
			i--
		default:
			j--
		}
	}
	// Ters çevir
	for l, r := 0, len(sb)-1; l < r; l, r = l+1, r-1 {
		sb[l], sb[r] = sb[r], sb[l]
	}
	return dp[m][n], string(sb), dp
}

// lcsOptimized: yalnızca uzunluk — O(min(m,n)) bellek
func lcsOptimized(a, b string) int {
	ra, rb := []rune(a), []rune(b)
	if len(ra) < len(rb) {
		ra, rb = rb, ra // kısa olanı sütun yap
	}
	prev := make([]int, len(rb)+1)
	cur := make([]int, len(rb)+1)

	for i := 1; i <= len(ra); i++ {
		for j := 1; j <= len(rb); j++ {
			if ra[i-1] == rb[j-1] {
				cur[j] = prev[j-1] + 1
			} else {
				cur[j] = max(prev[j], cur[j-1])
			}
		}
		prev, cur = cur, prev
	}
	return prev[len(rb)]
}

func printTable(a, b string, dp [][]int) {
	ra, rb := []rune(a), []rune(b)
	fmt.Print("      ''")
	for _, r := range rb {
		fmt.Printf("%4c", r)
	}
	fmt.Println()
	for i := range dp {
		if i == 0 {
			fmt.Print("  '' ")
		} else {
			fmt.Printf("  %2c ", ra[i-1])
		}
		for _, v := range dp[i] {
			fmt.Printf("%4d", v)
		}
		fmt.Println()
	}
}

func main() {
	a, b := "AGGTAB", "GXTXAYB"
	length, seq, dp := lcs(a, b)

	fmt.Printf("metinler: %q ve %q\n", a, b)
	printTable(a, b, dp)
	fmt.Println()
	fmt.Println("LCS uzunluğu:", length)
	fmt.Printf("LCS: %q\n", seq)
	fmt.Println("optimize sürüm aynı mı:", lcsOptimized(a, b) == length)

	fmt.Println()
	cases := [][2]string{
		{"merhaba", "marhaba"},
		{"abc", "abc"},
		{"abc", "xyz"},
		{"", "abc"},
		{"kitap", "kitaplık"},
		{"çilek", "çiçek"},
	}
	fmt.Printf("%-14s %-14s %8s %-12s\n", "metin 1", "metin 2", "uzunluk", "LCS")
	for _, c := range cases {
		l, s, _ := lcs(c[0], c[1])
		fmt.Printf("%-14q %-14q %8d %-12q\n", c[0], c[1], l, s)
	}

	// Benzerlik oranı: diff araçlarının kullandığı ölçüt
	fmt.Println()
	x, y := "dinamik programlama", "dinamik program"
	l, _, _ := lcs(x, y)
	maxLen := max(len([]rune(x)), len([]rune(y)))
	fmt.Printf("benzerlik: %q ↔ %q → %%%.1f\n", x, y, 100*float64(l)/float64(maxLen))
	fmt.Println("ortak kısım:", strings.Count(x, "")-1, "karakterden", l, "tanesi ortak")
}

package main

import "fmt"

type operation struct {
	kind     string
	from, to rune
	pos      int
}

// editDistance: mesafe + tablo + işlem listesi
func editDistance(a, b string) (int, []operation, [][]int) {
	ra, rb := []rune(a), []rune(b)
	m, n := len(ra), len(rb)

	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = i // ilk sütun: hepsini sil
	}
	for j := range dp[0] {
		dp[0][j] = j // ilk satır: hepsini ekle
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if ra[i-1] == rb[j-1] {
				dp[i][j] = dp[i-1][j-1]
				continue
			}
			dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
		}
	}

	// İşlemleri geri oluştur
	var ops []operation
	i, j := m, n
	for i > 0 || j > 0 {
		switch {
		case i > 0 && j > 0 && ra[i-1] == rb[j-1]:
			i--
			j--
		case i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1]+1:
			ops = append(ops, operation{"değiştir", ra[i-1], rb[j-1], i - 1})
			i--
			j--
		case j > 0 && (i == 0 || dp[i][j] == dp[i][j-1]+1):
			ops = append(ops, operation{"ekle", 0, rb[j-1], i})
			j--
		default:
			ops = append(ops, operation{"sil", ra[i-1], 0, i - 1})
			i--
		}
	}
	// Ters çevir
	for l, r := 0, len(ops)-1; l < r; l, r = l+1, r-1 {
		ops[l], ops[r] = ops[r], ops[l]
	}
	return dp[m][n], ops, dp
}

// editDistanceOptimized: O(n) bellek
func editDistanceOptimized(a, b string) int {
	ra, rb := []rune(a), []rune(b)
	prev := make([]int, len(rb)+1)
	for j := range prev {
		prev[j] = j
	}

	for i := 1; i <= len(ra); i++ {
		cur := make([]int, len(rb)+1)
		cur[0] = i
		for j := 1; j <= len(rb); j++ {
			if ra[i-1] == rb[j-1] {
				cur[j] = prev[j-1]
			} else {
				cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
			}
		}
		prev = cur
	}
	return prev[len(rb)]
}

func main() {
	a, b := "kitten", "sitting"
	dist, ops, dp := editDistance(a, b)

	fmt.Printf("%q → %q: %d işlem\n\n", a, b, dist)
	for _, op := range ops {
		switch op.kind {
		case "değiştir":
			fmt.Printf("  konum %d: %q → %q (değiştir)\n", op.pos, op.from, op.to)
		case "ekle":
			fmt.Printf("  konum %d: %q ekle\n", op.pos, op.to)
		case "sil":
			fmt.Printf("  konum %d: %q sil\n", op.pos, op.from)
		}
	}

	fmt.Println()
	fmt.Print("  ")
	fmt.Print("     ''")
	for _, r := range []rune(b) {
		fmt.Printf("%4c", r)
	}
	fmt.Println()
	for i := range dp {
		if i == 0 {
			fmt.Print("     '' ")
		} else {
			fmt.Printf("     %2c ", []rune(a)[i-1])
		}
		for _, v := range dp[i] {
			fmt.Printf("%4d", v)
		}
		fmt.Println()
	}

	fmt.Println()
	cases := [][2]string{
		{"merhaba", "merhba"},
		{"aynı", "aynı"},
		{"", "abc"},
		{"abc", ""},
		{"kitap", "kitaplık"},
		{"çiçek", "çilek"},
		{"istanbul", "İstanbul"},
	}
	fmt.Printf("%-14s %-14s %10s %8s\n", "metin 1", "metin 2", "mesafe", "optimize")
	for _, c := range cases {
		d, _, _ := editDistance(c[0], c[1])
		fmt.Printf("%-14q %-14q %10d %8d\n", c[0], c[1], d, editDistanceOptimized(c[0], c[1]))
	}

	fmt.Println()
	fmt.Println("Yazım denetimi: bir kelimeye en yakın sözlük kelimelerini bulur.")
	word := "progrmlama"
	dictionary := []string{"programlama", "program", "problem", "prova", "pragma"}
	fmt.Printf("girdi: %q\n", word)
	for _, d := range dictionary {
		dist, _, _ := editDistance(word, d)
		fmt.Printf("  %-14q mesafe: %d\n", d, dist)
	}
}

package main

import (
	"fmt"
	"slices"
)

type Item struct {
	Name   string
	Weight int
	Value  int
}

// knapsack: 2D tablo + seçilen eşyalar
func knapsack(items []Item, capacity int) (int, []Item, [][]int) {
	n := len(items)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}

	for i := 1; i <= n; i++ {
		for w := range capacity + 1 {
			dp[i][w] = dp[i-1][w] // almama
			if items[i-1].Weight <= w {
				withItem := dp[i-1][w-items[i-1].Weight] + items[i-1].Value
				dp[i][w] = max(dp[i][w], withItem)
			}
		}
	}

	// Geri oluşturma
	var chosen []Item
	w := capacity
	for i := n; i > 0; i-- {
		if dp[i][w] != dp[i-1][w] { // bu eşya alınmış
			chosen = append(chosen, items[i-1])
			w -= items[i-1].Weight
		}
	}
	slices.Reverse(chosen)
	return dp[n][capacity], chosen, dp
}

// knapsackOptimized: tek satır — O(capacity) bellek
func knapsackOptimized(items []Item, capacity int) int {
	dp := make([]int, capacity+1)
	for _, item := range items {
		// TERSTEN: her eşya en fazla bir kez kullanılsın
		for w := capacity; w >= item.Weight; w-- {
			dp[w] = max(dp[w], dp[w-item.Weight]+item.Value)
		}
	}
	return dp[capacity]
}

// unboundedKnapsack: her eşya SINIRSIZ kullanılabilir — ileri gezilir
func unboundedKnapsack(items []Item, capacity int) int {
	dp := make([]int, capacity+1)
	for _, item := range items {
		for w := item.Weight; w <= capacity; w++ { // İLERİ
			dp[w] = max(dp[w], dp[w-item.Weight]+item.Value)
		}
	}
	return dp[capacity]
}

func main() {
	items := []Item{
		{"altın külçe", 10, 60},
		{"gümüş takı", 20, 100},
		{"bronz heykel", 30, 120},
	}
	const capacity = 50

	value, chosen, dp := knapsack(items, capacity)

	fmt.Println("eşyalar:")
	for _, it := range items {
		fmt.Printf("  %-16s ağırlık=%-4d değer=%-4d oran=%.1f\n",
			it.Name, it.Weight, it.Value, float64(it.Value)/float64(it.Weight))
	}
	fmt.Println("kapasite:", capacity)

	fmt.Println()
	fmt.Println("en yüksek değer:", value)
	fmt.Println("seçilen eşyalar:")
	totalWeight := 0
	for _, it := range chosen {
		fmt.Printf("  %s (%d kg, %d değer)\n", it.Name, it.Weight, it.Value)
		totalWeight += it.Weight
	}
	fmt.Println("toplam ağırlık:", totalWeight, "/", capacity)

	// DP tablosunun bir kısmını göster
	fmt.Println()
	fmt.Println("DP tablosu (kapasite 0, 10, 20, 30, 40, 50):")
	fmt.Printf("%-18s", "eşya")
	for _, w := range []int{0, 10, 20, 30, 40, 50} {
		fmt.Printf("%6d", w)
	}
	fmt.Println()
	for i := range dp {
		label := "(hiçbiri)"
		if i > 0 {
			label = items[i-1].Name
		}
		fmt.Printf("%-18s", label)
		for _, w := range []int{0, 10, 20, 30, 40, 50} {
			fmt.Printf("%6d", dp[i][w])
		}
		fmt.Println()
	}

	fmt.Println()
	fmt.Println("optimize sürüm:", knapsackOptimized(items, capacity))
	fmt.Println("sınırsız sürüm:", unboundedKnapsack(items, capacity),
		"← aynı eşya tekrar alınabilir")

	fmt.Println()
	fmt.Println("Tek satırlık farka dikkat: döngü yönü")
	fmt.Println("  ters (w--): her eşya bir kez → 0/1 sırt çantası")
	fmt.Println("  ileri (w++): eşya tekrar tekrar → sınırsız sırt çantası")
}

package main

import (
	"fmt"
	"slices"
)

// lisDP: O(n²) — alt diziyi de verir
func lisDP(data []int) (int, []int) {
	n := len(data)
	if n == 0 {
		return 0, nil
	}
	dp := make([]int, n) // dp[i] = i ile BİTEN en uzun artan alt dizi
	prev := make([]int, n)
	for i := range dp {
		dp[i], prev[i] = 1, -1
	}

	bestLen, bestEnd := 1, 0
	for i := 1; i < n; i++ {
		for j := range i {
			if data[j] < data[i] && dp[j]+1 > dp[i] {
				dp[i], prev[i] = dp[j]+1, j
			}
		}
		if dp[i] > bestLen {
			bestLen, bestEnd = dp[i], i
		}
	}

	var seq []int
	for i := bestEnd; i != -1; i = prev[i] {
		seq = append(seq, data[i])
	}
	slices.Reverse(seq)
	return bestLen, seq
}

// lisBinary: O(n log n) — ikili arama ile
func lisBinary(data []int) (int, []int) {
	// tails[k] = uzunluğu k+1 olan artan alt dizilerin en küçük olası son elemanı
	var tails []int
	prev := make([]int, len(data))
	tailIdx := []int{} // tails'teki her konumun data içindeki indeksi

	for i, v := range data {
		pos, found := slices.BinarySearch(tails, v)
		if found {
			continue
		}
		prev[i] = -1
		if pos > 0 {
			prev[i] = tailIdx[pos-1]
		}
		if pos == len(tails) {
			tails = append(tails, v)
			tailIdx = append(tailIdx, i)
			continue
		}
		tails[pos] = v
		tailIdx[pos] = i
	}

	if len(tails) == 0 {
		return 0, nil
	}
	var seq []int
	for i := tailIdx[len(tailIdx)-1]; i != -1; i = prev[i] {
		seq = append(seq, data[i])
	}
	slices.Reverse(seq)
	return len(tails), seq
}

func main() {
	cases := [][]int{
		{10, 9, 2, 5, 3, 7, 101, 18},
		{1, 2, 3, 4, 5},
		{5, 4, 3, 2, 1},
		{2, 2, 2},
		{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5},
		{},
	}

	fmt.Printf("%-38s %8s %8s %8s\n", "dizi", "O(n²)", "O(nlogn)", "aynı")
	for _, c := range cases {
		a, _ := lisDP(c)
		b, _ := lisBinary(c)
		fmt.Printf("%-38v %8d %8d %8t\n", c, a, b, a == b)
	}

	fmt.Println()
	data := []int{10, 9, 2, 5, 3, 7, 101, 18}
	l1, s1 := lisDP(data)
	l2, s2 := lisBinary(data)
	fmt.Println("dizi:", data)
	fmt.Printf("O(n²) çözüm:    uzunluk=%d alt dizi=%v\n", l1, s1)
	fmt.Printf("O(n log n):     uzunluk=%d alt dizi=%v\n", l2, s2)
	fmt.Println("ikisi de geçerli artan alt dizi (farklı olabilirler)")

	fmt.Println()
	fmt.Println("Uygulama: en az kaç eleman silinerek dizi artan yapılır?")
	for _, c := range [][]int{{3, 1, 4, 1, 5}, {5, 4, 3}, {1, 2, 3}} {
		l, _ := lisBinary(c)
		fmt.Printf("  %v → %d eleman silinmeli\n", c, len(c)-l)
	}
}

package main

import "fmt"

// uniquePaths: sol üstten sağ alta kaç yol var (sağa ve aşağı hareket)
func uniquePaths(rows, cols int) ([][]int, int) {
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
		dp[i][0] = 1
	}
	for j := range dp[0] {
		dp[0][j] = 1
	}
	for i := 1; i < rows; i++ {
		for j := 1; j < cols; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp, dp[rows-1][cols-1]
}

// minPathSum: en az maliyetli yolu bul + yolu geri oluştur
func minPathSum(grid [][]int) (int, [][2]int) {
	rows, cols := len(grid), len(grid[0])
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}

	dp[0][0] = grid[0][0]
	for i := 1; i < rows; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for j := 1; j < cols; j++ {
		dp[0][j] = dp[0][j-1] + grid[0][j]
	}
	for i := 1; i < rows; i++ {
		for j := 1; j < cols; j++ {
			dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
		}
	}

	// Yolu geriye doğru kur
	var path [][2]int
	i, j := rows-1, cols-1
	for i > 0 || j > 0 {
		path = append(path, [2]int{i, j})
		switch {
		case i == 0:
			j--
		case j == 0:
			i--
		case dp[i-1][j] <= dp[i][j-1]:
			i--
		default:
			j--
		}
	}
	path = append(path, [2]int{0, 0})
	for l, r := 0, len(path)-1; l < r; l, r = l+1, r-1 {
		path[l], path[r] = path[r], path[l]
	}
	return dp[rows-1][cols-1], path
}

func main() {
	dp, paths := uniquePaths(3, 4)
	fmt.Println("3×4 ızgarada yol sayısı:", paths)
	for _, row := range dp {
		fmt.Println("  ", row)
	}

	fmt.Println()
	grid := [][]int{
		{1, 3, 1, 8},
		{1, 5, 1, 2},
		{4, 2, 1, 3},
	}
	fmt.Println("maliyet ızgarası:")
	for _, row := range grid {
		fmt.Println("  ", row)
	}

	cost, path := minPathSum(grid)
	fmt.Println("en az maliyet:", cost)
	fmt.Print("yol: ")
	for i, p := range path {
		if i > 0 {
			fmt.Print(" → ")
		}
		fmt.Printf("(%d,%d)", p[0], p[1])
	}
	fmt.Println()

	total := 0
	for _, p := range path {
		total += grid[p[0]][p[1]]
	}
	fmt.Println("yol üzerindeki değerler toplamı:", total, "| doğrulama:", total == cost)

	fmt.Println()
	fmt.Printf("%-12s %14s\n", "ızgara", "yol sayısı")
	for _, d := range [][2]int{{1, 1}, {2, 2}, {3, 3}, {5, 5}, {10, 10}} {
		_, p := uniquePaths(d[0], d[1])
		fmt.Printf("%-12s %14d\n", fmt.Sprintf("%d×%d", d[0], d[1]), p)
	}
}