Informatik: DYNAMISCHES PROGRAMMIEREN (Golang)

1. Einführung: Was also dynamische Programmierung ist, wird einfach gesagt, es ist eine Programmiermethodik, die sich darauf konzentriert, den Prompter in viele kleinere, aber ähnliche Unterprobleme zu zerlegen . Und dann durch eine clevere Optimierung, ermöglicht es Ihnen, diese Unterprobleme sehr schnell zu lösen, so dass Sie am Ende die endgültige Lösung haben, die Sie suchen. Darüber hinaus kann es Ihrem Code eine dramatische Verbesserung sowohl in Bezug auf Effizienz als auch Geschwindigkeit bieten. Und auch dieses Konzept zu verstehen und zu wissen, wie man es anwenden kann, um Probleme zu lösen , wird in technischen Interviews für Software-Engineering-Rollen äußerst vorteilhaft sein. Und ich arbeite momentan selbst als Software-Ingenieur. Und ich kann Ihnen aus Erfahrung sagen, dass sich in jedem einzelnen technischen Interview, das ich für die verschiedenen Unternehmen durchgemacht habe , in der Vergangenheit beworben haben. Irgendwann im Interview wurde ich gebeten, ein Problem zu lösen, indem ich Code auf ein White Board schrieb wo die Lösung dieses Problems die Verwendung von dynamischer Programmierung erforderte. Also, wenn Sie ein Interesse an offensichtlich Computerprogrammierung haben oder möglicherweise einen Informatik-Abschluss in der Hochschule oder vielleicht eine Software-Engineering-Rolle danach. Und das wäre ein großartiger Kurs für Sie weil ich Sie Schritt für Schritt begleiten werde. Ein paar Beispielprobleme, die Sie in einem Interview oder auf dem Job oder in der Schule begegnen können . Das erfordert natürlich eine dynamische Programmierung, um das Problem zu lösen. Und hier ist der erste Kurs von mir, auf den du gestoßen bist. Mein Name ist Scott Race. Wie gesagt, arbeite ich derzeit als Software-Ingenieur in der Finanzdienstleistungsbranche. Und ich habe einen Abschluss von UC Berkeley in Informatik und Wirtschaftswissenschaften. Also, wenn gesagt, lasst uns anfangen. 2. Was ist dynamische Programmierung?: Alles klar, willkommen zum ersten Video dieses Kurses über dynamische Programmierung. Und in diesem ersten schnellen Video hier, nur irgendwie gibt Ihnen eine kurze Einführung, offensichtlich in das, was dynamische Programmierung ist. Und so habe ich hier nur die grundlegende Definition von den Geeks für Geeks Website gezogen. Und so ist die Hauptidee hier, dass die dynamische Programmierung einfach eine Optimierung über einfache alte Rekursion ist . Und für den Fall, dass Sie es nicht wissen, ist die Rekursion nur das Konzept, dass eine Funktion sich immer und immer wieder aufruft , bis sie eine Art Basisfall trifft, an dem sie aufhört, sich selbst aufzurufen, und dann gibt es den Stapel zurück, bis er letztendlich beendet ist. Und so, wie ich schon sagte, ist die dynamische Programmierung einfach eine Optimierung darüber hinaus. Und die Grundidee ist, dass wir Ergebnisse von Unterproblemen speichern , damit wir sie später nicht neu berechnen müssen, wenn wir sie benötigen. Und was das im Grunde bedeutet, ist, wenn Sie ein Problem bekommen , das mit dynamischer Programmierung gelöst werden kann, können Sie dieses Problem immer annehmen und es in kleinere Unterprobleme und eine sehr ähnliche Natur aufteilen . Und anstatt zu versuchen, jedes dieser Unterprobleme unabhängig voneinander zu lösen , alle von selbst. Wir werden tatsächlich diese Lösungen einiger der Unterprobleme verwenden , um andere Unterprobleme sehr schnell zu lösen. Und so letztendlich ist die Art und Weise, wie das funktioniert, all diese verschiedenen Unterprobleme, und sie werden alle sehr ähnlich. Es wird aber eins geben, das ist das grundlegendste in der Natur, und wir nennen das den Basisfall. Und das Basis-Case-Unterproblem wird eine sehr einfache intuitive, logische Lösung haben. Aber das ist eine super einfache Lösung kann tatsächlich verwendet werden, um ein anderes Unterproblem sehr schnell zu lösen, das ein wenig komplexer sein könnte. Und jetzt kann die Lösung für dieses Subproblem dann verwendet werden, um ein anderes Unterproblem zu lösen, das noch komplexer sein könnte. Und es baut sich langsam von dort aus wie ein Schneeballeffekt auf. Und es klingt immer noch ein bisschen verwirrend oder abstrakt. Keine Sorge, Sie werden viele wirklich detaillierte Beispiele in diesem Kurs sehen , so dass am Ende, ein sehr festes Verständnis der dynamischen Programmierung offensichtlich, und dann, wie Sie es in Interviews und potenziell am Arbeitsplatz nutzen können. Und das letzte, was ich erwähnen möchte, bevor ich dieses Video einschließe, ist, weil dynamische Programmierung eine Optimierung über nur einfache alte Rekursion ist. Anwendungen können Sie keine massiven Leistungs- und Effizienzverbesserungen erkennen. Weißt du, zum Beispiel, wenn du hier unten schaust, kannst du diese kleinen Code-Snippets für das Fibonacci-Zahlenproblemsehen das Fibonacci-Zahlenproblem , das ich dich im nächsten Video durchführe. Es gibt zwei Möglichkeiten, dieses Problem zu lösen. einen beinhaltet Englisch nur die rekursive Methode des Klägers, und der andere Ansatz beinhaltet natürlich eine dynamische Programmierung. Und Sie können sehen, dass die Laufzeiteffizienz dieser beiden Probleme recht unterschiedlich ist. Mit nur einfacher alter Rekursion ist es eine exponentielle Laufzeit, während es bei der dynamischen Programmierung nur linear ist. Und so, um das in Perspektive zu bringen, wissen Sie, wenn Sie eine sehr große Eingabe in eine dieser Funktionen mit einer einfachen rekursiven Methode haben. Es kann Stunden oder sogar Tage dauern bis eine Funktion wie diese die Lösung berechnet, die Sie suchen. Während bei einem dynamischen Programmieransatz dieser riesige Input noch nur wenige Sekunden dauern konnte. Und das ist wirklich, wie unterschiedlich diese beiden Ansätze in Bezug auf die Effizienz sein können. Und das ist auch der Grund, warum nur zu wissen, wie man kodiert, oder? Ich weiß nur, wie man zum Beispiel diese kleinen Code-Snippets schreibt, damit sie technisch funktionieren. Es wird wahrscheinlich nicht ausreichen, um Ihnen einen guten Software-Engineering-Job zu besorgen, wenn Sie das wollen. Und das liegt daran, dass der Job eines Software-Ingenieurs natürlich darin besteht, Code zu schreiben, aber dies auf die effizienteste Art und Weise wie möglich zu tun. Und dieses Konzept gilt für alle Ingenieure, egal ob Sie Software-Ingenieur und Maschinenbauingenieur sind, Elektroingenieur spielt keine Rolle. Ihre einzige Aufgabe besteht darin, Probleme auf möglichst effiziente Weise zu lösen. Und wenn Sie dieses Konzept wirklich verstehen und beherrschen können und Sie verstehen, wie Sie es verwenden, um Probleme zu lösen , so dass die Laufzeit Ihrer Anwendungen oder Ihre Algorithmen in der Größenordnung von nur wenigen Sekunden im Gegensatz zu Sie wissen, Stunden oder Tage, je nachdem, was die Eingangsgrößen, das wird enorm vorteilhaft für Sie in Interviews und natürlich auf dem Job sein. Ich hoffe, das hat Ihnen eine ziemlich gute Einführung auf hohem Niveau und Verständnis dafür gegeben, was dynamische Programmierung ist. einem nächsten Video tauchen wir viel mehr in das Fibonacci-Zahlenbeispiel ein, damit Sie einechtes Lebens-Szenario und ein echtes Problem sehenkönnen echtes Lebens-Szenario und ein echtes Problem sehen , das Sie vielleicht in einem Interview lösen müssen. Und das soll eine leichter zu verständliche dynamische Programmierfrage sein. Und dann, wenn wir in diesem Kurs weiter kommen, werden die Beispiele, die ich Sie durchführe, immer schwieriger. So sehen wir uns den nächsten. 3. Fibonacci Nummern (einfach): Na gut, willkommen zurück. Und in diesem Video werden wir, wie gesagt, in das Fibonacci-Sequenz-Problem eintauchen , über das ich kurz gesprochen und dir im letzten Video gezeigt habe. Und wie Sie gesehen haben, gibt es zwei Hauptwege, dieses Problem anzugehen oder zu lösen. Die erste davon beinhaltet nur eine einfache alte Rekursion. Und diese Methode wird sehr langsam und träge und ineffizient sein. Und dann natürlich wird der dynamische Programmieransatz nur eine Optimierung darüber hinaus sein, das wird, wie Sie sehen werden, eine dramatische Verbesserung in Bezug auf Geschwindigkeit und Effizienz sein, eine dramatische Verbesserung in Bezug auf wenn Sie versuchen, dieses Problem. Und so ist der Code, den Sie hier betrachten nur drei einfache Funktionen, die in der Programmiersprache Go geschrieben sind. Und wenn du noch nie gesehen hättest, mach dir keine Sorgen, es ist eigentlich sehr einfach, nur irgendwie durchzulesen und zu verstehen, was los ist. Und syntaktisch gesehen ist es eigentlich ziemlich ähnlich wie Java und C und so etwas. Hoffentlich sollte es sehr einfach sein zu verstehen, was hier vor sich geht. Und ich werde Sie natürlich durch sie führen. Und so haben wir die Hauptfunktion, die nur der Einstiegspunkt unserer Anwendung sein wird . Und dann, wie du im letzten Video mit diesen zwei kleinen Code-Snippets gesehen hast, habe ich sie im Grunde neu geschrieben. Und das ist nur die Funktion, die diese Berechnungen nur mit dem einfachen alten rekursiven Ansatz ausführen wird . Deshalb wird es nur fib rekursiv genannt. Und dann heißt die zweite Funktion hier unten Fib Dp. Und das ist der dynamische Programmieransatz, der dieses Problem lösen wird. Bevor ich hineinkomme, nur für den Fall, dass Sie tatsächlich nicht mit Fibonacci-Nummern vertraut sind und wie das alles funktioniert. Es ist einfach eine Folge von Zahlen, die bei eins beginnt und bis ins Unendliche weitergeht. Und die grundlegende Struktur dieser Folge von Zahlen ist im Grunde jede Zahl ist die Summe der vorherigen zwei Zahlen. Also zum Beispiel, wenn wir uns die Nummer zwei hier ansehen, und ich sollte auch erwähnen, dass die Sequenz selbst einfach immer mit 11 beginnt. Und von da an ist jede Zahl die Summe der vorherigen zwei Zahlen. Wenn man sich diese zweistellige Stelle genau hier ansieht, ist dies natürlich die Summe von 11, die vorherigen zwei Ziffern, dann geht es zu drei. Diese Ziffer ist die Summe von 21. Und dann fünf natürlich, ist die Summe von 32 und so weiter und so weiter. Und das war's wirklich. Das ist das gesamte Konzept der Fibonacci-Nummern. Und das Problem, das wir lösen wollen, ist, dass wir eine Funktion schreiben wollen die die n-te Ziffer in der Fibonacci-Sequenz berechnet. Also zum Beispiel, wenn ich die fünfte Ziffer in den Fibonacci-Zahlen berechnen wollte, wäre das die Zahl fünf, richtig? 12345. Dies ist die fünfte Ziffer und es ist nur zufällig auch die Nummer fünf. Und so konzentrieren wir uns jetzt nur auf die reguläre fib rekursive Funktion. Die Funktion, die nur diese Berechnungen mit Planum-Rekursion durchführen wird, Keine dynamische Programmierung beteiligt. Und ich führe Sie durch, um Ihnen zu zeigen warum dieser Ansatz eigentlich sehr ineffizient ist. Und lassen Sie mich diesen Code zuerst durch ein Beispiel erklären. Also lasst uns so tun, als suche ich nach der fünften Ziffer, jetzt nach den Fibonacci-Zahlen. Und wenn diese Funktion von der Hauptfunktion aufgerufen wird, werden wir die Zahl 52 Argumente hier übergeben. Das n ist also nur die n-te Ziffer, nach der wir suchen. Und das wird anfangs auf fünf gesetzt. Und dann haben wir getroffen, wir haben diese if-Aussage natürlich getroffen, was, wie ich im letzten Video erwähnt habe, das ist unser Basis-Fall, und ich werde mehr davon in einer Minute hier erklären. Aber nur wenn man sich die if-Anweisung anschaut, ist offensichtlich fünf nicht kleiner oder gleich eins. Also überspringen wir das vorerst und kommen zu unserem Rückgabevermerk. Hier werden die Dinge interessant, weil sich diese Funktion jetzt noch zwei Mal rekursiv aufrufen wird. Einmal mit dem Streit von vier, richtig? Und minus eins ist vier. Und das zweite Mal mit einem Wert von drei und minus zwei. Und das sollte sinnvoll sein, denn um die fünfte Ziffer der Fibonacci-Sequenz zu berechnen, müssen wir zuerst die vierten, dritten Ziffern berechnen, damit wir sie tatsächlich zusammenfügen können, was uns zu die fünfte Ziffer. Und so konzentrieren Sie sich auf diesen ersten Funktionsaufruf genau hier mit dem Wert von vier, richtig? Diese Funktion wird sich selbst aufrufen und ist jetzt vier. Wir haben den Basis-Fall wieder getroffen. Offensichtlich spielt es keine Rolle, weil vier nicht kleiner oder gleich eins ist. Also, Boom, wir sind gleich wieder hier runter zum Rückgabe-Statement. Und wieder einmal wird sich diese Funktion jetzt zwei weitere Male rekursiv mit einem Wert von 32 aufrufen , was wiederum Sinn machen sollte, richtig, um die vierte Ziffer, die Fibonacci-Zahlen, zu berechnen , haben wir zuerst berechnen Sie die dritte, zweite Ziffer und fügen Sie sie zusammen. Und dieser Prozess wird sich immer und immer wieder wiederholen bis irgendwann der Basisfall tatsächlich wahr ist, oder? Irgendwann wird N kleiner oder gleich eins sein. In diesem Fall geben wir einfach zurück, was n ist und wir machen keine rekursiven Aufrufe. Okay, das ist nur die grundlegendste Form des Problems, das wir lösen wollen. Deshalb nennt man es den Basisfall. So zum Beispiel, wissen Sie, wenn n gleich eins ist, das entspricht nur der ersten Ziffer der Fibonacci-Zahlen, die wir gerade wissen, ist gleich eins. Und wenn n 0 ist, ergibt das keinen Sinn , weil nichts vor der ersten Ziffer kommt, also geben wir in diesem Fall einfach 0 zurück, richtig? Lassen Sie mich Ihnen das jetzt visuell zeigen. Und hier werden Sie tatsächlich sehen können, warum dieser Ansatz so ineffizient ist. Dies ist also nur eine kleine Baumstruktur, die Ihnen alle verschiedenen rekursiven Funktionsaufrufe zeigt , die gemacht werden. Und Sie können in Klammern die Argumente sehen, die übergeben werden. Also beginnen wir natürlich ganz oben mit unserem ersten Argument von fünf, oder? In der.m versuchen wir, diese fünfte Ziffer der Fibonacci-Zahlen zu berechnen. Dieser Funktionsaufruf ruft sich zwei weitere Male mit den Argumenten 43 auf. Und jeder dieser rekursiven Aufrufe ruft die gleiche Funktion noch zwei Mal mit unterschiedlichen Argumenten auf. In diesem Fall sind es 32. Und dann geht es von dort weiter und nennt sich exponentiell immer öfter bis man natürlich zu den Basisfällen kommt, die hier unten sind, richtig? Wenn wir die Funktion mit den Werten von eins oder 0 aufrufen, wie Sie hier in der if-Anweisung sehen können, kehren wir einfach zurück und dieser Punkt, was n ist. Hier hört die Rekursion auf. Und dann kehren wir den Baum zurück, um letztendlich zu berechnen, was die endgültige Lösung sein sollte, die fünfte Ziffer. Aber wenn Sie genauer hinschauen, werden Sie sehen, dass wir die gleiche Funktion mit den gleichen Argumenten mehrmals aufrufen. zum Beispiel diesen Funktionsaufruf hier mit dem Wert von zwei betrachten, nennen wir ihn hier, und dann rufen wir ihn wieder hier auf, und dann rufen wir ihn wieder hier auf, richtig? Also berechnen wir redundant das gleiche genaue Ding dreimal, wenn es in Wirklichkeit nur einmal berechnet werden sollte. Wir müssen immer nur die zweite Ziffer der Fibonacci-Zahlen genau einmal berechnen , damit wir sie verwenden können, um dann die dritte Ziffer zu berechnen. Und Sie werden sehen, was tatsächlich die dritte Ziffer zweimal berechnet, richtig? Mehr Redundanz. Und wir berechnen tatsächlich die erste Ziffer, 12345 mal. Und im Basisfall werden wir uns entziehen. Die Eingabe ist 0, das ist hier und hier und hier. Also Punkt ist, wir machen eine Menge redundanter Berechnungen, die, wissen Sie, wenn Sie sich vorstellen können, ob die Eingabe nicht nur fünf war, sondern sagen wir 100. Sie könnten sich vorstellen, wie massiv dieser Baum wir eine all die redundanten Berechnungen bekommen , die beteiligt wären , die nur CPU verschwenden, Zeit verschwenden. Wenn man in Wirklichkeit, wie ich schon sagte, jede Zahl in der Sequenz genau einmal berechnen muss. Und dort wird der dynamische Programmieransatz ins Spiel kommen , denn das ist es, was es uns erlauben wird. Berechnen Sie jede Zahl nur einmal und dann keine redundante Berechnung mehr nach der Tatsache. Aber lassen Sie mich Ihnen zuerst zeigen, wie ineffizient dieser Code tatsächlich ist. Also bin ich bereits voran gegangen und kompiliere diesen Code hier. Und gerade jetzt ist die Hauptmethode nur so eingestellt, dass das Ergebnis dieser einfachen fib rekursiven Methode gerade jetzt aufgerufen und ausgedruckt wird. Also gehe ich hier rüber zu meinem Terminal. Und so werde ich meinen Code ausführen. diesem kleinen Strich n Argument kann ich angeben , welche n-te Ziffer ich die Anwendung ausgeben möchte. Also einfach mit unserem Beispiel hier möchte ich herausfinden, was die fünfte Ziffer ist. Also gehe ich weiter und drücke die Eingabetaste und dann boom, sehr schnell. Die Antwort ist natürlich fünf. Also lasst uns etwas etwas schwieriger machen oder Bedingungen der Verarbeitung und so weiter, das wird die zehnte Ziffer tun. Das wird wieder 55 sein, sehr schnell. Aber sobald Sie anfangen, eine größere Eingabegröße zu bekommen, oder? Wie gesagt, vielleicht 100 oder so. Nun, wenn ich die 100. Ziffer in den Fibonacci-Zahlen berechnen möchte, drücke ich Enter. Und da gehst du. Es wird immer noch verarbeitet. Wird immer noch verarbeitet. Noch keine Antwort. Und ich habe ehrlich gesagt keine Ahnung, wie lange das dauern könnte. Es kann zehn Minuten dauern, es kann drei Stunden dauern. Ich habe ehrlich gesagt keine Ahnung. Ich werde nicht hier sitzen und warten, bis das beendet ist, aber da ich immer noch spreche, ist es immer noch nicht fertig. Also hoffe ich, das hat Ihnen bewiesen, dass die 100. Ziffer wirklich nicht so groß ist wie eine Eingabe. Und doch dauert es immer noch lange dieser spezielle einfache rekursive Ansatz die Ergebnisse tatsächlich berechnet. Also werde ich einfach voran gehen und kontrollieren, es zu sehen. Wenn Sie nun in den dynamischen Programmierungsteil gehen, wird dies Ihnen erlauben, die Effizienz dieser Art von Berechnung massiv zu beschleunigen. Und das ist, wo ich die Idee oder das Konzept der Unterprobleme, über die ich im letzten Video gesprochen habe, binden möchte. Schreiben Sie jedes dieser Unterprobleme, die wir zu lösen versuchen , und verwenden Sie dann die Lösungen von, werden die Berechnung von Ziffern in der Fibonacci-Sequenz, die vor dem Digital kommen, nach dem wir eigentlich suchen. also wieder mit unserem Beispiel gehen, kümmern wir uns wirklich, wirklich um die fünfte Ziffer. Das ist unser Hauptproblem. Aber die kleineren Unterprobleme berechnen die vierte Ziffer und dann die dritte Ziffer, die zweite Ziffer, die erste Ziffer. Und so gehst du hin. Wir haben im Grunde vier andere kleinere Unterprobleme , die wir berechnen und herausfinden müssen, dass die Antworten zuerst sind, so dass wir schließlich zu dem wirklichen Problem kommen können, das wir herausfinden wollen, was die fünfte Ziffer ist, richtig? Und natürlich wollen wir Lösungen für all diese Teilprobleme finden indem wir ihre Lösungen nur genau einmal berechnen. Und so werden wir das tun, ist, dass wir unten rechts beginnen und die erste Ziffer der Fibonacci-Sequenz berechnen, die im Grunde gegeben ist. Und wir werden im Wesentlichen das Ergebnis dieser Berechnung speichern , so dass wir es schnell verwenden können , um dann herauszufinden, was die zweite Ziffer ist, speichern Sie das Ergebnis davon. Und dann können wir das schnell nutzen. Antwort, um die dritte Ziffer als die vierte und dann schließlich die fünfte zu lösen. Und so werden wir immer nur die Lösungen für jedes dieser kleineren Teilprobleme genau einmal berechnen . Und so lassen Sie mich jetzt auf den Code hier zurückkommen. Und so werde ich Sie hier durch diese FIB DP-Methode führen, die natürlich der dynamische Programmieransatz ist, um dieses Problem zu lösen. Und es wird tatsächlich in Bezug auf seine Struktur der fib-rekursiven Methode sehr ähnlich sein. Außer es wird einen subtilen Unterschied geben, jetzt haben wir dieses Array-Argument und das wird als unsere Speicherkomponente fungieren. Deshalb nannte ich es kurz „Männer“. Dies wird die Lösungen dieser kleineren Teilprobleme enthalten, die wir dem Weg zu unserer endgültigen Antwort der fünften Ziffer berechnen. Und so wird das funktionieren, zum Beispiel, wenn wir die Antwort für die dritte Ziffer in den Fibonacci-Zahlen berechnen . Die Antwort für dieses Unterproblem wird im dritten Index gespeichert, dem dritten Punkt in diesem Array. Und dann auch mit der vierten Ziffer in den Fibonacci-Zahlen , werden diese Antworten im vierten Index gespeichert und so weiter und so weiter. Und das erlaubt uns, später wieder zu kommen, das Array c zu betrachten, wenn es bereits eine Zahl oder bereits eine Ziffer gibt, die vorher berechnet wurde. Und wenn ja, können wir diese Nummer einfach nehmen und sie verwenden, anstatt nach unten gehen und mehr Rekursion durchführen und dieselbe Nummer mehr als einmal neu berechnen zu müssen. Also haben wir hier immer noch den gleichen Basisfall, obwohl ich es ein bisschen anders geschrieben habe, ich bin mir nicht sicher, warum. Also, wenn N irgendwann auf eins oder 0 runterkommt, wir einfach den Wert dessen zurück, was N ist, oder? Wenn n 0 ist, geben wir einfach 0 zurück. Wenn n gleich eins ist und wir geben nur eins zurück. Also der gleiche Basis-Fall. Also haben wir im Grunde nur diese eine zusätzliche kleine if-Anweisung hinzugefügt , die im Grunde sagt, du weißt schon, wir werden in unser Array gehen und wir werden überprüfen , ob die Antwort für die n-te Ziffer bereits berechnet, bevor. Und wenn ja, wenn ja, dann holen wir es einfach aus dem Array und geben es zurück. Und genau als Nebennotiz, dieses Array, wenn es zum ersten Mal in diese Funktion übergeben wird, werden alle Indizes auf 0 initialisiert. Also 0 ist im Grunde die Art und Weise, wie wir identifizieren ob es tatsächlich eine Berechnung in der Vergangenheit gemacht hat oder nicht. Also, wenn es 0 ist, dann müssen wir offensichtlich nach unten gehen und die Rekursion machen und herausfinden, was die Antwort für diese n-te Ziffer ist. Aber wenn es nicht gleich 0 ist, dann gehst du. Wir haben eine Lösung für eines der Teilprobleme gefunden, das in der Vergangenheit bereits berechnet wurde. So können wir es einfach greifen und es zurückgeben und einfach den rekursiven Unsinn überspringen, der völlig nicht benötigt wird. Und natürlich, wenn keine dieser if-Aussagen trifft, dann müssen wir hier tatsächlich gehen und die n-te Ziffer der Fibonacci-Sequenz berechnen . Und wenn diese Rekursion zurückkehrt und wir endlich die Antwort bekommen, speichern wir sie in diesem Array, so dass irgendwo weiter unten auf der Straße, wenn wir jemals zu dem Punkt kommen, wo wir versuchen, die gleiche Ziffer zu berechnen. Nochmal, es gibt keine Notwendigkeit. Wir haben es bereits im Array gespeichert. Wir können es einfach rausholen und zurückgeben. Zurück hierher zu kommen, ist es irgendwie visuell zu sehen. wir also zum ersten Mal die zweite Ziffer in der Fibonacci-Serie berechnen Wennwir also zum ersten Mal die zweite Ziffer in der Fibonacci-Serie berechnen, müssen wir sie tatsächlich berechnen. Also machen wir diese Rekursion. Wir rufen die gleiche Funktion erneut mit den Werten von 10. Und das sind nur Basisfallszenario. So. Wenn diese Funktionen jedoch zurückkehren, würden wir unsere Antwort erhalten und dann speichern wir den Wert der zweiten Ziffer in unserem Array. So dass das nächste Mal später die Straße hinunter, wenn wir zu dem Punkt kommen, wo wir die zweite Ziffer berechnen müssen, wieder, gibt es keine Notwendigkeit. An diesem Punkt schauen wir in unser Array und wir sehen, oh, wir haben bereits die zweite Ziffer vorher berechnet. Ich hole das einfach raus und bringe es zurück. Und dann eliminiert das die Notwendigkeit, mehr Rekursion und entfernt vollständig alle redundanten Berechnungen, die Sie in diesem Baum sehen. Also komm ich jetzt zurück zum Code, werde ich hier ein paar Verbesserungen vornehmen. Ich werde mich nicht auskommentieren. Der Funktionsaufruf ist nur unsere normale fib rekursive Methode. Und dann entkommentieren Sie die dynamische Programmierung, die Fib DP Funktion, richtig? Und Speicher hier, hier initialisieren wir unser kleines Speicher-Array und dann übergeben wir es in unseren FIB-DP-Funktionsaufruf und drucken dann die Ergebnisaufstände aus und sie gehen voran und speichern diesen Code. Ich komme zurück und kompiliere es neu. Okay, also lass mich jetzt voran gehen und diesen Code mit den gleichen Argumenten ausführen , die ich vorher nicht nur mit dem normalen rekursiven Ansatz getan habe. Also noch einmal, die fünfte Ziffer der Fibonacci-Zahlen zu berechnen und gehen Sie vor und drücken Sie die Eingabetaste. Und wieder bekommen wir fünf wie erwartet. Dann gehen sie weiter und machen die zehnte Ziffer, Cat5 wieder wie erwartet. Und jetzt, wenn ich die 100. Ziffer mache, wie Sie sich vorher erinnern, mit nur dem normalen rekursiven Ansatz, ist es nie fertig? Jetzt drücke ich Enter, Boom, augenblicklich. Es ist ziemlich massive Zahl und es war in der Lage, dies in einem Bruchteil einer Sekunde noch zu berechnen. Genau dort hoffe ich, dass dieser Beweis für Sie ist, wie drastisch einer Leistungsverbesserung Sie aus der Optimierung Ihres Codes herauskommen können, sei es durch dynamische Programmierung oder etwas anderes. Aber Punkt ist, dynamische Programmierung ist wirklich eine signifikante Optimierung über nur eine einfache rekursive Methode und kann buchstäblich Ihren Code in nur einem Bruchteil einer Sekunde laufen lassen, im Gegensatz zu Minuten, Stunden, oder sogar Tage, je nachdem, was das Eingabeargument Größe, richtig? Also hoffe ich, dieses Beispiel, und es gibt irgendwie einen Sinn für Sie. Ich weiß, dass dieses dynamische Programmierkonzept ein wenig schwer zu verstehen sein kann, zunächst zu verstehen, ich weiß, dass ich sicherlich mit ihm in der Schule zu kämpfen, als ich es lernte. Also empfehle ich, als Funktionen für sich selbst zu schreiben und wirklich zu versuchen, darüber nachzudenken, wie diese Funktionen funktionieren. Vielleicht setzen Sie tatsächlich einige Haltepunkte und treten Sie durch den Code, um zu sehen, wie die Dinge Schritt für Schritt ausgeführt werden, so dass Sie ein sehr gutes Verständnis davon haben , was hinter den Kulissen vor sich geht. Wenn Sie schwierigere Probleme zu lösen haben, können Sie immer noch irgendwie das Problem navigieren und herausfinden, was die Unterprobleme sind und wie Sie einen rekursiven Ansatz entwickeln, der die Antworten auf diese Sub- Probleme auf dem Weg, so dass Sie die Leistung Ihrer Anwendung oder Ihres Algorithmus drastisch beschleunigen können. Also, wenn das gesagt wird, dass wir dieses Video einpacken und im nächsten kommt, werden wir in ein bisschen schwierigeres Problem tauchen. Ich hatte dies als eher ein Problem mit mittlerer Schwierigkeit bezeichnet , auf das Sie in einem Interview oder so stoßen könnten. Und es ist kann sich um die Suche nach all den verschiedenen einzigartigen Pfaden von irgendeinem Anfang spielt bis zu einem Ziel auf Schachbrett oder Schachbrett der Art drehen , bestimmte Barrieren auf dem Weg gibt. So ziemlich interessantes Problem. Und natürlich wird es ein großartiger Kandidat für einen dynamischen Programmieransatz sein. Also danke fürs Ansehen, und ich werde in der nächsten sehen. 4. Einzigartige Pfade (Mittel): Na gut, willkommen zurück. Und in diesem Video werde ich Sie durch ein anderes Problem , das in der Natur ein wenig schwieriger wird, nur in Bezug auf den Versuch, wirklich zu verstehen und zu denken, Ihren Weg durch eine mögliche Lösung für das Problem. Aber Sie werden später sehen, dass die eigentliche Lösung selbst Codierung der Lösung sehr ähnlich sein wird , die Sie für das Fibonacci-Problem gesehen haben , das im vorherigen Video. Also taucht man einfach hier rein. Das Problem, das wir in diesem Fall lösen wollen, wird eine Art Schachbrett oder Schachbrett bekommen, richtig? Und ich habe hier ein kleines Diagramm gezeigt, das ich dich in einer Minute durchführe. Also angesichts einer Art von Board wie diesem, wollen wir die Anzahl der einzigartigen Pfade von tau finden, s, Das ist unsere Startfliese, um es zu kacheln, E, das ist unsere Endkachel. Da Sie sich nur nach unten oder nach rechts bewegen können. Und dann sind Kacheln, die mit einem X markiert sind, grundsätzlich Barrieren und man kann diese nicht überqueren Also kommen zu unserem kleinen Beispiel hier, und das ist die eigentliche Board eingerichtet, die versuchen wird , für in diesem, in diesem Video zu lösen. So können Sie hier sehen, das ist unsere Startfliese und das ist unsere N Kachel. Und natürlich sind diese kleinen Xs die Barrieren. Und so versuchen wir wieder, alle möglichen Pfade zu finden, zumindest die Anzahl der eindeutigen Pfade von S, zwei 0s. Als Beispiel könnte ein Pfad von S sein und wir gehen runter, runter, runter, runter, runter und dann ganz nach rechts. Und denken Sie daran, dass wir nur nach unten oder nach rechts gehen können, also ist das ein Weg. Ein weiterer einzigartiger Pfad könnte unten sein und dann den ganzen Weg nach rechts, nochmal nach unten, notieren. Und so offensichtlich gibt es viele andere einzigartige Wege auf dem Weg. Ich glaube, es gibt 11 und insgesamt. Und so wissen Sie, das ist, wie ich schon sagte, das ist das besondere Setup, das wir in diesem Video lösen wollen, aber der Algorithmus, den wir schreiben werden, sollte in der Lage sein, jede Art von gelangweilt mit jeder Art von Dimension zu nehmen , richtig? Dies ist ein fünf mal fünf Brett, aber es könnte ein Fünf mal zehn oder eine 11 mal 223 mal acht sein, und jede Art von zufälligen Auswahl von Barrieren auf dem Weg. Also wirklich angesichts jeder Art von gelangweilt, sollten wir einen Algorithmus haben, der dieses Problem lösen sollte, oder? Berechnen Sie die ganze Anzahl oder berechnen Sie die Anzahl der eindeutigen Pfade durch dieses Board von S nach E. Also jetzt, wenn Sie versuchen, einen dynamischen Programmieransatz zu diesem Problem anzuwenden, ist das erste, was Sie tun wollen, zu versuchen, herauszufinden was die kleineren, aber sehr ähnlichen Unterprobleme wären , dass Sie während der Ausführung Ihres Algorithmus irgendwie lösen können. Und so, dass Sie die Lösungen für diese Unterprobleme verwenden können, um schließlich die endgültige Antwort zu berechnen, nach der Sie gesucht haben. Also ermutige ich Sie, dieses Video für eine Minute zu pausieren und nur über ein kleineres, aber sehr ähnliches Unterproblemnachzudenken über ein kleineres, aber sehr ähnliches Unterproblem , das es Ihnen erlauben würde, Ihren Weg zu bauen, um endlich die Gesamtzahl der eindeutigen Pfade von S zu E. Also mach weiter und pausiere das Video und komm zurück, wenn du bereit bist. Okay, ich hoffe, Sie haben sich ein paar Minuten Zeit genommen, um darüber nachzudenken. Und so werde ich einfach in die Lösung hier eintauchen. Und so, um die Anzahl der eindeutigen Pfade zu diesem Ende Kachel zu berechnen, müssen wir zuerst die Anzahl der eindeutigen Pfade zu den benachbarten Kacheln berechnen, im Grunde diese. Und das hier, wenn man bedenkt, dass wir nur nach unten oder nach rechts bewegen können. Von dieser Kachel aus können wir uns nach rechts bewegen, um zu unserer ETL oder n Kachel zu gelangen. Und von dieser Fliese können wir nach unten gehen, um zu unseren Endplatten zu gelangen. Wie gesagt, müssen wir zuerst die Anzahl der eindeutigen Pfade zu diesen Fliesen von unserer Startfliese kennen. Um jedoch die Anzahl der eindeutigen Pfade zu diesen Kacheln zu berechnen, müssen wir zuerst die Anzahl der eindeutigen Pfade zu ihren benachbarten Kacheln berechnen. Das wäre also dieser und dieser hier. Und so hoffe ich, Sie können hier ein Muster sehen, in dem, wissen Sie, um die Antwort auf unser, unser echtes Problem zu berechnen , das wir lösen wollen. Wir müssen die Anzahl der eindeutigen Pfade zu all diesen leeren Kacheln berechnen, zurück zu unserer Startkachel. Und insbesondere wird die Anzahl der eindeutigen Pfade zu unserer Endkachel die Summe der Anzahl der eindeutigen Pfade zu den benachbarten Kacheln sein. Also, wenn es vielleicht fünf Wege vom Anfang bis zu diesem speziellen Reifen hier gibt. Und dann gibt es sechs Pfade von Anfang bis zu dieser Kachel. Wenn man diese beiden zusammenfasst, wird das 11 sein. Und damit einige 11 die Antwort auf das Ganze sein werden, Ordnung, es wird 11 Pfade insgesamt von Anfang bis Ende geben. Und so wird es für all diese Kacheln funktionieren, richtig? Die Anzahl der eindeutigen Pfade zu dieser Kachel wird beispielsweise die Summe der Anzahl der eindeutigen Pfade zu den angrenzenden Kacheln sein. Und im Hinterkopf natürlich, dass wir nur entweder nach unten oder nach rechts bewegen können. Also für diese spezielle Kachel und der einzige Weg, den wir erreichen können, ist es, von oben nach unten zu bewegen. Natürlich können wir nicht von rechts kommen, da das hier eine Barriere ist. Und so wird die Anzahl der eindeutigen Pfade zu dieser speziellen Kachel nur die Anzahl der eindeutigen Pfade zu dieser Kachel sein, richtig? Die Art und Weise, wie Sie sich das im Grunde vorstellen können, ist, sagen wir, es gibt zwei Pfade vom Anfang bis zu dieser Kachel. Und es gibt offensichtlich 0 Pfade von Anfang bis als Barriere-Kacheln. Die Gesamtzahl der eindeutigen Pfade zu diesem Kerl hier wird im Grunde nur die Summe von zwei plus 0 sein. Und das ist gleich zwei. Und wie ein weiteres Beispiel, wenn man sich diese Kachel hier ansieht, wird die Anzahl der eindeutigen Pfade die Summe seiner benachbarten Kacheln sein, richtig? Und jetzt sind beide angrenzenden Fliesen offen. Also, wissen Sie, wenn es drei Pfade zu dieser Kachel von Anfang an gibt, und es gibt vielleicht vier Pfade von Anfang bis zu dieser Kachel und die Summe drei plus 47. Und es wird sieben einzigartige Wege zu diesem Tau hier geben. Und so können wir eine sehr einfache rekursive Funktion erstellen, die dies tun würde. Aber wenn wir nicht dynamische Programmierung im Sinne der Speicherung oder Speicherung der Ergebnisse all dieser Kacheln auf dem Weg verwenden , dann wird die Laufzeit dieses Algorithmus extrem ineffizient sein. Und das ist, weil, wissen Sie, sagen wir zum Beispiel, wir schauen auf diesen leeren Turm i hier, und wir versuchen, die Anzahl der einzigartigen Pfade von Anfang bis zu diesem leeren Turm genau hier zu finden . Also müssten wir im Grunde das gesamte Brett durchqueren und alle möglichen Wurzeln bis zu unserem Startfliese betrachten . Und was auch immer die Nummer ist, wir hätten die zur Hand und dann würden wir es wieder von dieser Kachel machen, richtig? Also wieder würden wir das gesamte Brett wieder durchqueren und die Anzahl der eindeutigen Pfade vom Anfang bis zu dieser Kachel herausfinden. Und wenn wir diese Antwort haben, können wir offensichtlich diese beiden zusammenfassen und unsere endgültige Lösung bekommen. Aber das ist sehr ineffizient, weil wir zuerst auf diese Kachel zurückgehen, sobald wir das gesamte Brett navigieren und herausfinden, alle möglichen Pfade von One zu r Start Kachel. Wenn wir das Gleiche wieder von dieser Kachel aus machen, wird es eine Menge Überlappungen geben, was bedeutet, dass sich einige der Pfade von dieser Kachel zurück zu unserer Startkachel mit den gleichen genauen Pfaden von dieser Kachel überlappen. D2 sind Startkachel. Und als Beispiel, sagen wir, einer der Pfade, die wir von dieser Kachel zurück zu unserem Startfliese herausfinden , ist, dass wir diesen Weg gehen und uns dann auf diese Weise zurückarbeiten. Boom, Knochen zurück zu unserem Starthandtuch, richtig? Das ist der Weg, den wir einschlagen. Und wenn wir das Gleiche von dieser Kachel machen, werden wir irgendwann versuchen, einen Weg zu finden, der diese Route entlang geht. Und dann boom genau hier. Hier würden sich die beiden Wege kreuzen und wir würden den gleichen genauen Weg zurück zu unserem Startpunkt nehmen. Und so ist das nur eine Zeitverschwendung, wenn man diesen Weg wieder aufrechterhält. Wenn wir irgendwann zu dieser Kachel kommen und wir bereits wissen, dass es einen Weg zurück zu unserem Starthandtuch gibt, dann sollten wir einfach aufhören und diese Informationen verwenden, richtig? Wenn zum Beispiel, sagen wir, wir versuchen, die Anzahl der eindeutigen Pfade vom Anfang bis zu dieser benachbarten Kachel genau hier zu berechnen . Wenn wir das tun, wenn wir schließlich herausfinden, gibt es, sagen wir, drei insgesamt einzigartige Pfade von dieser Krawatte direkt hier zurück zu unserem Startfliese. Dann später, wenn wir versuchen, die Anzahl der eindeutigen Pfade vom Anfang bis zu dieser benachbarten Kachel herauszufinden . Immer wenn wir zurückkommen, wenn wir versuchen, unser Brett wieder zu durchqueren , sollten wir wissen, dass, okay, na ja, in einer vorherigen Berechnung, wir haben bereits herausgefunden, dass es drei einzigartige Wege zurück zu unserem Ausgangspunkt. Also kann ich die Informationen einfach nehmen und verwenden und nicht weiter berechnen. Und hier wird dieses Männerbrett ins Spiel kommen. Der Mensch ist wieder kurz für das Gedächtnis. Und es ist im Grunde nur ein exaktes Duplikat in Bezug auf die Abmessungen unseres Boards hier. Und das wird verwendet, um die Anzahl der eindeutigen Pfade zu jedem dieser offenen Kacheln zu speichern . Also als Beispiel, richtig, wenn ich sagte, sagen wir, es gibt drei einzigartige Wege zurück von dieser Kachel, unserem Ausgangspunkt. Dann im exakt gleichen Quadranten oder in der exakt gleichen Kachel, sollte ich in unserem Gedächtnis sagen, es wird die Nummer drei hier haben. Und so, wie ich schon sagte, wenn wir versuchen, die Anzahl der eindeutigen Pfade vom Anfang bis zu dieser benachbarten Kachel herauszufinden . Immer wenn wir das Brett durchqueren und zu dieser Kachel zurückkehren, können wir in unser Gedächtnis schauen und sagen: Oh, weißt du, wir haben bereits berechnet, dass es drei Pfade gibt, also greifen wir einfach diese Zahl und benutzen sie und dann einfach nicht weiter noch weiter. Und jetzt sind wir an dieser Stelle endlich bereit, in den Code zu kommen und die Lösung für dieses Problem herauszufinden. Und nur zur Information, als ich dieses Video hier bearbeitete, erkannte ich, dass ich tatsächlich einen Fehler in diesem Code gemacht habe, dieser Zeile hier, es heißt, ob Rho gleich 0 ist oder col gleich 0 ist, sollte es eigentlich sein. Und dieser Basisfall sollte sein, wenn rho gleich 0 ist und col gleich 0 ist. Also, wenn Sie sehen das Risiko ist Video, nur so tun, als ob es zwei kaufmännisches Undd-Symbole hier gibt, was bedeutet und nicht oder. Und das wird sich tatsächlich auf das Endergebnis der Berechnung auswirken , wenn ich am Ende dieses Videos eine kleine Demonstration mache. Es gibt also hier sieben einzigartige Pfade durch dieses Board, nicht 11. Und noch einmal, das ist nur, weil ich diesen kleinen Fehler hier gemacht habe. Tut mir leid, und bedenken Sie das im Hinterkopf. Danke. Und das ist die eigentliche Funktion selbst, die diese Berechnungen durchführen wird. Und ich habe den größten Teil des Codes hier bereits für Sie geschrieben, aber ich habe ein paar Fragezeichen vorhanden, nur um Sie irgendwie zu zwingen, darüber nachzudenken, was diese Basisfälle sollten in Bezug auf die Werte sein, die sie zurückgeben sollten. Und so direkt neben der Fledermaus, sollten Sie hier einige Ähnlichkeiten zwischen dieser Lösung und dem Fibonacci-Problem sehen , das Sie im letzten Video gesehen haben. Und dass wir im Grunde nur ein paar einfache if-Anweisungen haben, die die Basisfälle sind. Und dann haben wir hier unten eine Rekursion, richtig? Wir haben im Grunde zwei rekursive Aufrufe. Und die Ergebnisse dieser rekursiven Aufrufe werden nur zusammengefasst und in unserem Speicher gespeichert. Und die Art und Weise, wie das funktioniert, ist durch unsere Rekursion hier. Wir werden zunächst an unserer Endkachel beginnen und rückwärts arbeiten. Die Rekursion wird uns den ganzen Weg zurück durch dieses Brett führen, zurück zu unserem Startfliese. Und das ist der ultimative Basisfall, auf den ich in einer Minute eingehen werde. Und dann, sobald die Rekursion wieder an unserer Startkachel stoppt, werden wir Backup durch all diese zurückgeben, diese Funktionsaufrufe sichern den Stapel. Und dann werden wir die Anzahl der eindeutigen Pfade zu all diesen leeren Kacheln auf dem Weg füllen . Backup, bis wir letztendlich bis zum Ende der Kachel am Ende kommen. Und wir werden unsere Lösung haben. Und nur für Ihr Bewusstsein ist die Art und Weise, wie dieses Board und diese Speicherkomponente strukturiert werden , der Benutzer im Grunde nur zweidimensionale Arrays sein wird, oder? Grundsätzlich nur ein Array von Arrays. Und das ist, was Sie hier in unseren Argumenten dieser Funktion sehen können. Wir haben unser Board, das, wie Sie sehen können, nur ein zweidimensionales String-Array ist. Und unser Gedächtnis, dasselbe, nur ein zweidimensionales ganzzahliges Array. Und die Funktionen hier unten sind nur dafür verantwortlich das Board selbst zu machen und einige Barrieren einzubauen und dann auch das eigentliche Speicherarray zu erstellen. Und die Hauptfunktion besteht darin, das Board im Grunde zu erstellen, den Speicher zu erstellen und dann einfach unsere Funktion „einzigartige Pfade finden“ aufzurufen. Und es wird nur die Lösung ausdrucken, die es findet. Und r n Kachel wird an der Koordinate von 44 sein, was bedeutet Zeile für Spalte vier. Und denken Sie daran, Arrays sind 0 Index. Also im Grunde ist dies Zeile 0, Spalte 0. Und wie gesagt, unsere Endplatte ist in Zeile 01234, Spalte 012344, Komma vier, das ist die Koordinate unserer Endfliese und unsere Startfliesen offensichtlich in Zeile 0, Spalte 0. So ist alles, was funktionieren wird, jetzt auf unsere Funktion zurückkommen, können wir zwei andere Argumente sehen. Dies ist die aktuelle Zeile, die wir im aktuellen Anrufnetz betrachten, das wir betrachten. Und diese Funktion wird zuerst von der Hauptfunktion mit den Koordinaten von vier Komma vier aufgerufen , oder? Gegen Start bei R n Fliese und dann rückwärts arbeiten. Und die Art und Weise, wie wir rückwärts arbeiten, ist, wie ich durch diese rekursiven Funktionsaufrufe sagte, oder subtrahieren Sie einfach einen von der aktuellen Zeile, in der wir sind, oder subtrahieren Sie eine von der aktuellen Spalte, die sich befanden. Zum Beispiel, wenn diese Funktion zum ersten Mal aufgerufen wird, ist Zeile vier und Spalte vier. Und dann, wenn wir diese rekursiven Aufrufe machen, sagen wir, wir betrachten diese 1 zuerst. Dies wird wieder Finding Pads nennen, außer mit Rho gleich 34 minus eins ist drei und dann Spalte vier. Und dann, wenn man sich diesen rekursiven Funktionsaufruf jetzt ansieht, wird die gleiche Funktion erneut mit Zeile vier aufrufen, aber jetzt Spalte drei. Und wie gesagt, diese rekursiven Aufrufe werden immer und immer wieder passieren. Was wird wieder, beginnend von hier, langsam durchqueren wir unseren Weg zurück durch unser Brett, bis wir einige dieser Basisfälle getroffen haben, die im Grunde, wissen Sie, irgendwann werden wir eine Reihe oder eine Spalte schlagen kleiner als 0 ist, da wir immer von unserer aktuellen Zeile oder aktuellen Spalte subtrahieren. Und offensichtlich können wir nicht zu einer Zeile oder Spalte kommen, das ist eine negative Zahl. Also werden wir etwas dorthin zurückgeben. Ein weiterer Basisfall ist, wissen Sie, irgendwann werden wir eine Barriere treffen. Und offensichtlich können wir an diesem Punkt nicht weiter gehen. Also müssen wir, wir müssen an diesem Punkt etwas zurückgeben. Oder wir haben unseren einfachsten Basisfall getroffen, das heißt, wir kommen einfach zu unserem Ausgangspunkt zurück, in welchem Fall, wissen Sie, wir können nicht weiter gehen. Und so geben wir an diesem Punkt auch eine Art Wert zurück. Und dann natürlich, wenn wir anfangen, Backup durch all diese Funktionsaufrufe zurückzugeben, richtig, wenn diese rekursiven Aufrufe beendet sind, werden die Ergebnisse offensichtlich zusammengefasst und dann in unserem Speicher-Array gespeichert. Also, dass irgendwann später die Straße hinunter, wenn wir jemals wieder auf die gleiche Zeile und Spalte durch einen Pfad, den wir zu berechnen versuchen. Dann werden wir diesen Fall hier treffen, wo wir unseren Speicher angesichts der aktuellen Zeile und col überprüfen, jetzt sind wir bei, wir werden sehen, ob der Wert dort größer als 0 war. Und wenn es so ist, dann werden wir in diesem Fall offensichtlich einen Wert zurückgeben und keine rekursiven Aufrufe machen. Und jetzt noch einmal, ermutige ich Sie, dieses Video zu pausieren und darüber nachzudenken , was diese Basisfälle zurückkehren sollten, richtig? Dies sind nur ganze Zahlen, die sie eine Zahl zurückgeben werden. Also gehen Sie weiter und pausieren Sie das Video und denken Sie darüber nach , was jede dieser, wenn Aussagen zurückkehren sollte. Okay, ich hoffe, du nimmst dir ein paar Minuten Zeit, um darüber nachzudenken. Schauen wir uns zuerst diesen einfachsten Basisfall an, in dem wir zu Zeile 0, Spalte 0 zurückkehren , was bedeutet, dass wir wieder an unserem Ausgangspunkt sind. Und was sollte dieser Basisfall zurückgeben? Nun, die Antwort wird einfach eine sein. Und lasst uns darüber nachdenken, warum zuerst, zweitens. Nehmen wir also an, durch diese rekursiven Funktionsaufrufe irgendwann kommen wir entweder zu dieser benachbarten Kachel zu unserem Startpunkt oder zu dieser benachbarten Kachel zu unserem Startpunkt, oder? Weil, weißt du, sagen wir, wir sind genau hier. Dies ist Zeile 0, Spalte eins. Irgendwann werden wir diesen rekursiven Aufruf machen , der uns an Zeile 0, Spalte 0 senden wird. Und das wird uns natürlich zu unserem Ausgangspunkt zurückschicken, dem Basisfall, der einen zurückgeben wird. Und das sollte logisch sinnvoll sein, denn wenn das passiert und wir zurück zu benachbarten Kacheln sind, gibt es genau einen einzigartigen Weg von unserem Startfliese zu diesem Kerl genau hier. Und dasselbe gilt für diese benachbarte Fliese. Dies ist Zeile 1, Spalte 0. Und so werden wir irgendwann diesen rekursiven Aufruf machen , der uns in Zeile 0, Spalte 0 zurückschicken wird. Und das ist natürlich wieder Startort, das ist der Basis-Fall. Es sollte eins zurückgeben, da es wieder genau einen eindeutigen Pfad vom Anfang bis zu dieser bestimmten Kachel gibt. Und so werden wir in beiden Fällen in unserem Gedächtnis den Wert eines in der entsprechenden speichern. Standorte. Und lass mich diesen Kerl auch loswerden. Also jetzt ist dies der aktuelle Zustand unseres Speichers 11, der dieser Kachel entspricht. Und diese Kachel, was bedeutet, dass es einen einzigartigen Weg zu einer dieser Kacheln von unserem Ausgangspunkt aus gibt. Sehen wir uns jetzt den nächsten Basisfall an , der hier ist. Und dies ist der Fall, wenn die aktuelle Zeile oder Spalte, die wir betrachten, kleiner als 0 ist. Und das wird in Fällen wie diesem passieren, wo wir sagen, Spiel, wir sind wieder hier. Und so wird uns einer dieser rekursiven Funktionsaufrufe natürlich zurück zu unserem Ausgangspunkt schicken . Aber der andere wird uns hier rüber ins Niemandsland schicken. Und offensichtlich ist es unmöglich, in Niemandsland zu kommen. Und so sollten wir in diesem Fall einfach 0 zurückgeben. Und das vervollständigt im Grunde den ganzen Fall von, wissen Sie, wenn wir an dieser Kachel hier wären, denn wie Sie gerade einen dieser rekursiven Aufrufe gesehen haben, die uns zu unserem Ausgangspunkt zurückschicken würden, was ist der Basisfall, der das eine und das andere rekursive Call-Center in Niemandsland zurückgibt. Und das trifft auf einen Basisfall, der 0 zurückgibt. Und dann summieren wir natürlich diese beiden Zahlen zusammen. Eins plus 0 ist eins, und hier speichern wir diesen Wert von Eins in unser Gedächtnis. Gleiches gilt für diesen angrenzenden Turm. Ich höre, einer dieser rekursiven Anrufe schickt uns zurück zu unserem Ausgangspunkt, der einen zurückgibt. Die anderen rekursiven Aufrufe schickt uns in Niemandsland, das 00 zurückgibt und eins ist eins. Ordnung? Und so ist der nächste Basisfall dieser hier. Und dies ist der Fall, wenn die aktuelle Zeilen- und Spaltennummer tatsächlich eine Barriere aufweist. Und so offensichtlich mit dem Niemandsgrundfall können wir nicht zu dieser speziellen Kachel kommen, richtig? Zum Beispiel gibt es keinen Pfad vom Anfang zu dieser bestimmten Kachel, da dort eine Barriere vorhanden ist. Und so wie bei diesem Niemandsland Basis-Fall, wird dieser auch einfach 0 zurückgeben. Und so haben wir dann unsere letzte if-Anweisung, die mit unserem tatsächlichen Speicher-Array zu tun hat. Und so sagen wir zum Beispiel, wir sind durch unsere rekursiven Aufrufe hier durchqueren , dass wir hier bei diesem Tau landen. Und wieder haben wir bereits die Nummern 11 im Speicher gespeichert. Wenn wir also bei diesem Tau hier sind, wird uns einer dieser rekursiven Aufrufe zu dieser Kachel schicken. Und dann wird der andere rekursive Aufruf uns zu dieser Kachel schicken. Und für diese beiden Kacheln. Wenn wir zu dieser if-Anweisung kommen, werden wir unseren Speicher überprüfen, um zu sehen, ob es einen Wert gibt, der dort gespeichert wurde. Und in der Tat, eins in eins oder beide in ihren jeweiligen Quadranten und Speicher gespeichert. Und so werden wir in diesen Fällen nur den Wert zurückgeben, der dort gespeichert ist. Und das ist die Schlüsselkomponente dieser gesamten Lösung hier, weil diese if-Anweisung uns erlaubt, jede weitere Rekursion zu überspringen, was im Grunde nur redundante Neuberechnung der Suche nach Pfaden zu unserem Startpunkt. Und so letztendlich, wenn wir wieder bei diesem Kerl sind, und einer dieser rekursiven Funktionsaufrufe sendet uns zu dieser Kachel. Und der andere rekursive Aufruf schickt uns zu dieser Kachel. Beide Funktionsaufrufe werden einen zurückgeben. Und so fügen wir am Ende, wenn diese Funktionen zurückkehren, wenn diese Funktionen zurückkehren,die Ergebnisse zusammen. Also eins plus eins ist zwei, und dann ist das die Anzahl der eindeutigen Pfade vom Anfang bis zu dieser bestimmten Kachel. Und im entsprechenden quadratischen Speicher. Dort haben wir die Nummer zwei angefangen. Und wenn Sie logisch darüber nachdenken, sollte das Sinn machen, denn um diese Kachel von unserem Ausgangspunkt zu bekommen, können wir entweder nach rechts und dann nach unten oder unten gehen und dann zwei mögliche Pfade schreiben. Und ich hoffe, Sie sehen hier ein Muster, so dass wir , wenn wir Backup durch all diese Funktionsaufrufe zurückgeben, die Werte in unserem Speicher-Array auf dem Weg füllen werden , so dass bis zum Ende, wenn kehren wir den ganzen Weg zurück zu unserer n Kachel, die eigentlich ist, wo wir am Anfang angefangen haben. Wir werden all diese Kacheln in Erinnerung haben, so dass am Ende alles, was ich tun muss, ist die Werte zu nehmen, die in dieser benachbarten Kachel gespeichert sind. Und diese angrenzende, benachbarte Fliese. Fügen Sie sie zusammen, und das wird der Wert sein, die Anzahl der eindeutigen Pfade, sozusagen von unserem Ausgangspunkt bis zum Endpunkt. Und so wie eine kleine Demonstration hier, die zurück zu meinem Terminal kommen. Und ich werde weitermachen und den Code kompilieren. Und dann kann ich es einfach ausführen. Und wieder, all das wird tun, ist, dass es diesen Code ausführen wird. Und für dieses spezielle Board hier wird alle möglichen einzigartigen Pfade von Anfang bis Ende finden und nur diese Zahl ausdrucken. Wenn ich also voran gehe und die Eingabetaste drücke, wie ich am Anfang dieses Videos sagte, gibt es 11 einzigartige Pfade und da gehst du. Das ist genau das, was ein berechnetes. Und es tat so sehr, sehr schnell. Und wieder einmal, das liegt daran, dass es nie eine redundante Berechnung durchführen muss, im Grunde Pfade mehr als einmal zu unserem Ausgangspunkt neu berechnet werden. Selbst wenn dieses Board extrem groß wäre, vielleicht 100 mal 100 Fliesen und eine Reihe von Barrieren, die zufällig verteilt sind, dass es in diesem Board immer noch in der Lage wäre, alle Wege sehr, sehr schnell zu laufen und herauszufinden, im Gegensatz zu nur einem einfache rekursive Methode ohne dynamische Programmierung, keine Speicherung von Werten auf dem Weg. Und mit einem Board von 100 mal 100 würde es wahrscheinlich sehr, sehr lange dauern , um all diese redundante Berechnung durchzuführen. Also hoffe ich, dass alles Sinn gemacht hat. Und im letzten Video, das als nächstes erscheint, werde ich Sie durch ein weiteres Beispielproblem führen, das meiner Meinung nach ziemlich schwierig sein wird. Aber wieder einmal, es wird immer noch viele Ähnlichkeiten in der Art und Weise geben, wie wir die Lösung für dieses Problem aus dem, was Sie in diesem Video mit diesem einzigartigen Pfadproblem gesehen haben . Und dann auch im vorherigen Video mit dem Fibonacci-Nummern Problem. Also nochmals vielen Dank fürs Ansehen, und wir sehen uns im nächsten. 5. Coin (schwer): Alles klar, willkommen zum letzten Video in diesem Kurs. Und wie ich in diesem Video hier sagte, werde ich Sie durch ein weiteres Problem führen, das meiner Meinung nach ziemlich schwierig in der Natur sein wird . Sie können so etwas in einem Interview oder in der Schule begegnen. Aber ich würde sagen, im Durchschnitt würde eine Frage dieser Art von Schwierigkeit wahrscheinlich nicht allzu oft auftauchen. Aber wenn Sie das verstehen und sich durch die Lösung arbeiten, ein gutes Verständnis dafür haben, wie alles funktioniert, dann sind Sie sehr gut vorbereitet und kariert um Ihren Weg durch so ziemlich jede dynamische Programmierart zu arbeiten von Fragen. Also taucht man einfach hier rein zur Problemaussage. Das Problem, das wir in diesem Video lösen wollen, wird sein, also erhalten Sie Münzen verschiedener Stückelungen und eine bestimmte Summe Geld. Und der Punkt dieses Problems hier ist, dass Sie eine Funktion schreiben möchten die wenigste Anzahl von Münzen berechnet, die Sie benötigen, um diese Menge Geld zu bilden. Und natürlich, wenn es nicht möglich ist, diese Münzen zu verwenden, schaffen Sie diese bestimmte Menge Geld? Dann geben wir nur ein negatives zurück. Also als Beispiel, und das ist das eigentliche Szenario, das wir in diesem Video zu lösen versuchen werden. Also dieses Array hier, das in unserer Münzvariablen gespeichert ist, ist das unsere Reihe von Münzbezeichnungen. So können Sie dies lesen, als wer im Grunde Münzen hat , die im Grunde 12 ¢$0,05 darstellen, oder? Dies sind im Grunde Werte für bestimmte Münzen, aber wir haben im Grunde drei Münzen, und das sind ihre jeweiligen Werte. Und die Menge an Geld, die wir versuchen, durch diese Münzen zu schaffen, ist $0,11. Und natürlich, wenn man bedenkt, dass wir versuchen, dies mit der minimalen Anzahl von Münzen möglich zu tun. Also können wir natürlich, mit einer Münze, die $0,01 darstellt, können wir einfach sagen, hey, wir nehmen 11 von diesen Jungs und gehen. Wir haben $0,11, aber offensichtlich haben wir einige andere Münzen mit größeren Werten und wir können sie verwenden, um $0,11 zu schaffen, aber mit weniger Münzen. Und Sie können wahrscheinlich einfach hier sitzen und sich das ansehen, eine Minute darüber nachdenken und selbst zur Lösung kommen, damit, okay, die Art und Weise, wie wir 0,11$ in den wenigsten möglichen Münzen schaffen können , ist, dass wir einfach zwei von diesen Jungs haben können, Richtig? 0,05 $ je. Also zwei davon wären $0,10. Und dann brauchen wir nur noch einen. Wir können diesen Kerl mit $0,01 nehmen und sie zusammen hinzufügen. Wir haben offensichtlich 0,11 Dollar. Also am Ende brauchen wir im Grunde nur drei Münzen, um diesen Betrag zu summieren. Das ist die wenigste Anzahl von Münzen möglich. Und das ist es, was wir wollen, dass unsere Funktion hier unten zurückkehrt. Also kommen wir zu unserer Funktion hier. Und das ist der Code, den ich für dich geschrieben habe. Genau wie im letzten Video habe ich ein paar dieser Basis-Case-Rückgabe-Anweisungen nur irgendwie mit Fragezeichen, weil ich Sie nicht zwingen wollte, darüber nachzudenken. Diese Basisfälle sollten zurückkehren, aber Sie können nur sehen, indem Sie sich diesen Code hier ansehen, er ist definitiv aber komplexer. Hier ist noch mehr los. Haben immer noch im Allgemeinen das gleiche Format wie in den vorherigen Videos, wo wir einige Basisfälle haben und wir haben eine Rekursion hier. Und wir werden Ergebnisse zu unseren Unterproblemen speichern, über die ich noch nicht in irgendeiner Art Speicherarray oder Komponente gesprochen habe. Und die Lösungen der Unterprobleme verwenden, um die endgültige Antwort zu erstellen, die wir suchen. Also, bevor ich in alle Details komme, lass mich wieder an die Spitze kommen. Und noch einmal ermutige ich euch, dieses Video zu pausieren und sich ein paar Minuten Zeit zu nehmen, um darüber nachzudenken , was diese kleineren, aber sehr ähnlichen Unterprobleme wären. Das würde Ihnen erlauben, dieses Hauptproblem hier zu lösen. Also mach weiter und pausiere das Video und komm zurück, wenn du bereit bist. Okay, ich hoffe, du hast dir ein paar Minuten Zeit genommen und darüber nachgedacht. Und so werde ich einfach in die Antwort hier eintauchen. Also werden die Unterprobleme für diese Problemaussage, die wir zu lösen versuchen, nun, wissen Sie, wenn wir die minimale Anzahl von Münzen in diesem Fall finden wollen, um bis zu 0,11$ zu addieren. Bevor wir das tun können, müssen wir zuerst die minimale Anzahl von Münzen herausfinden , die eine geringere Menge an Geld schaffen. Und das ist eine kleinere Menge an Geld wird das Ergebnis sein, indem wir unseren anfänglichen Betrag nehmen und daraus die Werte jeder unserer Münzen subtrahieren , die wir haben. Als Beispiel nehmen wir 11, subtrahieren eins, das gibt Ihnen zehn. Dann machen wir dasselbe, 11 minus zwei für die zweite Münze, das ist neun. Und dann machen wir dasselbe wieder für die dritte Münze. 11 minus fünf ist sechs, also haben wir 109 $0,06 Cent übrig, nachdem wir die Werte jeder unserer Münzbezeichnungen hier subtrahieren. Und so müssen wir für jede dieser kleineren Geldbeträge herausfinden, wie die geringste Anzahl an Münzen möglich wäre, die sich zu diesen kleineren Beträgen addieren würde. Also die wenigste Anzahl von Münzen, die bis zu $0,10 summieren, die bis zu $0,09 addieren, und das summieren sich auf $0,06. Und hier kommt das rekursive Muster ins Spiel denn um die Ergebnisse für diese kleineren Geldbeträge zu berechnen, müssen wir diesen Vorgang erneut wiederholen. Und für jede dieser kleineren Geldbeträge, wenn Sie von ihnen die Werte jeder unserer Münzdominationen subtrahieren. Also für die kleine Menge von $0,10, wiederholen wir diesen Prozess. Zehn minus eins ist 910, minus zwei ist 810, minus fünf ist fünf. Also 98, $0,05. Das sind die noch kleineren Geldbeträge. Und wir müssen die wenigste Anzahl von Münzen herausfinden , die zu diesen kleineren Beträgen addieren. Und dann noch einmal, dieser Prozess wiederholt sich und wir müssen die Werte unserer Münzen Nominierungen von diesen noch kleineren Beträgen subtrahieren die Werte unserer Münzen Nominierungen von und so weiter und so weiter, bis auf die kleinste Menge Geld möglich ist, das ist nur $0,01. Und dann, wenn wir wissen, die minimale Anzahl von Münzen möglich, um bis zu 100%, das ist nur im Grunde dieser Kerl genau hier. Wir haben eine Münze im Wert von $0,01. Dann können wir unseren Weg zurück durch all die kleineren Geldbeträge in einen Fonds bauen , um auf den ursprünglichen Betrag zurückzukommen, den wir von 0,11$ erhalten. Und so wirklich im Wesentlichen, was wir hier tun, ist, dass wir versuchen, alle möglichen Möglichkeiten herauszufinden, die Werte über Münzen hier zu kombinieren, um möglicherweise 0,11$ zu entsprechen, oder? Jede mögliche Kombination. Und die Art und Weise, wie wir das tun, ist durch die Methode, die ich gerade beschrieben habe, jeden dieser Münzwerte von einem subtrahieren, von der Menge an Geld, die wir erhalten. Und sie subtrahieren ständig die Münzwerte von diesen kleineren und kleineren Beträgen. Aber wenn wir das nur richtig machen würden, erkunden Sie hier jede mögliche Kombination unserer Münzen, das wäre extrem ineffizient, weil die Anzahl der möglichen Kombinationen Ihrer Münzen exponentiell sein wird. Das bedeutet, je mehr Münzbezeichnungen Sie hier in Ihrem Eingang haben, desto exponentieller Anzahl möglicher Kombinationen dieser Münzen müssen Sie durchschauen , um herauszufinden, welche Kombination von Münzen Ihnen die kleinste Anzahl der Münzen. Um die Menge an Geld, die Sie versuchen, zunächst zu entsprechen, ist am Anfang gelöst. Und so kommt hier unser Memory-Array ins Spiel, denn während wir diesen Prozess durchlaufen, habe ich ständig diese Münzbezeichnungen subtrahiert oder diese subtrahiert ihre Werte von kleineren und kleineren Mengen von Geld. Während wir diesen Prozess durchlaufen und die wenigste Anzahl von Münzen herausfinden, die nötig sind , um 12 $0,03 Cent für Sinn zu machen, richtig? Bauen wir zurück zu $0,11, können wir diese Werte speichern, richtig, die wenigsten Anzahl von Münzwerten in unserem Speicher-Array. Also, wenn wir jemals wieder durch all diese Rekursion zu versuchen, wieder herauszufinden , was die wenigste Anzahl von Münzen, die erforderlich sind, um bis zu $0,04 addieren. Nun, wir können in unser Array schauen und sagen, oh, wir haben bereits berechnet, dass es in der Vergangenheit zwei Münzen sein könnten oder was auch immer es ist. Damit wir diesen Wert greifen können. Und ich muss weiter unten berechnen und einfach wieder nach oben zurückkehren und unseren Weg zurück zu dieser 11. gesendeten Nummer bauen. Lassen Sie mich hier auf unsere Münzwechselfunktion zurückkommen. Und so wird die Art und Weise, wie das funktioniert, und nur zuerst Blick auf die Argumente hier. Diese Münze geänderte Funktion nimmt also drei Argumente ein. Das erste davon ist unser Münzfeld, richtig? Dies ist nur unsere Reihe von Münzbezeichnungen, die wir in diesem Problem gegeben werden. Das zweite Argument ist dieser RAM, Integer-Argument RAM ist kurz für Rest. Und dieses Argument wird die aktuelle Geldsumme darstellen, die wir im Kontext dieser Funktionsaufrufe betrachten. Also wird dieser Wert als 11 gestartet werden, oder? Unsere Hauptfunktion wird unsere Münzwechselfunktion aufrufen, und es wird die Argumente unserer Münzen übergeben, offensichtlich die anfängliche Geldmenge, die wir versuchen, zwei zusammenzufassen, das ist 0,11$, und unser leeres Speicher-Array. Und dann, da wir unsere Münzstückelungswerte von unserem ursprünglichen Betrag subtrahieren , 0,11$. Wir werden durch diesen Aufruf diese Funktion immer und immer wieder. Jedes Mal, wenn wir diese Münzwechselfunktion erneut aufrufen, werden wir einen bestimmten Münzwert von unserem Betrag subtrahieren, und diese Restargumente werden diesen Betrag repräsentieren. Also in dem Beispiel, das ich zuvor beschrieben habe, wo wir $0,11 nehmen und einen gesendeten subtrahieren, richtig? Das wird Ihnen das Ergebnis von zehn geben. Irgendwann, wenn wir diese Funktion wieder aufrufen, wird Rahm zehn sein. Und dann später, wenn wir zwei von 11 subtrahieren wird neun sein und dann so weiter und so weiter den ganzen Weg nach unten. Ram ist entweder kleiner als 0 oder gleich 0 und so weiter und so weiter. Das sind wieder die Basis-Fälle, richtig? Und dann ist natürlich das letzte Argument, wie ich gesagt habe, unser Speicher-Array. Und so, wie ich bereits in diesem Video sagte, hat diese Münzwechselfunktion eine sehr ähnliche Struktur wie die vorherigen Videos, die Sie gesehen haben. Wir haben hier unsere Basis-Fälle. Und dann ist dies eine Art neues Stück, das benötigt wird, um dieses Problem zu lösen. Und es ist nur eine einfache for-Schleife und es tut nur, was ich oben in diesem Video beschrieben habe , wo für jeden unserer Münzbezeichnungswerte, oder? Dies für, for-Schleife wird nur durch jede unserer Münzbezeichnungen schleifen. Und für jede Münze wird es nur rekursiv unsere Münzwechselfunktion aufrufen, mit sind gleich. Array von Münzen, das gleiche Speicher-Array, aber der einzige Unterschied ist, dass wir den Wert dieser Münze von der restlichen Menge an Geld, die wir haben, subtrahieren . Und dann hier unten, ist dies, wo, wie Sie zuvor gesehen haben, oder wir nehmen einfach einige der Ergebnisse aus früheren Berechnungen, die von dieser for-Schleife durchgeführt wurden, und dann speichern wir die Ergebnisse in unserem Speicher-Array und geben es dann schließlich an das Ende. Also noch einmal möchte ich, dass Sie sich diesen Code hier ansehen und dann dieses Video anhalten und sich ein paar Minuten Zeit nehmen, um darüber nachzudenken, was die Basisfälle in Bezug auf Integer-Wert zurückgeben sollten, den Stapel einmal diese Fälle sind Treffer. Also mach weiter und pausiere das Video noch einmal und komm zurück, wenn du bereit bist. Okay, ich hoffe, du hast dir ein paar Minuten Zeit genommen und darüber nachgedacht. Und so werde ich hier nur auf die Antworten eingehen. Also schaut man sich zuerst diesen Basisfall genau hier an, wo der Rest kleiner als 0 ist. In diesem Fall sollten wir negative zurückgeben. Und lasst uns darüber nachdenken, warum. Nun, da wir die Werte unserer Münzbezeichnungen vom aktuellen Restbetrag subtrahieren . Wenn wir zu einem Ort kommen, wo der Rest kleiner als 0 ist, ist es eine negative Zahl. Wir haben offensichtlich eine Sequenz von Münzwerten gewählt, so dass, wenn wir sie zusammen hinzufügen , wir haben nicht 0,11$, oder? Wenn wir zum Beispiel den Fall betrachten, in dem wir unsere anfängliche Menge von 11 nehmen und dann fünf subtrahieren und wir sechs bekommen. Mach das nochmal. Sechs minus fünf ist eins. Und das machen wir wieder. Eins minus fünf ist negativ vier. Und das offensichtlich, richtig, drei Münzen mit einem Wert von fünf Sätzen jeweils gleich 0,15$. Das ist viel mehr als unser anfänglicher Betrag. Das ist also der Fall, dass wir hier treffen, wobei der Rest kleiner als 0 ist. Und wir wissen aus unserer Problematik, dass, wenn wir hier auf eine Folge von Münzen stoßen , die nicht der Menge an Geld entspricht, nach der wir suchen, dann sollten wir einfach negative zurückgeben. Das deckt den Basisfall ab. Der zweite ist genau hier. Und hier ist der Rest gleich 0. Und das ist der Fall, nach dem wir wirklich in diesem Problem suchen , denn wenn wir zu dieser Situation kommen, haben wir in diesem Szenario eine Folge von Münzen gefunden, die gleich sind, 0,11$, richtig? Wenn wir all dieses rekursive Zeug erkunden, wenn wir die Kombination der Einnahme von 11 minus fünf untersuchen, dann ist das Subtrahieren von fünf wieder, also sechs minus fünf ist eins. Und dann nehmen wir unseren Rest von eins und subtrahieren eins davon, bekommen wir 0. Und im Rückblick wählten wir zwei Münzen von jeweils 0,05$ plus eine Münze von einem Sinn, das entspricht insgesamt 0,11$. Deshalb ist unser Rest gleich 0. Und in diesem Fall werden wir 0 zurückgeben. Das liegt daran, dass wir hier zu unserer for-Schleife kommen, wenn wir durch unser Münzarray iterieren. Und wir nennen diese Münzwechselfunktion wieder. Wann immer es zurückkehrt, speichern wir den Wert in diesem variablen Ergebnis. Und dann haben wir diese if-Aussage hier. Und wir schauen zu sehen, ob das Ergebnis größer oder gleich 0 ist und das Ergebnis kleiner ist als dieser Min-Wert hier , der anfänglich auf einige riesige max ganze Zahlen gesetzt ist, so etwas wie, wissen Sie, eine 100 Milliarden oder eine Billionen oder So etwas. Irgendeine riesige Zahl. Bei diesem if Anweisung geht, dann ändern wir den Wert von R min Variable auf gleiches Ergebnis plus eins. Also als Beispiel, direkt durch all diese Rekursion, da wir ständig Münzwerte von diesem Restbetrag subtrahieren. Irgendwann kommen wir zu einer Situation, in der der Rest gleich eins ist. Und in diesem Fall werden wir diese for-Schleife noch einmal durchmachen. Ich werde rekursiv diese Münzwechselfunktion mit jedem unserer Münzwerte aufrufen. Und wenn wir also unseren Rest von eins nehmen und davon den Wert eins subtrahieren, erhalten wir 0. Und in diesem Fall wird dieser Basisfall getroffen. Der Rest wird 0 sein, wir geben 0 zurück. Das wird das Ergebnis sein. Das Ergebnis ist offensichtlich größer oder gleich 0. Und es ist weniger als unser riesiger initialisierter Wert von Männern. Also, wenn wir dann setzen wir min auf 0 plus eins, das ist nur eins. Und dann rufen wir diese Funktion erneut durch eine andere Iteration unserer for-Schleife auf, wo wir den Rest nehmen, der in diesem Szenario gleich eins ist, und wir subtrahieren davon, der nächste Münzwert von 21 minus zwei ist negativ. Das wird also diesen Basisfall treffen. Und wenn diese Funktion zurückkehrt, ist das Ergebnis negativ. Offensichtlich negativ ist nicht größer oder gleich 0. Und so wird diese if-Anweisung einfach überspringen. Dann wiederholt sich diese for-Schleife noch einmal. Wir nehmen unseren Rest, der den Wert von eins hat, und wir subtrahieren daraus den Wert fünf, der Ihnen negative vier gibt. Und noch einmal, die trifft diesen Basisfall, es gibt einen negativen zurück. If-Anweisung wird dann überspringen und dann ist diese for-Schleife abgeschlossen. Also jetzt an diesem Punkt ist der Wert von min nur eins. Und plötzlich traf d's little this if Aussage hier unten. Und wir schauen zu sehen, ob die min Variable immer noch diesen riesigen max Integer-Wert hat. In diesem Fall gingen wir, um den Index von einem in unserem Speicherarray so zu setzen , dass er dem negativen entspricht. Und das würde bedeuten, dass es keine Möglichkeit gibt, 0,01 Dollar aus den Münzbezeichnungen zu schaffen, die wir haben. Aber natürlich, da eine der Münzbezeichnungen haben wir eine RA ist gleich 100%. Deshalb hat diese min Variable den Wert eins darin gespeichert. Also diese if-Anweisung wird nicht getroffen. Und so lassen Sie mich zu dieser anderen Aussage gehen. Und so speichern wir dann im Index eins in unserem Speicherarray den Wert von eins. Und das bedeutet, dass die wenigste Anzahl von Münzen, die wir brauchen, um $0,01 zu schaffen , nur eine Münze ist, weil wir eine Münze im Wert von $0,01 haben. Und deshalb wird dieser Wert in unserem Array dort gespeichert. Also lass mich hier rauf gehen, das in unsere Memory-Arrays platzieren. Also setzen wir in Index eins den Wert eins ein. Nun lassen Sie uns durch das Szenario Krieg Rest ist derzeit gleich zwei. Also versuchen wir, die wenigste Anzahl von Münzen zu finden, die wir bis zu $0,02 addieren müssen. Und so wiederholen wir noch einmal diesen Prozess und die for-Schleife, wir nehmen den Wert im Rest, der zwei ist, und wir subtrahieren von diesem den Wert jeder unserer Münzbezeichnungen. Also machen wir zwei minus eins ist eins, und diese Subtraktion passiert hier unten, genau, wo wir diese Münzänderung rekursiv wieder nennen, und wir machen RAM minus Münzen. Also zwei minus eins ist eins. Also rufen wir den Münzwechsel wieder an. Und jetzt ist RAM gleich eins. Und jetzt ist dies, wo dieser andere Basis-Fall trifft, wo wir in unser Array schauen und RAM ist jetzt gleich eins. Und so haben wir in RA geschaut und wir sagen, oh, der Wert eines ist immer hier zu beginnen. Also schnappen wir uns das einfach und geben es zurück. Und so wird man dann in unsere Ergebnisvariable gespeichert. Wir gehen diese if-Anweisung durch. Offensichtlich geht es vorbei, weil das Ergebnis größer oder gleich 0 ist und es sicherlich kleiner ist als unsere initialisierten max ganzzahligen Werte, die in men gespeichert sind. Und jetzt ändern wir den Wert von min, richtig? Ergebnis ist jetzt 11 plus eins ist zwei, so dass min der Wert zwei wird. Und bis zu diesem Punkt bedeutet das, dass wir jetzt mindestens zwei Münzen brauchen, um 0,02$ zu schaffen, oder? Nachdem diese Münzwechselfunktion zurückkehrt, sind wir zurück zu ram gleich zwei. Und so Nin gleich zwei bedeutet, wie ich schon sagte, wir müssen so weit münzen, um 0,02$ zu schaffen, und das wären nur zwei Kopien unserer 0,01 Dollar Münze. Aber natürlich haben wir noch zwei weitere Münzbezeichnungen zu betrachten. Und so könnte Nin noch weniger werden Im Grunde könnte es nur eine sein, die passieren würde, wenn wir, wie wir diese anderen Konfessionen hier erforschen, wenn wir feststellen, dass es möglich ist, $0.02 mit nur einer Münze zu schaffen, dann ist es, wo Sie ändern Sie den Wert des Menschen, um eins zu werden. Und Sie werden feststellen, dass dies der Fall ist, wenn wir mit dieser for-Schleife hier fortfahren. Also gehen wir durch eine andere Iteration, richtig? Wir nehmen RAM wünschte seinen Rücken, um den Wert zwei, und wir gehen zu unseren nächsten Münzen, Dominanz, die hat auch den Wert zwei. Und wir subtrahieren diese wieder direkt durch einen anderen rekursiven Funktionsaufruf zwei minus zwei ist 0. Und in diesem Fall haben wir diesen Basisfall getroffen, RAM ist gleich 0 und wir geben 0 zurück. Sobald diese Münzwechselfunktion zurückkehrt, ist das Ergebnis jetzt 0. Kommen Sie zu diesem if Aussage. Offensichtlich ist das Ergebnis größer als gleich 0 und es ist auch kleiner als unser aktueller Wert von name , der auf zwei gesetzt ist. Also jetzt setzen wir den Wert von min auf 0 plus eins gleich eins zurück. Also, wie ich gerade sagte, wenn wir in der Lage sind, eine andere Möglichkeit zu finden, Münzen zu kombinieren, um $0,02 mit weniger als zwei Münzen zu schaffen. Dann werden wir den Wert der Männer ändern. Und so ist jetzt Manie eins, weil wir herausgefunden haben, dass es möglich ist , $0.02 mit nur einer Münze zu schaffen. Wir müssen uns noch eine Nominierung ansehen. Also wird sich diese for-Schleife noch einmal wiederholen. Also nehmen wir Rand, das ist zwei, wir subtrahieren von dem Wert von fünf, das wird negativ drei sein. Das ist also, wo wir diesen ersten Basisfall getroffen haben, richtig? Ran ist kleiner als 0, also geben wir negative ein zurück. Das Ergebnis speichert nun den negativen Wert. Wenn Anweisungen übersprungen, und dann ist diese for-Schleife jetzt getan. Und so lassen Sie mich zu dieser If-Aussage hier unten kommen. Und Männer sind nicht mehr gleich unserem initialisierten Wert von max int. Es wurde auf eins eingestellt. Und so kommen wir wieder hier runter. Und wir sagten, der zweite Index im Speicher gleich eins. Also kommen wir wieder hierher. Und so wird dieser Wert in unserem Speicher-Array eins, was wiederum bedeutet, dass die wenigste Anzahl von Münzen, die wir brauchen, um $0.02 zu erstellen , einfach eine Münze ist, weil wir eine Münze haben, die gleich $0.02 ist. Und so wie wir ständig Backups durch all diese rekursiven Funktionsaufrufe zurückgeben, werden wir die Werte in jedem dieser Indizes und unserem Speicher-Array gespeichert füllen . Also, dass wir am Ende und am letzten Index den Wert drei hier gespeichert haben, richtig? Dies ist die Antwort auf dieses Hauptproblem, dass wir nach drei Münzen suchen die $0,11 entsprechen und dann geben wir es einfach ganz am Ende zurück. Und so kann ich dann genauso wenig Demonstration hierher zurück zu meinem Terminal kommen und einfach diesen Code kompilieren, und dann kann ich ihn ausführen. Und natürlich wird dies unseren Algorithmus mit diesem speziellen Szenario im Hinterkopf mit diesen Münzbezeichnungen ausführen unseren Algorithmus mit diesem speziellen Szenario im Hinterkopf und diese 11 sitzen auf dem Berg, zu dem wir addieren wollen. Also gehe ich weiter und drücke die Eingabetaste. Und dann gehst du hin. Unsere Antwort ist, die wenigsten Münzen, die wir schaffen müssen. $0,11 ist einfach drei Münzen. Und wieder einmal war ich in der Lage, all diese Berechnungen extrem schnell zu machen , denn obwohl wir im Wesentlichen versuchen, jede mögliche Kombination unserer Münzen hier zu betrachten, die bis zu 0,11$ summieren kann. Und dann dieser Kombinationen, finden Sie die wenigste Anzahl von Münzen, da wir die Ergebnisse einiger dieser kleineren Unterprobleme speichern, IE, die wenigste Anzahl von Münzen benötigt, um kleinere Geldbeträge zu erstellen. Da wir diese Werte auf dem Weg speichern, müssen wir nicht alle Kombinationen dieser Münzen in ihrer Gesamtheit erforschen, oder? Waren in der Lage, eine Sequenz oder Kombination von Münzen zu erkunden. Und dann, wenn wir diesen Pfad untersuchen, sind wir in der Lage, auf dem Weg in unser Speicher-Array zu schauen, um zu sehen, ob wir bereits einige dieser Ergebnisse in früheren Funktionsaufrufen berechnet haben . Und in diesen Fällen hören wir einfach auf, nehmen diesen Wert und dann müssen wir diese bestimmte Reihenfolge von Münzen nicht weiter erforschen . Und so wird dies eine enorme Menge an Berechnung und Zeit sparen, besonders wenn Sie viele verschiedene Münzbezeichnungen haben. Und die Menge, die Sie versuchen, addieren zu wollen, ist sehr groß. Also hoffe ich, dass all das Sinn gemacht hat. Auch hier weiß ich, dass dieses spezielle Problem ziemlich schwierig ist, sich durchzuarbeiten. Wenn Sie also ein wenig kämpfen, um zu verstehen, was hier vor sich ging, empfehle ich Ihnen, dieses Video vielleicht ein paar Mal anzusehen, insbesondere den Code anzusehen und zu versuchen, sich selbst durchzugehen. Ich habe jede der Codedateien, die in den Videos in diesem Kurs gezeigt werden, im Projektbereich dieses Kurses veröffentlicht. Also sind Sie mehr als willkommen, dorthin zu gehen und die Dateien herunterzuladen und einen Blick zu werfen, führen Sie sie aus, wenn Sie Änderungen an Druckanweisungen vornehmen möchten, was auch immer Sie tun müssen, um wirklich zu verstehen, wie dieses Zeug funktioniert. Also danke für das Ansehen und ich sehe Sie im letzten Video kommen als nächstes, nur um einige Dinge zu packen. 6. Wir kommen zum Ende: Ordnung, an dieser Stelle haben Sie den Kurs abgeschlossen. Ich hoffe, Sie können viel davon lernen und erzählen, Ihnen etwas Übung bei der Lösung von Problemen mit der dynamischen Programmierung geben. Sie können einen Blick auf das Kursprojekt unten werfen. Und so, dass gesagt, ich danke Ihnen so sehr, dass Sie diesen Kurs gesehen haben. Ich weiß jedes Feedback zu schätzen, das Sie haben können. Ich M Scott Reese wieder. Ich versuche, alle zwei Wochen einen neuen Kurs zu veröffentlichen. Und bitte schauen Sie sich auch die anderen Kurse an, die auf Geschicklichkeitsbeteiligung haben. Oder sie haben viele Inhalte zu Informatik-Lead-Themen wie diesen veröffentlicht, sowie andere Kurse zu Handels- und Anlagethemen. Und vergessen Sie nicht, mir auch zu folgen und Fähigkeiten teilen, so dass Sie jedes Mal benachrichtigt werden, wenn ich den neuen Kurs herauskomme. Also nochmals vielen Dank für das Anschauen und glückliche Programmieren.