logo

TechCodeview

Dynamische Programmierung oder DP

Dynamische Programmierung ist eine in der Mathematik und Informatik verwendete Methode zur Lösung komplexer Probleme durch Zerlegung in einfachere Teilprobleme. Indem jedes Teilproblem nur einmal gelöst und die Ergebnisse gespeichert werden, werden redundante Berechnungen vermieden, was zu effizienteren Lösungen für eine Vielzahl von Problemen führt. Dieser Artikel bietet eine detaillierte Untersuchung dynamischer Programmierkonzepte, veranschaulicht durch Beispiele.

partielle Ableitungen in Latex

Dynamische Programmierung

Inhaltsverzeichnis



Was ist dynamische Programmierung (DP)?

Dynamische Programmierung (DP) ist eine in der Mathematik und Informatik verwendete Methode zur Lösung komplexer Probleme durch Zerlegung in einfachere Teilprobleme. Indem jedes Teilproblem nur einmal gelöst und die Ergebnisse gespeichert werden, werden redundante Berechnungen vermieden, was zu effizienteren Lösungen für eine Vielzahl von Problemen führt.

Wie funktioniert dynamische Programmierung (DP)?

  • Teilprobleme identifizieren: Teilen Sie das Hauptproblem in kleinere, unabhängige Teilprobleme auf.
  • Store-Lösungen: Lösen Sie jedes Teilproblem und speichern Sie die Lösung in einer Tabelle oder einem Array.
  • Aufbaulösungen: Verwenden Sie die gespeicherten Lösungen, um die Lösung des Hauptproblems aufzubauen.
  • Redundanz vermeiden: Durch das Speichern von Lösungen stellt DP sicher, dass jedes Teilproblem nur einmal gelöst wird, wodurch die Rechenzeit verkürzt wird.

Beispiele für dynamische Programmierung (DP)

Beispiel 1: Betrachten Sie das Problem, die Fibonacci-Folge zu finden:

Fibonacci-Folge: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Brute-Force-Ansatz:

Um die n-te Fibonacci-Zahl mit einem Brute-Force-Ansatz zu finden, addieren Sie einfach die (n-1)th Und (n-2)th Fibonacci-Zahlen. Dies würde funktionieren, wäre aber für große Werte von ineffizient N , da hierfür alle vorherigen Fibonacci-Zahlen berechnet werden müssten.

Dynamischer Programmieransatz:

Fibonacci-Reihe mit dynamischer Programmierung

  • Teilprobleme: F(0), F(1), F(2), F(3), …
  • Store-Lösungen: Erstellen Sie eine Tabelle, um die berechneten Werte von F(n) zu speichern.
  • Aufbaulösungen: Suchen Sie für F(n) in der Tabelle nach F(n-1) und F(n-2) und fügen Sie sie hinzu.
  • Redundanz vermeiden: Die Tabelle stellt sicher, dass jedes Teilproblem (z. B. F(2)) nur einmal gelöst wird.

Durch die Verwendung von DP können wir die Fibonacci-Folge effizient berechnen, ohne Teilprobleme neu berechnen zu müssen.

Datenstrukturen Java

Beispiel 2: Längste gemeinsame Teilsequenz (Finden der längsten Teilsequenz, die zwei Zeichenfolgen gemeinsam ist)

Beispiel 3: Kürzester Pfad in einem Diagramm (Finden des kürzesten Pfades zwischen zwei Knoten in einem Diagramm)

Beispiel 4: Rucksackproblem (Ermitteln des maximalen Werts von Gegenständen, die in einen Rucksack mit einem bestimmten Fassungsvermögen gelegt werden können)

Wann sollte dynamische Programmierung (DP) verwendet werden?

Dynamische Programmierung ist eine Optimierungstechnik zur Lösung von Problemen, die aus den folgenden Merkmalen besteht:

1. Optimaler Unterbau:

Optimale Unterstruktur bedeutet, dass wir die optimalen Ergebnisse von Teilproblemen kombinieren, um das optimale Ergebnis des größeren Problems zu erzielen.

Bienenstockarchitektur

Beispiel:

Betrachten Sie das Problem, das zu finden minimale Kosten Pfad in einem gewichteten Diagramm von a Quelle Knoten zu a Ziel Knoten. Wir können dieses Problem in kleinere Teilprobleme zerlegen:

  • Finden Sie die Minimum kosten Weg von der Quelle Knoten zu jedem dazwischenliegend Knoten.
  • Finden Sie die Minimum kosten Pfad von jedem dazwischenliegend Knoten zum Ziel Knoten.

