Ein einfaches Beispiel für jemanden, der die dynamische Programmierung verstehen möchte [geschlossen]

96

Ich suche ein überschaubares Beispiel für jemanden, der Dynamisches Programmieren lernen möchte. Hier gibt es nette Antworten darauf, was dynamische Programmierung ist . Die Fibonacci-Sequenz ist ein gutes Beispiel, aber zu klein, um die Oberfläche zu zerkratzen. Es sieht nach einem großartigen Thema aus, über das ich lernen kann, obwohl ich die Algorithmenklasse noch nicht besucht habe. Hoffentlich steht es für den Frühling auf meiner Liste.

algorithm dynamic-programming AraK
quelle

Antworten:

30

Schauen Sie sich diese Seite an: Probleme mit der dynamischen Programmierpraxis

Nick Dandoulakis
quelle
1
Wenn Sie diesen Vortrag von MIT video.mit.edu/watch/… sehen und dann die oben genannten Probleme lösen, können Sie besser verstehen, warum DP hilfreich ist.
2286,
In diesem Fall ist der Youtube-Link im Kommentar bereits defekt. Neuer Link: youtube.com/watch?v=OQ5jsbhAv_M
AJP
Schauen Sie sich diese Videos an, von denen ich fand, dass sie sowohl den Top-Down- als auch den Bottom-Up-Aspekt der Algorithmen ziemlich intuitiv
abdecken
Es sieht so aus, als hätte MIT den Inhalt von der Hauptseite auf die MIT OpenCourseWare-Seite verschoben, sodass der angegebene Link @ pg2286 ungültig ist. Der Link ist jetzt 19. Dynamische Programmierung I Die vollständige Wiedergabeliste Einführung in Algorithmen ist ebenfalls verfügbar
rite2hhh
7

Die Idee hinter der dynamischen Programmierung ist, dass Sie Lösungen für Teilprobleme zwischenspeichern (auswendig lernen), obwohl ich denke, dass mehr dahinter steckt.

Es gibt viele Probleme mit Google Code Jam, sodass Lösungen eine dynamische Programmierung erfordern, um effizient zu sein. Beispiele:

Willkommen bei Code Jam (moderat)

Einen Booleschen Baum betrügen (moderat)

PermRLE (schwer)

Beachten Sie, dass jeder der Code Jam-Übungswettbewerbe einen Abschnitt "Wettbewerbsanalyse" enthält, wenn Sie beim Versuch, das Problem zu lösen, ratlos sind.

Joey Adams
quelle
Danke für die Ressourcen. Ich löse von Zeit zu Zeit ein oder zwei Fragen von Project Euler, und es scheint, dass ich wirklich an einigen Problemen festhalte, die Kenntnisse über DP erfordern.
AraK
5
  1. Geeks für Geeks hat eine große Sammlung dynamischer Programmierprobleme. Ich denke, dieses Set ist eines der besten, wenn Sie sich auf ein Interview vorbereiten.
  2. Wenn Sie kleine Tutorial-Videos zu DP-Problemen wünschen, können Sie dieses Problem vom MIT überprüfen .
Diptendu
quelle
4

Die Berechnung der Levenshtein-Entfernungen war eines der ersten Probleme, die ich mit der dynamischen Programmierung gelöst habe. Ich denke, es ist ein anständiger nächster Schritt von der Fibonacci-Sequenz in Bezug auf die Komplexität.

http://en.wikipedia.org/wiki/Levenshtein_distance

David Winslow
quelle