Dynamische Programmierung

Question 1

Was ist das Prinzip der Dynamischen Programmierung?

Answer 1

• Es ist eine Methode zum Lösen von Optimierungsproblemen
• das Problem in kleinere Teilprobleme zerlegen und diese Teilprobleme systematisch lösen
• Die Lösungen der Teilprobleme werden dann in einer Tabelle gespeichert
• Diese werden dann später wiederverwendet um urspüngliches Problem zu lösen
• oft rekusriv

Question 2

wie funktioniert LCS?

Answer 2

1. Erstelle Tabelle mit leerer Menge und beiden Wörtern
2. Gehe spalten Weise voran
3. Stimmen die buchstaben überein, nehme die Zahl von Diagonal links oben und addiere 1
4. Stimmen sie nicht überein nehme das Maximum vom linken und oberen Nachbarn
5. Ist man fertig startet man wieder unten rechts
6. Stimmen die buchstaben überein markiere die Zelle und geh Diagonal links nach oben
7. Stimmen sie nicht überein gehe zum maximum vom linken oder oberen nachbarn
   * Sind beide gleich ist es egal zu welchem man geht
8. Kommt man bei 0 an ist man fertig und alle markierten Zellen ergeben die LCS
   * Laufzeit: O(n1 * n2), O(n^2) wenn beide gleich lang