Ich habe die Technik des dynamischen Programmierens mehrmals angewendet, aber heute fragte mich ein Freund, wie ich meine Unterprobleme definiere. Mir wurde klar, dass ich keine Möglichkeit hatte, eine objektive formale Antwort zu geben. Wie definieren Sie formal ein Unterproblem für ein Problem, das Sie mit dynamischer Programmierung lösen würden?
algorithms
dynamic-programming
jozefg
quelle
quelle
Antworten:
Das Prinzip der dynamischen Programmierung besteht darin, von oben nach unten (dh rekursiv) zu denken, aber von unten nach oben zu lösen. Eine gute Strategie zum Entwerfen eines DP besteht darin, das Problem rekursiv zu formulieren und auf diese Weise Unterprobleme zu generieren.
quelle
Wenn Sie wissen, dass Ihr Problem durch DP gelöst werden kann (dh, es weist eine optimale Unterstruktur und überlappende Unterprobleme auf), können Sie, wie @Suresh betonte, an eine Teilung denken und eine rekursive Lösung erobern.
Wenn Sie also über eine Lösung zum Teilen und Überwinden nachdenken, erhalten Sie einen Einblick, was für ein Unterproblem für Ihr spezielles Problem sein kann.
quelle
Meine Erfahrung besteht darin, einen Weg zu finden, um "redundante Aufzählungen mithilfe der Speicherung von bereits aufgelisteten nützlichen Werten zu reduzieren". Übrigens, Dynamic Programming ist bei ICPC (International Collegiate Programming Contest) sehr beliebt. Jeder kann nach dem Üben verschiedener ICPC-Probleme ein eigenes Gefühl für DP entwickeln.
quelle