Algorithmen und Datenstrukturen · Middle · Frage 40 von 75
Welche zwei Eigenschaften machen ein Problem geeignet für dynamische Programmierung?
- 1Sortierte Eingabe und eine einzige eindeutige Antwort
- 2Überlappende Teilprobleme und optimale Teilstruktur
- 3Eine Graphstruktur mit positiven Kantengewichten
Antwort zeigen
Richtige Antwort: Überlappende Teilprobleme und optimale Teilstruktur
Erklärung
Überlappende Teilprobleme heißt, dieselben Teilergebnisse werden oft gebraucht, ihr Caching lohnt sich also. Optimale Teilstruktur heißt, die beste Antwort setzt sich aus besten Antworten der Teilprobleme zusammen.