Looking for algorithm Keywords? Try Ask4Keywords

algorithmDynamische Programmierung


Einführung

Dynamics-Programmierung ist ein weit verbreitetes Konzept und wird häufig zur Optimierung verwendet. Es bezieht sich auf die Vereinfachung eines komplizierten Problems, indem es rekursiv in einfachere Unterprobleme zerlegt wird, in der Regel einen Bottom-Up-Ansatz. Es gibt zwei Hauptattribute, die ein Problem aufweisen muss, damit die dynamische Programmierung anwendbar ist "Optimale Unterstruktur" und "Überlappende Unterprobleme". Zur Optimierung der Dynamics-Programmierung wird ein Konzept namens "Memorization" verwendet

Bemerkungen

Dynamic Programming ist eine Verbesserung von Brute Force. In diesem Beispiel erfahren Sie, wie Sie eine Dynamic Programming-Lösung von Brute Force erhalten.

Eine dynamische Programmierlösung hat zwei Hauptanforderungen:

  1. Überlappende Probleme

  2. Optimale Unterkonstruktion

Überlappende Teilprobleme bedeuten, dass Ergebnisse kleinerer Versionen des Problems mehrfach wiederverwendet werden, um zur Lösung des ursprünglichen Problems zu gelangen

Optimale Unterstruktur bedeutet, dass es eine Methode gibt, um ein Problem aus seinen Unterproblemen zu berechnen.

Eine dynamische Programmierlösung besteht aus zwei Hauptkomponenten, dem Zustand und dem Übergang

Der Staat verweist auf ein Teilproblem des ursprünglichen Problems.

Der Übergang ist die Methode, um ein Problem basierend auf seinen Unterproblemen zu lösen

Die Zeit, die eine Dynamic Programming Solution benötigt, kann als No. of States * Transition Time berechnet werden. Wenn also eine Lösung N^2 -Zustände hat und der Übergang O(N) , würde die Lösung ungefähr O(N^3) Zeit O(N^3) .

Dynamische Programmierung Verwandte Beispiele