Dinamik Programlama I: Temeller

package main

import "fmt"

var naiveCalls, memoCalls int

// fibNaive: O(2^n) — örtüşen alt problemler yüzünden felaket
func fibNaive(n int) int {
	naiveCalls++
	if n <= 1 {
		return n
	}
	return fibNaive(n-1) + fibNaive(n-2)
}

// fibMemo: O(n) — sonuçlar saklanır
func fibMemo(n int, memo map[int]int) int {
	memoCalls++
	if n <= 1 {
		return n
	}
	if v, ok := memo[n]; ok {
		return v // önbellekten oku: iş yok
	}
	result := fibMemo(n-1, memo) + fibMemo(n-2, memo)
	memo[n] = result
	return result
}

// fibMemoSlice: harita yerine dilim — daha hızlı
func fibMemoSlice(n int) int {
	memo := make([]int, n+1)
	for i := range memo {
		memo[i] = -1
	}

	var solve func(int) int
	solve = func(k int) int {
		if k <= 1 {
			return k
		}
		if memo[k] != -1 {
			return memo[k]
		}
		memo[k] = solve(k-1) + solve(k-2)
		return memo[k]
	}
	return solve(n)
}

func main() {
	fmt.Printf("%6s %14s %16s %14s %14s\n", "n", "sonuç", "naif çağrı", "memo çağrı", "oran")
	for _, n := range []int{5, 10, 20, 25, 30} {
		naiveCalls, memoCalls = 0, 0
		v1 := fibNaive(n)
		v2 := fibMemo(n, map[int]int{})
		fmt.Printf("%6d %14d %16d %14d %14.0f\n",
			n, v1, naiveCalls, memoCalls, float64(naiveCalls)/float64(memoCalls))
		_ = v2
	}

	fmt.Println()
	fmt.Println("memoization ile büyük değerler anında hesaplanır:")
	for _, n := range []int{50, 80, 90} {
		fmt.Printf("  F(%d) = %d\n", n, fibMemoSlice(n))
	}

	fmt.Println()
	fmt.Println("naif sürümde F(90) hesaplamak evrenin yaşından uzun sürerdi.")
}

package main

import "fmt"

// fibTable: klasik tabulation — O(n) zaman, O(n) bellek
func fibTable(n int) ([]int, int) {
	if n <= 1 {
		return []int{0, 1}[:n+1], n
	}
	dp := make([]int, n+1)
	dp[0], dp[1] = 0, 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp, dp[n]
}

// fibOptimized: alan optimizasyonu — O(1) bellek
// Yalnızca son iki değere ihtiyaç var, tüm tabloyu tutmaya gerek yok
func fibOptimized(n int) int {
	if n <= 1 {
		return n
	}
	prev2, prev1 := 0, 1
	for range n - 1 {
		prev2, prev1 = prev1, prev1+prev2
	}
	return prev1
}

func main() {
	table, result := fibTable(10)
	fmt.Println("DP tablosu:", table)
	fmt.Println("F(10) =", result)

	fmt.Println()
	fmt.Printf("%6s %12s %12s %8s\n", "n", "tablolu", "optimize", "aynı")
	for _, n := range []int{0, 1, 5, 10, 30, 50, 80} {
		_, a := fibTable(n)
		b := fibOptimized(n)
		fmt.Printf("%6d %12d %12d %8t\n", n, a, b, a == b)
	}

	fmt.Println()
	fmt.Println("Bellek kullanımı:")
	fmt.Println("  tablolu:  O(n) — n=1.000.000 için 8 MB")
	fmt.Println("  optimize: O(1) — her n için 16 bayt")
}

package main

import (
	"fmt"
	"slices"
)

// climbStairs: 1 veya 2 adımla — Fibonacci ile aynı bağıntı
func climbStairs(n int) int {
	if n <= 1 {
		return 1
	}
	prev2, prev1 := 1, 1
	for range n - 1 {
		prev2, prev1 = prev1, prev1+prev2
	}
	return prev1
}

// climbStairsSteps: izin verilen adım kümesi genelleştirildi
func climbStairsSteps(n int, steps []int) ([]int, int) {
	dp := make([]int, n+1)
	dp[0] = 1 // temel durum: hiç adım atmamak bir yoldur

	for i := 1; i <= n; i++ {
		for _, s := range steps {
			if i-s >= 0 {
				dp[i] += dp[i-s]
			}
		}
	}
	return dp, dp[n]
}

// minCostClimb: her basamağın bir maliyeti var, en az maliyetle çık
func minCostClimb(cost []int) ([]int, int) {
	n := len(cost)
	if n == 0 {
		return nil, 0
	}
	dp := make([]int, n+1)
	// dp[i] = i. basamağa ulaşmanın en az maliyeti
	for i := 2; i <= n; i++ {
		dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
	}
	return dp, dp[n]
}

// waysWithPath: yolları da göster (küçük n için)
func waysWithPath(n int, steps []int) [][]int {
	var paths [][]int
	var walk func(remaining int, path []int)
	walk = func(remaining int, path []int) {
		if remaining == 0 {
			paths = append(paths, slices.Clone(path))
			return
		}
		for _, s := range steps {
			if s <= remaining {
				walk(remaining-s, append(path, s))
			}
		}
	}
	walk(n, nil)
	return paths
}

