© TippaPatt/Shutterstock.com
Dynamisches Programmieren (DP) ist ein anspruchsvolles Gebiet der Computerprogrammierung mit spezifischen Fähigkeiten und Techniken zur Lösung von Problemen. Ja, Sie kommen als Softwareentwickler auch ohne aus, aber die dynamische Programmierung hat wichtige Anwendungen in der realen Welt, und Sie werden möglicherweise bei einem Entwicklerinterview dazu befragt.
Wenn Sie neu in der dynamischen Programmierung sind Programmieren oder Ihre Fähigkeiten auffrischen möchten, erklärt dieser kurze Artikel, was dynamisches Programmieren ist, mit Beispielen und wo Sie Ihre DV-Fähigkeiten online aufbauen können.
Was ist dynamisches Programmieren?
In der Computerprogrammierung ist dynamisches Programmieren (DP) eine Problemlösungsmethode, die komplizierte Probleme strukturiert und vereinfacht, indem sie sie in eine Kaskade sich überschneidender Teilprobleme zerlegt. Durch die Anwendung von DP können mehrere Klassen von Problemen effizient gelöst werden.
DP hat ihren Ursprung in der Mathematik und ist in verschiedenen Bereichen von Bioinformatik über Wasserressourcentechnik bis hin zu Wirtschaftswissenschaften anwendbar.
Wie funktioniert Dynamische Programmierung in der Informatik?
Dynamische Programmierung muss angemessen angewendet werden, um in der Computerprogrammierung verwendet zu werden. Ein Problem muss zwei Eigenschaften aufweisen, um für DP geeignet zu sein:
Eine optimale Unterstruktur: Ein spezifiziertes Problem hat die Eigenschaft einer optimalen Unterstruktur, wenn seine optimale Lösung aus optimalen Lösungen seiner Unterprobleme abgeleitet werden kann. Überlappende Teilprobleme: Das betreffende Problem sollte in eine Kaskade wiederverwendbarer Teilprobleme oder einen rekursiven Algorithmus zerlegt werden können, der wiederholt Teilprobleme lösen kann, ohne neue zu erzeugen.
Diese beiden Eigenschaften sind der Schlüssel zur Verwendung von DP. Wenn die optimale Lösung unter Verwendung von Teilproblemen gefunden wird, die sich nicht überschneiden, kann DP nicht verwendet werden. Stattdessen wird teile und herrsche verwendet. Ähnliche Sortieralgorithmen wie Merge Sort und Quick Sort sind keine DP.
Rekursion und dynamische Programmierung
Rekursion ist ein Schlüssel Eigenschaft der optimalen Substrukturen, die in DP verwendet werden. Rekursion ist einfach ein Prozess, der sich wiederholt, wie wenn Sie zwischen zwei Spiegeln stehen und Ihre Reflexion immer und immer wieder wiederholt wird (der Droste-Effekt).
Die optimalen Unterstrukturen haben Kaskaden von Problemen, die sich kontinuierlich selbst lösen, und das primäre Problem rekursiv.
Ein rekursiver Algorithmus in DP erzeugt keine neuen Unterprobleme und behält den Platzbedarf bei von den einzelnen sich überlagernden Teilproblemen klein in Anspruch genommen. Idealerweise sollten immer wieder dieselben Teilprobleme gelöst werden.
Schlüsselarten der dynamischen Programmierung?
Es gibt zwei Arten oder Methoden der DP, die davon abhängen, wie Sie ein Problem angehen. Beide Methoden verwenden Lösungen zum Merken, Speichern und Tabellieren, sodass sie schnell abgerufen werden können, wodurch die Zeit für die Wiederholung der Berechnung gespart wird.
Top-down
Beim Top-down-Ansatz ist die Lösung eines Problems rekursiv, was das Merken von Lösungen für sich überschneidende Teilprobleme ermöglicht. Nachfolgende neue Unterprobleme werden gelöst, indem auf den gespeicherten Datencache Bezug genommen wird, um zu sehen, ob bereits eine Lösung vorhanden ist. Wenn das Teilproblem vorher nicht gelöst wurde, werden es und seine Lösung dem Memoisierungs-Cache hinzugefügt.
Top-down-DP ist einfach zu verstehen und anzuwenden, da es die gezielte Lösung von Teilproblemen erleichtert. Sie können es leicht debuggen, aber dieser Rekursionsansatz kann viel Cache-Speicher verbrauchen, was zu Stapelüberlauffehlern führen kann.
Bottom-up
Der Bottom-up-Ansatz, auch bekannt als Tabellierung oder Tabellenfüllung, verwendet die Tabellierung, um eine Aufzeichnung gespeicherter Teilprobleme und Lösungen zu erstellen. Es verwendet dann die tabellierten gelösten Teilprobleme für eine Bottom-up-Umformulierung des Problems. Kleinere Teilprobleme werden gelöst, wobei die Lösungen genutzt werden, um größere Teilprobleme zu lösen. Die For-Schleife kann verwendet werden, um die Teilprobleme zu durchlaufen.
Beispiel: Dynamisches Programmieren und die Fibonacci-Serie
Ein praktisches Beispiel für dynamische Programmierung in Aktion, die mit der Fibonacci-Serie arbeiten:
0, 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55…
Bei den Fibonacci-Zahlen (Fn) ist jede Zahl in der Folge die Summe der beiden vorherigen Zahlen. Wenn der Wert von „n“ in Fn zunimmt, nehmen Umfang und Komplexität der Berechnung dieser Zahlen zu.
DP kann zur Berechnung jeder Fibonacci-Zahl verwendet werden. Durch die Verwendung von DP müssen Sie keinen rekursiven Baum generieren oder Probleme immer wieder lösen. Verwenden Sie einfach zuvor berechnete Werte. So sieht der Code für eine Implementierung dieser Reihe mit der Top-Down-Methode aus:
Der Code zur Berechnung einer beliebigen Fibonacci-Zahl.
©”TNGD”.com
Warum ist dynamische Programmierung wichtig?
Dynamische Programmierung ist kein herausragender Teil der modernen Programmierlandschaft. Dies liegt daran, dass es normalerweise nicht direkt in der zeitgenössischen Entwicklung auf Produktionsebene verwendet wird.
Viele kompetente Ingenieure haben sich etabliert, ohne mehr als nur geringfügige Kenntnisse über DP zu haben, obwohl es Teil führender Programmiersprachen wie:
PythonJavaScriptRubyPHPPerlLua
Grundlegendes Wissen über DV ist für Ingenieure wertvoll, da es Entwicklern helfen kann, Softwareanwendungen zu erstellen, die besser strukturiert und effizienter sind.
Die moderne Shared-Service-Architektur besteht aus unabhängigen Anwendungen, die auf die Ressourcen (Speicher, Rechenleistung, Netzwerkkapazität, Kosten) eines gemeinsamen Pools zugreifen. Schlecht strukturierter Code mit geringer Aufmerksamkeit für die Problemlösung kann zu unnötigem Ressourcenverbrauch führen und die Leistung anderer Anwendungen beeinträchtigen. DP hilft bei der Verfeinerung des Softwarecodes, um dies zu verhindern.
Reale Beispiele für dynamische Programmierung
Es gibt viele Beispiele für reale Softwareanwendungen, die DP verwenden, um agil und effizient zu bleiben und die Systemanforderungen für ihre Ausführung zu minimieren. Hier sind einige Beispiele:
Google Maps: In Google Maps wird DP verwendet, um den kürzesten Weg zwischen einem einzelnen Startpunkt und einer Vielzahl von Zielen zu identifizieren. Suchmaschinen: Um den Grad der Ähnlichkeit zwischen zwei Online-Inhalten zu berechnen.Plagiatssoftware: Entwicklung eines Dokumentabstandsalgorithmus zur Unterstützung der Erkennung des Ähnlichkeitsgrads zwischen Textdokumenten.Netzwerk: Übertragung von Daten von einer einzigen Quelle nacheinander an mehrere verschiedene Empfänger.Rechtschreibprüfung: Der Bearbeitungsabstandsalgorithmus, der verwendet wird, um zu quantifizieren, wie unterschiedlich zwei sind Wörter sind und berechnen Sie die Anzahl der Operationen, die erforderlich sind, um ein Wort in ein anderes umzuwandeln.
Datenbanken/Wissensbasis-Cache: Speicherung allgemeiner Abfragen/Anfragen in zugänglichen lokalen Speichern oder Caches. DP hilft, das wiederholte Abrufen häufig verwendeter Daten von Servern zugunsten einer lokalen Speicherung zu verhindern.
Beispielfragen für Vorstellungsgespräche zur dynamischen Programmierung
Wenn Sie auf der Suche nach Ihrem nächsten Job als Softwareentwickler oder-entwickler sind, werden Ihnen Kenntnisse über DV bei Vorstellungsgesprächen einen Vorteil verschaffen.
DP ist eine große Sache in Tech-Interviews. Führende Technologieunternehmen wie Google und Amazon fordern Kandidaten routinemäßig mit DV-Fragen heraus, die vor Ort ausgearbeitet werden müssen! Dies soll testen, wie Entwickler denken, und ob sie Aufgaben aufschlüsseln und die ressourceneffizientesten Wege finden, um Probleme zu lösen.
Hier sind einige Beispiele für Fragen und Antworten in Vorstellungsgesprächen zur dynamischen Programmierung
Neben der oben gezeigten Fibonacci-Gleichung sind hier einige gängige Fragen zur dynamischen Programmierung mit Beispielantworten und Lösungen:
Frage 1: Können Sie die Vor-und Nachteile der Memoisierung erläutern?
(Hinweis: Dies ist eine Frage zu den Vor-und Nachteilen des Top-Down-Ansatzes in der DP)
Antwort:
Zu den Vorteilen der Memoisierung gehören:
Die Codierung ist einfachEin Problem kann angegangen werden, indem ein Wrapper oder eine Anmerkung geschrieben wird, die automatisch die rekursive Funktion ausführt Antworten können aus einem Cache bezogen und für mehrere Probleme verwendet werden
Der Hauptnachteil der Memoisierung besteht darin, dass Sie eine große oder tiefe Zahl haben von Berechnungen kann Ihnen schnell der Stack-Platz ausgehen.
Frage 2: Sie klettern auf st Lüfte. Sie können entweder eine oder zwei Stufen gleichzeitig erklimmen. Wie viele verschiedene Möglichkeiten gibt es, nach oben zu klettern?
(Tipp: Diese Frage ist als das „Treppensteigen“-Problem bekannt)
Antwort: Sehen Sie sich die Herangehensweise an diese häufige Interviewfrage zum Programmieren in diesem Video:
Wo kann ich dynamische Programmierung üben?
Der Aufbau von Fähigkeiten in der dynamischen Programmierung stärkt die Denkfähigkeit und Problemlösung von Entwicklern. DP kann Ihnen auch helfen, ganzheitlicher über Probleme nachzudenken und ungewöhnliche, aber effektive Lösungen zu entwickeln. Wenn es für Sie an der Zeit ist, eine Schulung oder Zertifizierung in DP zu erhalten, finden Sie hier 3 der besten Online-Kurse:
Sobald Sie auf dem neuesten Stand sind, macht Übung den Meister!
Runden nach oben
Dynamische Programmierung ist vielleicht nicht Teil Ihres Entwickler-Stacks, aber es ist wichtig für die Unternehmen, für die Sie arbeiten möchten. Das Verstehen und Erlernen von DP verschafft Ihnen nicht nur Jobs, sondern verfeinert auch Ihre Fähigkeiten und hilft Ihnen, sauberen Code zu schreiben, den Ihr Hauptentwickler lieben wird!
Was ist dynamische Programmierung, mit Beispielen, häufig gestellte Fragen (FAQs)
Was ist Memoisierung?
In der Programmierung ist Memoisierung eine Optimierungstechnik, die die Ergebnisse ressourcenintensiver Funktionen in einem Cache speichert, damit sie aufgerufen werden können schnell auf, wenn sie wieder benötigt werden. Dies steigert die Geschwindigkeit und Effizienz von Computerprogrammen.
Was ist Tabellierung?
Tabulation ist ein anderer Begriff für den Bottom-up-Ansatz der dynamischen Programmierung. Eine Tabelle wird mit Lösungen aus den niedrigsten Teilproblemen gefüllt und verwendet, um die Antwort auf Teilprobleme auf höheren Ebenen zu berechnen, bis die ursprüngliche Lösung gefunden ist.
Was ist Teile und Herrsche?
Teile und Herrsche ist eine weitere Problemlösungstechnik. Es nimmt das ursprüngliche Problem und zerlegt es in kleinere, verwandte Teilprobleme, die unabhängig voneinander gelöst werden können.
Ist das Google-Coding-Interview schwer?
Ja. Dieses virtuelle Interview hat den Ruf, eines der härtesten Interviews im Tech-Bereich zu sein. Die Fragen erfordern umfangreiche Recherche und Übung und behandeln in der Regel Themen im Zusammenhang mit Google-Diensten. Oft werden DV-Fragen gestellt.
Befragt Amazon Bewerber für Vorstellungsgespräche im Bereich Software Engineering zu dynamischer Programmierung?
Ja. Amazon scheut sich nicht, Kandidaten fortgeschrittene Fragen zur dynamischen Programmierung zu stellen, um die Unvorbereiteten zu trennen.