🏴‍☠️ LEYLA'S CODE

🆚 DP vs. Greedy Algorithms:
Greedy: Wähle lokal optimale Lösung (oft falsch!)
• Beispiel: Münzwechsel mit [1, 5, 10, 25]
• Greedy: Nimm immer größte Münze → funktioniert hier!
• Aber mit [1, 3, 4]: 6¢ → Greedy: 4+1+1 (3 Münzen), DP: 3+3 (2 Münzen)

DP: Betrachte ALLE Möglichkeiten, wähle global optimal
• Immer korrekt, aber langsamer als Greedy
• Nutze DP wenn Greedy nicht garantiert optimal ist!

📊 Top-Down (Memoization) vs. Bottom-Up (Tabulation):

# TOP-DOWN (Memoization) - Rekursiv mit Cache
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
# Vorteile: Intuitiv, berechnet nur nötige Subprobleme
# Nachteile: Rekursions-Overhead, Stack Overflow bei großem n

# BOTTOM-UP (Tabulation) - Iterativ mit Array
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
# Vorteile: Kein Rekursions-Overhead, oft schneller
# Nachteile: Berechnet alle Subprobleme (auch unnötige)

# OPTIMIERT - O(1) Space!
def fib_optimized(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr
# Nur 2 Variablen statt Array! O(1) Space statt O(n)

🎒 Knapsack Problem (Klassisches DP):
Du hast einen Rucksack mit Kapazität W und n Items mit Gewicht & Wert:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                # Max von: Item nehmen vs. nicht nehmen
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w - weights[i-1]],  # Nehmen
                    dp[i-1][w]  # Nicht nehmen
                )
            else:
                dp[i][w] = dp[i-1][w]  # Zu schwer
    
    return dp[n][capacity]

# Real-World: Resource Allocation, Portfolio Optimization
# Zeit: O(n·W), Space: O(n·W) → kann auf O(W) reduziert werden!

🧬 Edit Distance (Levenshtein Distance):
Minimale Anzahl Operationen, um String A → B zu transformieren:

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i  # Lösche alle Zeichen
    for j in range(n + 1):
        dp[0][j] = j  # Füge alle Zeichen ein
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # Keine Operation
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Lösche
                    dp[i][j-1],    # Füge ein
                    dp[i-1][j-1]   # Ersetze
                )
    
    return dp[m][n]

# "KITTEN" → "SITTING" = 3 Operationen
# Real-World: Spell Checkers, DNA Sequencing, Git Diff

🏗️ Real-World DP Anwendungen:
1. Reinforcement Learning (Q-Learning):
  → AlphaGo, ChatGPT nutzen DP-Varianten
  → Bellman Equation ist DP-Formulierung!
2. Bioinformatik:
  → DNA-Sequenz-Alignment (BLAST-Algorithmus)
  → Protein-Folding Prediction
3. Finance:
  → Option Pricing (Black-Scholes nutzt DP)
  → Portfolio-Optimierung
4. Game AI:
  → Chess Engines (Minimax mit DP)
  → Speedrun Routing (Shortest Path DP)

🎯 DP Pattern Recognition:
Ein Problem ist DP-geeignet wenn:
1. Overlapping Subproblems: Teilprobleme wiederholen sich
2. Optimal Substructure: Optimal = Optimal(Sub1) + Optimal(Sub2)
3. Entscheidungen beeinflussen Zukunft: (nicht nur aktuellen Schritt)

Beispiele:
• ✅ Fibonacci, Knapsack, Edit Distance, Shortest Path
• ❌ Lineares Suchen, Hashing, Binary Search (keine Überlappung)

⚠️ Common DP Patterns:
1. Linear DP (1D): Fibonacci, Climbing Stairs
2. Grid DP (2D): Unique Paths, Coin Change
3. Interval DP: Longest Palindromic Substring
4. Tree DP: Binary Tree Maximum Path Sum
5. State Machine DP: Best Time to Buy/Sell Stock

💡 DP Optimization Tricks:
• Space Optimization: 2D → 1D wenn nur vorherige Zeile benötigt
  Beispiel: Knapsack O(n·W) → O(W) Space
• Rolling Array: Nutze nur aktuelle & vorherige Zeile
• Sparse Table: Für Range Queries (RMQ)
• Bitmask DP: Für Subset-Probleme (Traveling Salesman)

🎓 Pro-Tipp:
DP ist schwer zu erkennen, aber folge diesem Prozess:
1. Schreibe naive rekursive Lösung
2. Identifiziere sich wiederholende Aufrufe → Memoize!
3. Konvertiere zu Bottom-Up (optional, aber oft schneller)
4. Optimiere Space (optional, aber elegant)

LeetCode-Tipp: 80% der "Hard" Problems sind DP! Master DP = Master Interviews! 🏴‍☠️

🚀 Next Level: Nach diesem Level verstehst du:
• Reinforcement Learning (Q-Learning = DP!)
• Graph Shortest Path (Bellman-Ford = DP)
• String Matching (KMP-Algorithmus nutzt DP-Idee)
• Advanced Optimization (Linear Programming ist DP-verwandt)

DP ist nicht nur ein Algorithmus-Pattern - es ist ein fundamentales Prinzip in Computer Science, Machine Learning und Optimierung. Master DP und du denkst wie ein echter Algorithmus-Architekt! - Deine Leyla 🐀