func main() {
	fmt.Println("1 veya 2 adımla merdiven çıkma:")
	for n := 0; n <= 8; n++ {
		fmt.Printf("  n=%d → %d yol\n", n, climbStairs(n))
	}
	fmt.Println("  (Fibonacci dizisiyle aynı!)")

	fmt.Println()
	dp, ways := climbStairsSteps(6, []int{1, 2, 3})
	fmt.Println("1, 2 veya 3 adımla n=6:")
	fmt.Println("  DP tablosu:", dp)
	fmt.Println("  toplam yol:", ways)

	fmt.Println()
	fmt.Println("n=4 için tüm yollar (adımlar 1,2):")
	for _, p := range waysWithPath(4, []int{1, 2}) {
		fmt.Println("  ", p)
	}

	fmt.Println()
	costs := []int{10, 15, 20, 5, 30, 8}
	costDP, minCost := minCostClimb(costs)
	fmt.Println("basamak maliyetleri:", costs)
	fmt.Println("maliyet DP tablosu:", costDP)
	fmt.Println("en az maliyet:", minCost)
}

package main

import (
	"fmt"
	"slices"
)

const inf = 1 << 30

// minCoins: en az para sayısı + kullanılan paralar
func minCoins(coins []int, amount int) ([]int, []int, bool) {
	dp := make([]int, amount+1)
	choice := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = inf
		choice[i] = -1
	}

	for i := 1; i <= amount; i++ {
		for _, c := range coins {
			if c <= i && dp[i-c] != inf && dp[i-c]+1 < dp[i] {
				dp[i] = dp[i-c] + 1
				choice[i] = c
			}
		}
	}

	if dp[amount] == inf {
		return dp, nil, false
	}

	// Seçimleri geriye doğru takip et
	var used []int
	for a := amount; a > 0; a -= choice[a] {
		used = append(used, choice[a])
	}
	slices.Sort(used)
	return dp, used, true
}

// countWays: kaç FARKLI şekilde ödenebilir (sıra önemsiz)
func countWays(coins []int, amount int) int {
	dp := make([]int, amount+1)
	dp[0] = 1

	// Dış döngü paralar: her para kombinasyonu bir kez sayılır
	for _, c := range coins {
		for i := c; i <= amount; i++ {
			dp[i] += dp[i-c]
		}
	}
	return dp[amount]
}

// countPermutations: sıra ÖNEMLİ olduğunda
func countPermutations(coins []int, amount int) int {
	dp := make([]int, amount+1)
	dp[0] = 1

	// Dış döngü tutar: her sıra ayrı sayılır
	for i := 1; i <= amount; i++ {
		for _, c := range coins {
			if c <= i {
				dp[i] += dp[i-c]
			}
		}
	}
	return dp[amount]
}

func main() {
	coins := []int{1, 3, 4}

	dp, used, ok := minCoins(coins, 6)
	fmt.Println("paralar:", coins, "tutar: 6")
	fmt.Println("DP tablosu:", dp[:7])
	fmt.Println("en az para:", len(used), "→", used, "(bulundu:", ok, ")")

	fmt.Println()
	fmt.Printf("%8s %14s %16s\n", "tutar", "en az para", "kullanılanlar")
	for amount := 1; amount <= 12; amount++ {
		_, u, ok := minCoins(coins, amount)
		if !ok {
			fmt.Printf("%8d %14s %16s\n", amount, "imkânsız", "-")
			continue
		}
		fmt.Printf("%8d %14d %16v\n", amount, len(u), u)
	}

	fmt.Println()
	fmt.Println("kaç farklı şekilde ödenebilir:")
	for amount := 1; amount <= 8; amount++ {
		fmt.Printf("  %d → kombinasyon: %-4d permütasyon: %d\n",
			amount, countWays(coins, amount), countPermutations(coins, amount))
	}

	fmt.Println()
	// Ödenemez tutar
	odd := []int{3, 5}
	_, _, ok2 := minCoins(odd, 7)
	fmt.Println("paralar", odd, "ile 7 ödenebilir mi:", ok2)
	_, u3, _ := minCoins(odd, 8)
	fmt.Println("paralar", odd, "ile 8:", u3)
}

package main

import "fmt"

// rob: klasik tabulation
func rob(houses []int) ([]int, int) {
	n := len(houses)
	if n == 0 {
		return nil, 0
	}
	dp := make([]int, n+1)
	dp[1] = houses[0]

	for i := 2; i <= n; i++ {
		dp[i] = max(dp[i-1], dp[i-2]+houses[i-1])
	}
	return dp, dp[n]
}

// robOptimized: O(1) bellek — yalnızca son iki değer gerekli
func robOptimized(houses []int) int {
	prev2, prev1 := 0, 0
	for _, money := range houses {
		prev2, prev1 = prev1, max(prev1, prev2+money)
	}
	return prev1
}

