Dynamische Programmierung des Lernens von PHP-Algorithmen

Dynamische Programmierung ist ein Weg und eine Methode zur Lösung von Optimierungsproblemen. Die optimale Lösung des Endproblems kann aus den optimalen Lösungen der vorherigen Teilprobleme abgeleitet werden.

Was den dynamischen Programmieralgorithmus betrifft, habe ich ihn nicht gründlich gelernt. Eine einfache Zusammenfassung meiner Lernerfahrung ist:

Dynamische Programmierideen beinhalten die Ideen der Rekursion und des Teilens und Eroberns , aber anders als bei „Divide and Conquer“ wird beim dynamischen Programmierlösen die optimale Lösung jedes Zweigs im Lösungsprozess über den Status aufgezeichnet, wodurch wiederholte Berechnungen vieler Zweige eingespart werden.

Die wichtigsten und schwierigsten zwei Schritte der dynamischen Programmierung bestehen darin, den Zustand zu finden, der das Unterproblem beschreibt, und die Ableitungsbeziehung zwischen den Zuständen.

Probleme, bei denen die dynamische Programmierung eher zum Einsatz kommt: Ermitteln der Maximal- und Minimalwerte, ob es realisierbare Lösungen gibt und wie viele realisierbare Lösungen vorhanden sind.

Versuchen wir zunächst die häufigste Frage: Finden Sie den Wert einer bestimmten Position in der Fibonacci-Folge (Studenten, die es nicht wissen, suchen sie bitte auf Baidu).
Anwenden der Divide-and-Conquer-Methode zum Lösen des Codes

Während des Divide-and-Conquer-Lösungsprozesses werden die Abbildungen 3 und 4 wiederholt 2 unten wurden zweimal wiederholt. Je größer der Indexwert, desto öfter wird er wiederholt.

ok, schauen wir uns an, wie dynamische Programmierung optimiert werden kann.

Wir definieren ein Array, um den Wert jeder Fibonacci-Position aufzuzeichnen. Dies entspricht der Definition eines Status für jede Position Summe der beiden vorherigen, was einer Zustandsübergangsgleichung entspricht.
Das Aufzeichnen des Status über ein Array ist hier eine Idee des Austauschs von Raum gegen Zeit. Tatsächlich ist es dem Cache-Design, das wir in der täglichen Entwicklung verwenden, sehr ähnlich.

Zusammenfassung Die Lösung der dynamischen Programmierung kann in 4 Schritte unterteilt werden:
1. Bestimmen Sie das zu lösende Teilproblem, dh die Definition des Zustands.
2. Listen Sie die Zustandsübergangsgleichung auf.
3. Initialisieren Sie den bekannten Zustandswert gemäß den gegebenen Bedingungen.
4. Lösen Sie die endgültige Problemlösung.

Lassen Sie uns ein interessanteres Problem lösen, das Treppensteigen:

Das Obige ist der Inhalt der dynamischen Programmierung des PHP-Algorithmuslernens. Bitte achten Sie auf weitere verwandte Themen Inhalt PHP chinesische Website (www.php.cn)!