Die Lösung des größeren Problems (Finden des Pfads mit minimalen Kosten vom Quellknoten zum Zielknoten) kann aus den Lösungen dieser kleineren Teilprobleme konstruiert werden.

2. Überlappende Teilprobleme:

Dieselben Teilprobleme werden wiederholt in verschiedenen Teilen des Problems gelöst.

Beispiel:

Betrachten Sie das Problem der Berechnung des Fibonacci-Reihe . Um die Fibonacci-Zahl am Index zu berechnen N , müssen wir die Fibonacci-Zahlen bei Indizes berechnen n-1 Und n-2 . Dies bedeutet, dass das Teilproblem der Berechnung der Fibonacci-Zahl bei Index n-1 wird bei der Lösung des größeren Problems der Berechnung der Fibonacci-Zahl am Index zweimal verwendet N .

Ansätze der dynamischen Programmierung (DP)

Dynamische Programmierung kann mit zwei Ansätzen erreicht werden:

1. Top-Down-Ansatz (Memoisierung):

Beim Top-Down-Ansatz, auch bekannt als Auswendiglernen , beginnen wir mit der endgültigen Lösung und zerlegen sie rekursiv in kleinere Teilprobleme. Um redundante Berechnungen zu vermeiden, speichern wir die Ergebnisse gelöster Teilprobleme in einer Memoisierungstabelle.

Lassen Sie uns den Top-Down-Ansatz aufschlüsseln:

  • Beginnt mit der endgültigen Lösung und zerlegt sie rekursiv in kleinere Teilprobleme.
  • Speichert die Lösungen zu Teilproblemen in einer Tabelle, um redundante Berechnungen zu vermeiden.
  • Geeignet, wenn die Anzahl der Teilprobleme groß ist und viele davon wiederverwendet werden.

2. Bottom-Up-Ansatz (Tabellarische Darstellung):

Beim Bottom-up-Ansatz, auch bekannt als Tabellierung Wir beginnen mit den kleinsten Teilproblemen und bauen uns schrittweise bis zur endgültigen Lösung auf. Wir speichern die Ergebnisse gelöster Teilprobleme in einer Tabelle, um redundante Berechnungen zu vermeiden.

Lassen Sie uns den Bottom-up-Ansatz aufschlüsseln:

  • Beginnt mit den kleinsten Teilproblemen und steigert sich schrittweise zur endgültigen Lösung.
  • Füllt eine Tabelle von unten nach oben mit Lösungen für Teilprobleme.
  • Geeignet, wenn die Anzahl der Teilprobleme gering ist und die optimale Lösung direkt aus den Lösungen kleinerer Teilprobleme berechnet werden kann.

Dynamische Programmierung (DP) Algorithmus

Dynamische Programmierung ist eine algorithmische Technik, die komplexe Probleme löst, indem sie sie in kleinere Teilprobleme zerlegt und ihre Lösungen für die zukünftige Verwendung speichert. Es ist besonders wirksam bei Problemen, die darin bestehen überlappende Teilprobleme Und Optimaler Unterbau.

Gängige Algorithmen, die dynamische Programmierung verwenden:

  • Längste gemeinsame Teilsequenz (LCS): Findet die längste gemeinsame Teilsequenz zwischen zwei Zeichenfolgen.
  • Kürzester Pfad in einem Diagramm: Findet den kürzesten Pfad zwischen zwei Knoten in einem Diagramm.
  • Rucksackproblem: Bestimmt den maximalen Wert der Gegenstände, die in einem Rucksack mit einem bestimmten Fassungsvermögen untergebracht werden können.
  • Matrixkettenmultiplikation: Optimiert die Reihenfolge der Matrixmultiplikation, um die Anzahl der Operationen zu minimieren.
  • Fibonacci-Folge: Berechnet die n-te Fibonacci-Zahl.

Vorteile der dynamischen Programmierung (DP)

Dynamische Programmierung bietet zahlreiche Vorteile, darunter:

  • Vermeidet die mehrfache Neuberechnung derselben Teilprobleme, was zu erheblichen Zeiteinsparungen führt.
  • Stellt sicher, dass durch Berücksichtigung aller möglichen Kombinationen die optimale Lösung gefunden wird.
  • Zerlegt komplexe Probleme in kleinere, besser beherrschbare Teilprobleme.

Anwendungen der dynamischen Programmierung (DP)

Dynamische Programmierung hat ein breites Anwendungsspektrum, darunter:

JFX-Java-Tutorial
  • Optimierung: Rucksackproblem, Problem des kürzesten Pfades, Problem des maximalen Subarrays
  • Informatik: Längste gemeinsame Teilsequenz, Bearbeitungsabstand, String-Übereinstimmung
  • Unternehmensforschung: Bestandsverwaltung, Terminplanung, Ressourcenzuweisung