// robWithHouses: hangi evlerin soyulduğunu da döndürür
func robWithHouses(houses []int) (int, []int) {
	n := len(houses)
	if n == 0 {
		return 0, nil
	}
	dp := make([]int, n+1)
	dp[1] = houses[0]
	for i := 2; i <= n; i++ {
		dp[i] = max(dp[i-1], dp[i-2]+houses[i-1])
	}

	// Geriye doğru takip: hangi kararlar alındı?
	var chosen []int
	i := n
	for i > 0 {
		if i == 1 || dp[i] != dp[i-1] {
			chosen = append([]int{i - 1}, chosen...) // bu ev soyuldu
			i -= 2
			continue
		}
		i-- // bu ev soyulmadı
	}
	return dp[n], chosen
}

// robCircular: evler DAİRE şeklinde — ilk ve son ev komşu
func robCircular(houses []int) int {
	n := len(houses)
	switch n {
	case 0:
		return 0
	case 1:
		return houses[0]
	}
	// İki senaryo: ilk evi dâhil et (sonu hariç) veya son evi dâhil et (başı hariç)
	return max(robOptimized(houses[:n-1]), robOptimized(houses[1:]))
}

func main() {
	houses := []int{2, 7, 9, 3, 1}
	dp, best := rob(houses)

	fmt.Println("evler:", houses)
	fmt.Println("DP tablosu:", dp)
	fmt.Println("en fazla para:", best)

	total, chosen := robWithHouses(houses)
	fmt.Printf("soyulan evler (indeks): %v → toplam %d\n", chosen, total)

	fmt.Println()
	fmt.Printf("%-26s %10s %10s %8s\n", "evler", "doğrusal", "daire", "optimize")
	cases := [][]int{
		{2, 7, 9, 3, 1},
		{1, 2, 3, 1},
		{5, 5, 5, 5},
		{100},
		{50, 1, 1, 50},
		{},
	}
	for _, c := range cases {
		_, linear := rob(c)
		fmt.Printf("%-26v %10d %10d %8d\n", c, linear, robCircular(c), robOptimized(c))
	}

	fmt.Println()
	fmt.Println("Dikkat: [50,1,1,50] dairesel dizilimde ilk ve son ev komşu;")
	fmt.Println("bu yüzden ikisi birden alınamaz ve sonuç doğrusal hâlden düşük olur.")
}

package main

import "fmt"

// gridPaths2D: tam tablo — O(m×n) bellek
func gridPaths2D(rows, cols int) ([][]int, int) {
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
		dp[i][0] = 1 // ilk sütun: tek yol (hep aşağı)
	}
	for j := range dp[0] {
		dp[0][j] = 1 // ilk satır: tek yol (hep sağa)
	}

	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]
}

// gridPaths1D: tek satır yeterli — O(n) bellek
func gridPaths1D(rows, cols int) int {
	dp := make([]int, cols)
	for j := range dp {
		dp[j] = 1
	}
	for range rows - 1 {
		for j := 1; j < cols; j++ {
			dp[j] += dp[j-1] // dp[j] = üst, dp[j-1] = sol
		}
	}
	return dp[cols-1]
}

// gridPathsWithObstacles: engelli ızgara
func gridPathsWithObstacles(grid [][]int) int {
	if len(grid) == 0 || grid[0][0] == 1 {
		return 0
	}
	rows, cols := len(grid), len(grid[0])
	dp := make([]int, cols)
	dp[0] = 1

	for i := range rows {
		for j := range cols {
			if grid[i][j] == 1 {
				dp[j] = 0 // engel: buraya ulaşılamaz
				continue
			}
			if j > 0 {
				dp[j] += dp[j-1]
			}
		}
	}
	return dp[cols-1]
}

func main() {
	table, paths := gridPaths2D(3, 4)
	fmt.Println("3×4 ızgarada sol üstten sağ alta yol sayısı:")
	for _, row := range table {
		fmt.Println("  ", row)
	}
	fmt.Println("toplam yol:", paths)

	fmt.Println()
	fmt.Printf("%-14s %12s %12s %8s\n", "ızgara", "2D tablo", "1D tablo", "aynı")
	for _, dim := range [][2]int{{1, 1}, {2, 2}, {3, 4}, {5, 5}, {10, 10}} {
		_, a := gridPaths2D(dim[0], dim[1])
		b := gridPaths1D(dim[0], dim[1])
		fmt.Printf("%-14s %12d %12d %8t\n",
			fmt.Sprintf("%d×%d", dim[0], dim[1]), a, b, a == b)
	}

	fmt.Println()
	obstacles := [][]int{
		{0, 0, 0},
		{0, 1, 0},
		{0, 0, 0},
	}
	fmt.Println("engelli ızgara (1 = engel):")
	for _, row := range obstacles {
		fmt.Println("  ", row)
	}
	fmt.Println("yol sayısı:", gridPathsWithObstacles(obstacles))

	fmt.Println()
	fmt.Println("Bellek: 1000×1000 ızgara için")
	fmt.Println("  2D tablo: 1.000.000 hücre ≈ 8 MB")
	fmt.Println("  1D tablo: 1.000 hücre ≈ 8 KB")
}