Lassen Sie uns nun eine umfassende Roadmap zur Beherrschung der dynamischen Programmierung erkunden.

Lernen Sie die Grundlagen der dynamischen Programmierung (DP)

Fortgeschrittene Konzepte der dynamischen Programmierung (DP)

  • Bitmaskierung und dynamische Programmierung | Set 1
  • Bitmaskierung und dynamische Programmierung | Satz 2 (TSP)
  • Ziffer DP | Einführung
  • Summe über Teilmengen | Dynamische Programmierung

Dynamische Programmierung (DP) Probleme

Wir haben Standardprobleme der dynamischen Programmierung (DP) in drei Kategorien eingeteilt: einfach, mittel und schwer.

1. Einfache Probleme der dynamischen Programmierung (DP)

  • Fibonacci-Zahlen
  • n-te katalanische Zahl
  • Glockenzahlen (Anzahl der Möglichkeiten, einen Satz zu unterteilen)
  • Binomialkoeffizient
  • Problem beim Münzwechsel
  • Teilmengensummenproblem
  • Berechnen Sie nCr % p
  • Eine Rute schneiden
  • Algorithmus zum Malen von Zäunen
  • Längste gemeinsame Folge
  • Längste ansteigende Folge
  • Längste Teilfolge, bei der der Unterschied zwischen benachbarten Folgen eins beträgt
  • Quadratische Submatrix maximaler Größe mit allen Einsen
  • Min. Kostenpfad
  • Mindestanzahl an Sprüngen, um das Ende zu erreichen
  • Längster gemeinsamer Teilstring (platzoptimierte DP-Lösung)
  • Zählen Sie die Wege, um mit Schritt 1, 2 oder 3 die n-te Treppe zu erreichen
  • Zählen Sie alle möglichen Pfade von links oben nach rechts unten in einer mXn-Matrix
  • Einzigartige Wege in einem Raster mit Hindernissen

2. Mittlere Probleme bei der dynamischen Programmierung (DP)

  • Floyd Warshall-Algorithmus
  • Bellman-Ford-Algorithmus
  • 0-1 Rucksackproblem
  • Drucken von Artikeln im 0/1-Rucksack
  • Unbegrenzter Rucksack (Wiederholung von Gegenständen erlaubt)
  • Eier-Fall-Puzzle
  • Wortbruchproblem
  • Scheitelpunktabdeckungsproblem
  • Problem beim Stapeln von Kacheln
  • Problem beim Stapeln von Kartons
  • Partitionsproblem
  • Problem des Handlungsreisenden | Set 1 (Naive und dynamische Programmierung)
  • Längste palindromische Folge
  • Längste gemeinsame ansteigende Teilsequenz (LCS + LIS)
  • Finden Sie alle unterschiedlichen Teilmengen- (oder Teilsequenz-)Summen eines Arrays
  • Gewichtete Jobplanung
  • Count Derangements (Permutation, sodass kein Element an seiner ursprünglichen Position erscheint)
  • Minimale Einfügungen, um ein Palindrom zu bilden
  • Wildcard-Mustervergleich
  • Möglichkeiten, Bälle so anzuordnen, dass benachbarte Bälle unterschiedlicher Art sind

3. Schwierige Probleme bei der dynamischen Programmierung (DP)

  • Palindrom-Partitionierung
  • Problem mit dem Zeilenumbruch
  • Das Partitionsproblem des Malers
  • Programm für Bridge- und Torch-Problem
  • Matrixkettenmultiplikation
  • Drucken von Klammern im Matrixkettenmultiplikationsproblem
  • Maximales Summenrechteck in einer 2D-Matrix
  • Maximaler Gewinn durch Kauf und Verkauf einer Aktie höchstens k-mal
  • Minimale Kosten zum Sortieren von Zeichenfolgen mithilfe von Umkehroperationen unterschiedlicher Kosten
  • Anzahl der AP-Teilsequenzen (Arithmetische Progression) in einem Array
  • Einführung in die dynamische Programmierung auf Bäumen
  • Maximale Höhe des Baums, wenn jeder Knoten als Wurzel betrachtet werden kann
  • Längster sich wiederholender und nicht überlappender Teilstring

Quicklinks:

  • Lernen Sie Datenstruktur und Algorithmen | DSA-Tutorial
  • Die 20 wichtigsten Interviewfragen zur dynamischen Programmierung
  • „Übungsaufgaben“ zur dynamischen Programmierung
  • „Quiz“ zur dynamischen Programmierung