Dynamische Programmierung: Java, JavaScript und Python

1. Einführung: Hallo an alle und willkommen zu diesem neuen Kurs, bei dem es um dynamische Programmierung geht. Mein Name ist 100 Einheiten und ich werde Ihr Lehrer während dieses Kurses sein. Zunächst einmal möchte ich Ihnen das Schema mit dem Umriss dieses Kurses zeigen. Wir werden mit der Definition dynamischer Programmierung beginnen. Und wir werden über zwei der beliebtesten Techniken lernen , die normalerweise in diesem Thema verwendet werden. Die erste ist das Auswendiglernen, und die zweite ist die Tabellierung. Und wir werden über sie lernen, indem wir die Fibonacci-Sequenz verwenden. Wir werden dieses Problem mit drei Methoden lösen. Die erste ist die Verwendung der generativen Rekursion, die wir alle kennen. Und wir werden zum Auswendiglernen und Tabulieren übergehen. Und wir werden die Unterschiede zwischen ihnen sehen. Und wir werden lernen, wann und wo wir jeden von ihnen benutzen können. Danach werden wir einige der berühmtesten Übungen mit dynamischer Programmierung lösen . Das erste, was wir tun werden, ist zu versuchen, einen Baum zu bauen oder vielleicht eine Art Array oder eine 2D-Matrix dieses Problems. Danach werden wir versuchen, einen Pseudocode zu schreiben , der uns hilft, dieses Problem zu implementieren. Und schließlich werden wir tatsächlich mit drei Sprachen implementiert, Java, JavaScript und Python. also durch die Abschnitte gehen, Sie feststellen, dass wir in jedem Abschnitt ein Hauptproblem lösen werden. Und das Problem enthält die Erklärung des Problems neben dem Code oder der Beispielarbeit. Dann werden wir einen Pseudocode haben, der unsere Logik und Formeln erklärt. Und danach werden wir es mit den drei zuvor erwähnten Sprachen implementieren. Wir haben auch eine zusätzliche Funktion, die diese Website ist. Ich habe diese Website erstellt, damit Sie Ihren Code ausführen und getestet haben. Also hier haben wir einige Probleme, die wir lösen werden. Und Sie können voran gehen und eines der Probleme wählen. Versuchen Sie, es hier zu lösen, bevor Sie zurück zu der Video-Erklärung und Umsetzung, die wir haben und Diskurs. Das heißt im Grunde, das ist das Schema oder der Umriss unseres Kurses. Ich hoffe, es gefällt Ihnen und wir sehen uns im nächsten Abschnitt. 2. Anforderungen: Okay, bevor wir beginnen, gibt es eine Liste von Anforderungen, die Sie herunterladen müssen entsprechend der Sprache, die Sie verwenden werden. Zum Beispiel, wenn Sie Java verwenden, aber Sie müssen herunterladen, ist Eclipse oder eine Art von IDE, wo Sie Java ausführen können. Dann müssen Sie natürlich Java herunterladen. Sie gehen über zu Java SDK und sie nur irgendwie drücken und zustimmen und so kostenlosen Download. Und du erhältst deine neueste Version. Wenn Sie zum Beispiel Python verwenden , müssen Sie Python herunterladen. Und natürlich werde ich Visual Studio Code herunterladen, wo wir unseren Code mit Python und JavaScript ausführen werden. Schließlich werden wir für JavaScript Node.JS verwenden, um es auf unserem Server auszuführen. Dies sind also die Anforderungen, die Sie benötigen. Ich werde die Links im Beschreibungsabschnitt hinzufügen. Und ich hoffe, Sie haben diesen Kurs genossen. So sehen wir uns im nächsten Abschnitt. 3. Fibonacci-Sequenz: Alles klar, so hallo und willkommen. Und diese paar Videos, werden wir die Frage beantworten, was ist dynamische Programmierung? Also fangen wir mit etwas Einfaches an. Das ist die Fibonacci-Sequenz. Und die Fibonacci-Sequenz ist eigentlich eine Sequenz, in der jede Zahl die Summe ihrer beiden vorherigen Zahlen ist. Unsere Basisfälle sind also eigentlich die ersten beiden Zahlen, das ist 01. Dies sind also die ersten beiden Zahlen in der Fibonacci-Sequenz. Und der Rest von ihnen ist eigentlich die Summe der vorherigen Zahlen. Zum Beispiel, wenn ich diese Zahl bekomme, ist es 0 plus eins ist eins. Dann haben wir 1 plus 1, 2, 1, 2, 3, 2 plus 35, so weiter und so weiter. Das ist also die Fibonacci-Sequenz. Jetzt, wann immer wir es lösen wollen, geht unser erster Gedanke in die Rekursion. Da jedes Mal, wenn wir die Zahl an einer bestimmten Position berechnen möchten, müssen wir zu den vorherigen Zahlen zurückkehren. Also lassen Sie mich einfach die Indizes hier schreiben. Das ist also Index 0, 1, 2, 3, 4, 5, 6 und 7. Lassen Sie mich einfach einen Baum zeichnen, wo wir diese Zahlen repräsentieren werden. Nehmen wir an, ich möchte den Fibonacci von fünf berechnen. Also, um die Fibonacci von fünf zu berechnen, muss ich die Fibonacci von vier berechnen und dann die Fibonacci von drei und dann summieren sie zusammen. Nun, um dieses Fibonacci von vier zu bekommen, was ich eigentlich tun sollte, ist, die Fibonacci von drei und dann die Fibonacci von zwei zu berechnen . Und das Gleiche gilt auch hier. Also möchte ich f von 2 und f von 1 bekommen. Und hier treffen wir uns, um f von 1 und f von 0 zu bekommen. Und denken Sie daran, dass f von 1 und f von z die Basisfälle sind. Und wann immer wir zu diesem Punkt kommen, sollten wir eigentlich nur diese beiden Werte zurückgeben, die wir hier haben. Also hier haben wir f von 1 auch und f von 0. Und das Gleiche gilt auch hier. Also werde ich nur diese Punkte schreiben. Also, das ist es im Grunde jetzt, wenn wir über die Zeitkomplexität dieses Algorithmus nachdenken, wird es eine exponentielle Form annehmen, da wir, wie wir sehen können , immer wieder die gleichen Zahlen berechnen. Also hier haben wir f von 2, 2, und hier haben wir f von 1, 1 und 1. Und Sie berechnen sie immer und immer wieder, wie wir sehen können. Unsere Lösung könnte also funktionieren, oder sie funktioniert tatsächlich für kleine Zahlen, aber es wird eine lange Zeit dauern, kann Sekunden, Minuten oder sogar Stunden dauern , um eine große Fibonacci-Sequenz zu berechnen. Also, wie absoluter Code könnte aussehen? Also lassen Sie mich einfach die Fibonacci schreiben und es sollte diesem Code gleich sein. Das erste, was wir tun werden, ist, unsere Basisfälle zu schreiben. Wenn n gleich 0 ist. Also, wenn n bei Index 0 ist, sollten wir nur diesen Wert zurückgeben, der 0 ist. Also werde ich in diesem Fall einfach 0 zurückgeben. Nun, wenn n gleich 1 ist, was wir als tatsächlich diesen Wert an einem bestimmten Index zurückgeben sollten, der tatsächlich eins ist. Also werde ich einfach einen zurückgeben. Jetzt können wir mit unserem Basisfall beginnen, oder es tut mir leid, mit unserer Rekursion. Was wir tatsächlich zurückgeben müssen, sind die beiden vorherigen Zahlen. Also, wenn wir Banaji von n sind, die gleich fünf ist, sollten wir zu Fibonacci von vier plus Fibonacci von drei vorgeben. Also, wie haben wir das gemacht? Wir haben einfach die Fibonacci-Funktion von n-minus-1 genannt. Und dann summieren wir es mit dem Fibonacci von n minus 2. Das war's also. Grundsätzlich ist dies für unseren Pseudocode. Nun, was ich tun werde, ist, den Geist Gottes zu nehmen und tatsächlich mit Java implementiert. Sie daran, dass wir Java nur verwenden, um die Zeitkomplexität in diesem Problem zu visualisieren und der Rest Ihrer Probleme wird in allen Sprachen, Java, JavaScript und Python dargestellt . Also, um das zu tun, lassen Sie mich einfach zu Eclipse gehen. Und was ich tun werde, ist, diesen Code hier zu schreiben. Also f n ist gleich 0. Ich werde tun, ist einfach 0 zurückzugeben. Nun, wenn n gleich eins ist, werde ich eins zurückgeben. Und wenn das nicht die Fälle sind, werde ich einfach zurückkehren. Also werde ich Fibonacci von n minus 1 plus Fibonacci von n minus zwei zurückgeben. Nun, danach werde ich gehen, es tut mir leid, ich habe hier vergessen. Nun, um dies zu testen, was ich tun werde, ist, eine Hauptfunktion zu erstellen und die Fibonacci einer bestimmten Nummer aufzurufen , drucken Sie die Fibonacci von 7 in diesem Fall aus. Wie Sie sehen können, wenn ich voran gehe und diesen Code direkt hier ausführe. Aber ich werde tatsächlich als P Nummer 13 bekommen. Und wenn Sie hier zurück gehen, können wir sehen, dass diese Fibonacci dieser spezifischen und X7 ist eigentlich 13. Unser Code funktioniert also korrekt. Aber wenn ich jetzt zurückgehe und versuchen wir die Fibonacci 50. Und wenn wir diesen Code Dienstag ausführen, einige Zeit ausgeführt werden, da wir rekursive Aufrufe haben, bei denen wir den gleichen Code ausführen oder die gleiche Funktion immer und immer wieder ausführen werden. Und es wird in diesem Fall vielleicht Sekunden oder vielleicht Minuten dauern. Also müssen wir einen besseren Weg haben, um nur diese Fibonacci-Sequenzen oder die Ergebnisse in diesem Fall zu bekommen. Und hier kommt in der dynamischen Programmierung. Wir haben also zwei Techniken, mit denen wir uns vorstellen werden. Die erste wird Memoisierung genannt, und die zweite wird Tabulation genannt. Und wir werden sie in den nächsten Videos präsentieren. So sehen wir uns dann. 4. Memoization: Also haben wir die Lösung gefunden, bei der wir Rekursion verwenden , um dieses Fibonacci-Problem zu lösen. Wir stoßen jedoch auf ein Problem wegen seiner zeitlichen Komplexität. Weil wir die gleiche Funktion ausführen oder die gleiche Funktion immer und immer wieder aufrufen. Also, wie gehen wir damit um? Hier kommt die dynamische Programmierung. Die erste Technik, die wir verwenden werden, heißt Memoisierung, die im Grunde nur die Werte speichern, die wir immer und immer wieder verwenden werden. Also, um das zu tun, anstatt nur f von 2 hier ein Mal und hier ein anderes Mal anzurufen. Aber wir gehen tatsächlich zu zwei, um dieses f von zwei zu lösen, wenn wir es zum ersten Mal sehen. Also wird unser Code auf diese Weise funktionieren. Wir rufen f von 5, 10 an. In diesem Fall wird es f von 4, 4, 3 nennen. Bevor Sie dies jedoch aufrufen, wird es diesen Weg gehen. Also ist der Fluss unseres Codes tatsächlich f von 5, 4, 3, und dann gehen wir den ganzen Weg bis 21, und wir sind gut und dann gehen wir den ganzen Weg zurück. Und wie Sie genau dort sehen können. Das ist also der Fluss unseres Codes. Was wir im Grunde getan haben, ist, all diese Werte jedes Mal oder das erste Mal zu speichern , wenn wir sie sehen. Und natürlich, wann immer wir sie wieder benutzen wollen, nehmen wir sie einfach aus unserem Gedächtnis. Also, um das zu tun, was ich in diesem Fall tatsächlich hinzufügen werde, ist eine Liste hier. Also lassen Sie mich das einfach löschen. Und ich werde die Parameter hier ändern, von N in N und einem Speicher. Und in diesem Fall, was wir eigentlich tun werden, ist, diesen Speicher zu nehmen und ihn später zu verwenden. Also, bevor wir all dies tun, werden wir überprüfen, ob die Fibonacci dieser Sequenz, und es ist tatsächlich in unserem Speicher gespeichert. Also, wie machen wir das? Lassen Sie mich einfach die Farbe ändern, damit wir die Veränderungen visualisieren können. Also, wenn der Speicher an dieser bestimmten Position und ist ungleich 0. Denken Sie nun daran, dass, wenn wir diesen Speicher erstellen , wir werden einfach Nullen setzen und Annette und FDA Position, die bei n ist, nicht gleich 0 ist. Was wir eigentlich tun werden, ist, es einfach so zurückzugeben, wie es ist. Also werden wir das Gedächtnis an dieser bestimmten Position zurückgeben. Und jetzt, wenn dies nicht der Fall ist, werden wir mit unserem Code wie zuvor fortfahren. Bevor wir diesen hier zurückgeben, müssen wir ihn jedoch in unserem Gedächtnis speichern. Denn denken Sie daran, dass Fibonacci n von dieser rechten Hüfte zurückgegeben wird. Also, um das zu tun, werde ich es einfach im Speicher bei n speichern und dann zurückkehren. Also lassen Sie mich das tun, indem Sie einfach all diese nehmen und sie einfach nur zum Hören drängen. Und was ich jetzt tun werde, ist, das zu nehmen und es hier zu platzieren. Lasst uns fortfahren. Also, anstatt dieses zurückzugeben, und ich werde tun, ist, sie einfach in unser Gedächtnis zu setzen und die eigentliche Erinnerung zurückzugeben. Also lassen Sie es mich einfach hier versuchen. Wir haben Speicher an n wird gleich diesem sein. Und natürlich, danach, werden wir einfach die Erinnerung an dieser bestimmten Position zurückgeben. Und das ist es jetzt, anstatt all diese Funktionen immer und immer wieder aufzurufen, wer wird nur überprüfen, ob sie in dieser Erinnerung sind? Wenn dies der Fall ist, werden wir sie einfach zurückgeben. Wenn dies nicht der Fall ist, werden wir sie berechnen und sie zum zweiten Mal im Speicher speichern , wir werden sie verwenden. Natürlich wird es richtig funktionieren. Nun gehen wir weiter und verwenden diesen Pseudocode und unser Java. Anstatt nur n zu bekommen, werde ich eine Erinnerung nehmen. Und natürlich, wenn wir hier den Nazi anrufen, sollten wir auch das Gedächtnis zurückgeben. Bevor wir es jedoch zurückgeben, sollten wir eigentlich nur einen Schwanz hinzufügen. Also Speicher bei n sollte gleich ds sein, und natürlich sollten wir auf Speicher passen. Und danach, Nun, nennen wir es Kriterien. Wie Sie sehen können, dauerte diese große Zahl eine Weile, um zu bekommen und sie ist negativ, weil wir ganze Zahlen verwendet haben. Also vielleicht werden wir jetzt 24 benutzen. Wir müssen es jedoch inkrementieren. Also werden wir ein neues Ende der Größe 21 haben, um innerhalb von Pseudocode zu verwenden. Nun, wenn wir zurückgehen und diesen Code ausführen, wie Sie sehen können, haben wir unser Ergebnis, das 67, 65 ist, was heißt, wir haben nicht viel Zeit wie zuvor in Anspruch genommen. Also lassen Sie mich jetzt nach der Nummer 30 suchen. Und wie wir sehen können, werden wir für unentdeckte, diese große Zahl und diese Zahl bekommen, die nicht nurmit der ursprünglichen rekursiven Funktion berechnethaben könnte mit der ursprünglichen rekursiven Funktion berechnet weil wir immer wieder dieselben exakten Funktionen aufrufen. Also, jetzt, was wir tun werden, ist, für eine sehr große Zahl wie 20000 versuchen. In diesem Fall, wenn wir voran gehen und es ausführen, können wir sehen, dass wir einen Fehler haben. Und dieser Fehler ist eigentlich StackOverflow. So wird unser Code schnell ausgeführt. Immer dann, wenn wir diese Funktionen immer und immer wieder aufrufen. Wenn wir also an einer bestimmten Position sind, wo wir 10 Tausend haben, werden wir zehntausend, neunhunderttausend, neunhundertneunundneunzig tausend, neunhundertachtundneunzig den ganzen Weg bis zum letzten, der bei 0 ist nennen neunhundertneunundneunzig tausend, . Also alle diese einen Rückruf Funktionen oder Callback SysML werden oder die oder nur in einem Stapel gespeichert. Und unsere Mitarbeiter nehmen vielleicht nicht alle diese oder passen all diese zusammen. Also, was wir tun werden, ist eine andere Technik zu verwenden, die Tabulation genannt wird. Und es ist auch eine dynamische Programmiertechnik, und wir werden es im nächsten Video sehen. 5. Tabulation: Okay, im letzten Video verwenden wir Memoisierung, um dieses Fibonacci-Problem zu lösen. Wir stoßen jedoch auf ein Problem, bei dem wir einen Stapelüberlauffehler hatten , weil wir zu viele Return-Anweisungen, Callbacks verwendet haben und wir alle in unserem Stack speichern und es konnte nicht passen. Also jetzt, was wir tun werden, ist die Tabellarisierung zu verwenden, um dieses Fibonacci-Problem zu lösen. Nun, wenn wir wissen, dass wir dieses f von fünf bekommen müssen, und um dieses f von 5 zu bekommen, müssen wir f von vier, f von 2 und f von eins bekommen . Es macht also Sinn, alle diese vorher zu lösen und sie einfach in einer Art Array-Liste oder so etwas zu speichern. Und dann einfach f von 5 zurückgeben. Also, was wir tun werden, ist von unten bis zum letzten Element zu beginnen. Und dies wird Tabulation genannt, die im Grunde dynamische Programmierung von Bottom-up ist. Und eigentlich nannte es das, weil wir es von unten bauen werden, eins nach 12, predigen unseren Zweck. Was wir also tatsächlich tun werden, ist, von 0 zu beginnen, unsere Funktion zu füllen oder unsere Ruhe zu durchlaufen und dann die letzte zurückzugeben, die wir brauchen. Also lassen Sie mich einfach all diesen Pseudocode löschen und nochmals mit Tabulation schreiben. Also werde ich tatsächlich tun, ist eine Funktion zu erstellen , und es wird eine iterative Funktion sein, also iteriert. Und in diesem Fall, was wir tun werden, ist eine Nummer zu haben und dass wir zurückkehren werden. Und in diesem Fall, was ich tun werde, ist, vielleicht eine Liste oder ein Array zu erstellen. Ich nenne es einfach eine Liste. Und es wird von Größe und plus eins sein. Und was wir eigentlich tun werden, ist, diese Liste mit diesen Werten hier zu füllen. Die Liste am spezifischen Index 0 sollte also gleich 0 sein. Und dann ist die Liste an einem bestimmten Index 1 gleich eins. Und dann können wir mit einer for-Schleife beginnen, die bei I gleich zwei den ganzen Weg bis n beginnt. Und jedes Mal in dieser Liste werden wir diesen spezifischen Index I speichern, den Wert der Liste bei i minus1 und das Plus bei I minus zwei. Also wird es ein großes O von n. Das ist also die Laufzeitkomplexität, weil wir alle Elemente von 0 bis n durchlaufen. Und wann immer wir das letzte Element erreichen, das sich an einem bestimmten Index befindet, und wir können es zurückgeben. Nachdem wir von all diesen fertig sind, wir einfach die Liste an der Position zurück. Und in diesem Fall, das ist es im Grunde jetzt, anstatt jedes Mal zurückzurufen, wenn wir das aufrufen müssen, zum Beispiel f bei 99, 99, können wir es einfach in unserer Liste speichern und schließlich bekommen, wann immer wir wollten. Also, lassen Sie mich in diesem Fall einfach diese Funktion hier mit Tabulation lesen. Also, anstatt all diese zu bekommen, was ich tun werde, ist, einfach eine Funktion zu erstellen, und es wird sein. Und anstatt diesen Parameter zu speichern, schreibe ich ihn einfach hier. Also werde ich die Ma'am hier von Größe n plus eins haben. Und in diesem Fall, was ich tun werde, ist, bei Mammoth 0 den Wert von 0 zu speichern, die Mutter von einem wird eins sein. Und jetzt können wir mit der for-Schleife beginnen, beginnend mit I gleich zwei den ganzen Weg. Und so eingeschlossen. Und natürlich werden wir es danach erhöhen. Was ich tun werde, ist, an dieser spezifischen Position bei i zu beginnen, dem Wert von m bei I minus 1, und fügen Sie ihm den Wert von n minus zwei in diesem Fall hinzu. Wie wir sehen können, wenn wir voran gehen und den Wert von und am Ende zurückgeben, was wir tatsächlich als den richtigen Wert dieser 20000 genau hier bekommen werden. Also, wenn ich diesen Code ausführe, bekomme ich 93637285. Und das ist die korrekte Fibonacci-Sequenz bei einem bestimmten Index von 20000. Also werden wir nur die StactOverflow-Probleme loswerden, die wir früher mit der Memoisierung hatten, und wir haben bereits Tabulation in dieser Lösung verwendet. Das heißt im Grunde für das Auswendiglernen und Tabulieren, was wir als nächstes tun werden, ist tatsächlich einige der berühmtesten dynamischen Programmierprobleme mit Memoisierung und Tabulation zu lösen . Also, was wir tun werden, ist, das Problem zu sehen, durchzulesen, und durch ein Beispiel eines versucht, es mit einer Hand zu lösen. Und danach werden wir einen Pseudo-Code erstellen oder einfach nur generieren. Und das wird uns helfen, es in unseren Sprachen, Java, JavaScript und Python zu implementieren . Das Schema unserer Kosten wird also wie folgt sein. Wir werden das Problem haben als den Pseudocode und dann die Implementierung. Also, das ist es, im Grunde, was dieses Video sehen Sie in der nächsten. 6. Mindestzahl um Betrachtung: In diesem Video werden wir eines der beliebtesten Beispiele durchlaufen , das normalerweise mit dynamischer Programmierung gelöst wird. Und das Problem geht so. Stellen Sie sich vor, Sie haben ein Geschäft und ein Kunde kommt rein und bestellt mit $60 Lebensmittel. Jetzt gibt er Ihnen eine $100 Rechnung und in diesem Fall werden Sie den Rest zurückgeben, das sind die $40. Also zum Beispiel, nehmen wir an, wir haben $100 und er kauft mit $60 und sollte ihn für zurückgeben. Nun, um dieses Problem willen, nehmen wir an, dass wir vier Arten von Glocken haben. Nehmen wir an, wir haben die $1 Rechnung. Ich schreibe sie hier. Also haben wir den Geruch und ist die $1, wir haben die Fünf-Dollar. Wir haben auch 10, und wir haben auch die 25. Das war's also. Also haben wir diese vier Arten von Glocken. Nun, wenn wir dieses Problem mit einem gierigen Algorithmus lösen wollen, versuchen wir es hier. Für dieses Beispiel haben wir eine Rendite von $40. Und in diesem Fall geht der gierige Algorithmus so. Das erste, was wir tun werden, ist, nach der größtmöglichen Rechnung zu suchen , mit der wir bezahlen können. Also in diesem Fall sollten wir $40 zurückgeben. Also lassen Sie mich es hier schreiben. Das sind also die $40, die wir zurückgeben sollten. Nun werden wir neben diesen vier Typen überprüfen, was ist die größte Menge, die wir aus diesen 40 extrahieren können? In diesem Fall haben wir die 25, also $40 minus 25. Also verwenden wir diese 11 Mal. Jetzt werden wir 15 haben. Und in diesem Fall haben wir auch eine 10, die kleiner als 15 ist, also 15, wir können sie extrahieren. Also verwenden wir diese 10 auch einmal. Und das wird uns mit fünf verlassen und dann entkommen. Schließlich haben wir fünf minus fünf, was gleich 0 ist. Um zu lösen, haben wir diese 5 auch einmal verwendet. Also landeten wir mit 25 plus 10 plus 5. Und in diesem Fall funktioniert dieser gierige Algorithmus tatsächlich und es gibt uns die optimale Lösung, die 25, 10 und 5$ Rechnungen verwendet . Stellen Sie sich vor, wir haben auch einen 20-Dollar-Schein, anstatt nur diese vier Typen zu haben. Lassen Sie mich das einfach löschen und versuchen Sie es erneut. Also, wenn ich hier eine weitere 20-Dollar-Scheine habe, und lasst uns den gierigen Algorithmus noch einmal versuchen. In diesem Fall haben wir jetzt bereits Dollar ausgefallen, die wir zurückgeben sollten. Und in diesem Fall wird der gierige Algorithmus genau wie zuvor funktionieren. Also werden wir für die meisten oder den größten Gürtel suchen , die wir aus diesem $40 extrahieren können, sollte weniger als diese $40 sein. Allerdings haben wir 25. Also sind wir gut. Wir werden mit 15 übrig bleiben. Und in diesem Fall, wenn wir mit $20 arbeiten wollen, können wir nicht, weil wir jetzt 15 haben. Wir müssen nach allem suchen, was gleich oder weniger als 15 ist. Und dieser Fall. Und so werden wir mit der gleichen, exakten Sache wie zuvor übrig bleiben. Und das ist eindeutig nicht die optimale Lösung. Die optimale Lösung besteht also darin, einfach die 20-Dollar-Scheine mal zwei zu verwenden. Also werden wir diese 20-Dollar-Scheine zweimal verwenden und wir werden die $40 bekommen , die wir brauchen, um an den Kunden zurückzukehren. Und in diesem Fall, wie Sie sehen können, der gierige Algorithmus nicht funktionieren. Es wird eigentlich nicht die optimale Lösung sein. Also werden wir stattdessen dynamische Programmierung verwenden. Lassen Sie mich das alles klar machen und wir werden ein weiteres Beispiel mit der dynamischen Programmiermethode durchlaufen . Richtig? Dies ist also ein weiteres Beispiel. Also haben wir $7, die wir zurückkehren sollten und wir haben die 1, 3 und 4 Gürtel. In diesem Fall. Diese Glocken bilden die, die wir vorher zeichnen. Also mach dir keine Sorgen darüber, passt sich mit ihnen an und melde dich an. Und in diesem Fall, was wir tun werden, ist ein Array oder eine Liste zu konstruieren. Und wir werden in einer Sekunde darüber reden. Aber zuerst lassen Sie mich einfach konstruieren und dieses Array wird hochdimensioniert sein, diese sieben plus eins. Also in diesem Fall werde ich nur sieben zeichnen. Alles klar hier, also 3, 4, 5, 6, 7. Und wie gesagt, einige plus eins, was es ein S-Fall ist, werden die Indizes 0, 1, 2, 3, 4 , 5, 6 und 7. Wie gesagt, haben wir acht Elemente in dieser Liste. Und was wir tun werden, ist, dass wir diese Glockenliste einzeln durchgehen und prüfen, ob eine mögliche Ergänzung in dieser rechten Hüfte möglich ist. Also, mit anderen Worten, was wir tun werden, ist zu überprüfen, zum Beispiel, wenn wir nur eine $1-Rechnung haben, was wird für diese hier passieren? Also in diesem Fall probieren wir es mit der $1 Rechnung aus. Also zum Beispiel, wenn wir diese $1 haben, aber wie viele Rechnungen müssen wir die 0 bilden? Und in diesem Fall brauchen wir keine gebaut, also schreiben wir einfach 0. Das ist also nur ein Basisfall. Nehmen wir an, wir müssen $1 zurückgeben. Wie viele $1 Rechnungen brauchen wir, um $1 zurückzugeben? Wir brauchen nur einen. Nun, gehen wir zur zweiten. Also zum Beispiel, wenn wir haben, müssen wir $2 zurückgeben. Wie viele $1 Rechnung tut es, um diese $2 zurückzugeben würde nur $1 Rechnungen. Also in diesem Fall, was wir sagen, dass wir brauchen, um $1 Rechnungen, um den Betrag zurückzugeben, der $2 ist. Um es also ein bisschen einfacher zu machen, sind dies die Menge und das sind einfach die minimale Anzahl von Rechnungen, die wir in diesem Fall zurückgeben sollten. Also, was wir hier sagen, ist, dass wir nur diese $1 Rechnung haben, und das ist die minimale Anzahl von $1 Rechnungen, die wir zurückgeben sollten, wenn wir diese Beträge haben wollen. Und nun, ohne all das durchzugehen, ist es dasselbe. Es ist ziemlich unkompliziert. Also brauchen wir $3 Rechnungen, um einen Betrag von drei zurückzugeben. Wir brauchen 4567. Das war's also. Im Grunde ist das, was wir brauchen. Lassen Sie mich das einfach löschen und lassen Sie uns damit fortfahren. Also in diesem Fall haben wir gerade die $1 hier durchgemacht. Also, was wir jetzt tun müssen, ist, nach den $3 zu suchen. Nehmen wir an, wir haben nicht nur den einen Diabetes. Wir haben die $1 sowie die $3. Aber in diesem Fall, was wir tun werden, ist, von Anfang an zu überprüfen. Also bei 0, wie viele Dollar-Scheine würden wir brauchen, um den 0 Betrag darzustellen? Wir brauchen keine. Nun, drei, wie viele $3 Rechnungen brauchen wir eine zu repräsentieren, die wir können, um eine mit $3 Rechnungen zu verhindern. Also gehen wir weiter zu zwei. In diesem Fall werden wir auch überprüfen und wir kamen, um zwei mit $3 Rechnungen zu präsentieren. Also werden wir zu diesen drei hier weitermachen. Und in diesem Fall fragen wir uns, wie viele $3 Rechnungen brauchen wir, um diesen $3 Betrag zu repräsentieren? Und die Antwort ist ziemlich unkompliziert. Wir brauchen keine drei, wir brauchen nur einen. Was wir hier sagen, ist, dass wir einen Drei-Dollar-Schein brauchen , um diesen Betrag zu repräsentieren. Und lasst uns zum vierten übergehen. Wie viele Bits brauchen wir, um diese vier zu repräsentieren? Und eigentlich müssen wir nur Rechnungen machen, das ist die $3 Rechnung plus die $1 Rechnung, um dies zu präsentieren. Also brauchen wir nicht für Gürtel, wir müssen nur und dieser Fall, es ist drei plus eins. Also, was machen wir? Wir stornieren dies und ersetzen auch hier. Und was den Fünf-Dollar betrifft, wie viele Bits brauchen wir, um den Betrag von 5 zu präsentieren? Und eigentlich brauchen wir drei Bits. Das ist die $3 Rechnung Plus ein Plus $1 Rechnung dann ist 3 Jahre genau hier. Was den Sex angeht, und wie viele Bits brauchen wir, um den Sex zu präsentieren? Wir brauchen eigentlich, nur um sich daran zu erinnern, dass drei, wir haben so viele, wie wir wollen. Anstatt es mit sechs zu repräsentieren, können wir es präsentieren, es repräsentiert mit zwei Dreien. In diesem Fall müssen wir nur jetzt zum siebten übergehen. Und in diesem Fall, was wir tun werden, ist, $3,3 Geburten zu verwenden, es tut mir leid. Und das sind $2 bis $3 Rechnungen und 1 $1 Rechnung. Und in diesem Fall werden wir mit so etwas enden. Wir haben 01212323. Nun, gehen wir zum letzten. Das ist, um die vierte zu repräsentieren. Also jetzt haben wir auch den $4 Gürtel. In diesem Fall haben wir die 1, 3 und 4 Dollarzahlen alle auf einmal und wir können sie alle in diesem Fall verwenden. Nun, was wir tun werden, ist, all diese bis zu den vier zu überspringen , weil wir keine der kleineren Menge darstellen können, 0, 1, 2 und 3. Und wir gehen den ganzen Weg bis zum vierten. Und in diesem Fall werden wir uns wie zuvor fragen, wie viele $4 Rechnungen müssen wir den Standard-Dollarbetrag darstellen? Und die Antwort ist eins. Wie viele dann? Für Dollar-Scheine oder Glocken müssen wir die Fünf präsentieren und die Antwort ist ziemlich einfach. Das heißt, wir brauchen $4 Rechnung plus $1 Rechnung. Und in diesem Fall gibt es zwei. Und das Gleiche gilt auch für das. Also hier haben wir zwei. Und natürlich werden wir es überprüfen. Also jetzt haben wir auch vier. Also vier plus eins plus eins ist gleich $6. Also in diesem Fall haben wir drei Gürtel verwendet, und das ist nicht optimal. Wir haben bereits eine Lösung, die mit zwei Riemen besser funktioniert. Das sind die 2 $3 Scheine. Wenn wir drei oder zwei haben, werden wir uns entscheiden, bei diesen beiden zu bleiben. Und schließlich, wenn wir uns nach dem letzten fragen, dann sind das die $7. In diesem Fall brauchen wir 4 $3. So kann es mit drei statt zu einem Satz von drei darstellen. Das war's also. Grundsätzlich sind wir so mit einer endlichen Antwort gekommen. Das heißt, wir können diesen Betrag mit nur zwei Glocken darstellen. Das ist es also für die Idee der Arbeit bis jetzt. Kleiner Pseudocode, um genau zu sehen, was passiert und wie wir darüber nachdenken können. Was haben wir gesagt, als wir drei oder vier waren? Wir haben gesagt, dass wir all diese überspringen können, 43, da sie kleiner als drei sind. Und lassen Sie uns das hier genau an den Glocken bezeichnen. Das sind also die Überzeugungen, die wir haben. Dies sind die Mindestanzahl und das ist der Betrag. Nun in diesem Fall, wenn die Glocke, so dass die Glocken sind 1, 3 und 4, so Glocke steht entweder für 12 oder drei. Und in diesem Fall, wenn diese Rechnung ist kleiner oder gleich zu dem Betrag, den wir, dass wir suchen. Was wir tun werden, ist, die Mindestzahl zu aktualisieren. Und wenn wir zu unserem Beispiel zurückkehren, können wir sehen, dass die Mindestzahl eines von zwei Dingen sein sollte. Das ist entweder dieses hier oder wir müssen es wie hier aktualisieren. Also, zum Beispiel 012, mussten wir sie nicht aktualisieren. Also schickten sie die gleichen oder die aktualisierten, das heißt 1, 2, 2 und 2, wie wir oben sehen können. Und in diesem Fall, wie haben wir diese aktualisierten Zahlen bekommen? Also, wenn wir uns die vier dieser Fall und diese vier Rechnungen ansehen, was wir tatsächlich getan haben, ist, dass wir diese vier von jedem der Beträge genommen haben, die wir. Also lassen Sie uns eine Sekunde darüber nachdenken. Also zum Beispiel, in diesem Fall, als wir diese fünf genau hier hatten, so haben wir $5 zurück. Und dieser Fall, was wir getan haben, ist, dass wir $4 von hier abziehen. Also haben wir 5 minus 4, also haben wir noch $1. Und dieser Fall, was wir tun werden, ist, den $1 Betrag genau hier in der Tabelle zu betrachten . Dies ist der $1 Betrag. Und in diesem Fall, was wir getan haben, ist nur, dass wir diese Mindestanzahl hier genommen und hinzugefügt haben, wie viele Rechnungen, wie viele $4 Rechnungen haben wir verwendet? Hier? Wir haben nur eine Rechnung benutzt. Das ist die $4 und wir müssen immer noch den Restbetrag zurückgeben, der $1 ist. In diesem Fall ist der Datensatz genau hier. Wir haben den hier. Das ist also der Betrag, den wir zurückgeben sollten. Also 1, 4 Dollar-Scheine plus 1 $1 Rechnung. Und in diesem Fall, die Antwort ist zwei, wie wir sehen können, das ist die Verwendung dieser Formel. Was wir danach tun werden, ist, dass wir dafür tatsächlich Pseudocode schreiben werden. Und dann werden wir es in Java implementieren. 7. Pseudo-Code: In Ordnung, jetzt, wo wir wirklich wissen, wie dieser Algorithmus funktioniert, und wir haben ein tatsächliches Beispiel durchlaufen. Wir kennen bereits die Idee dahinter. Lassen Sie uns nun versuchen, einen Pseudocode zu finden, der uns und unserem Code hilft , ein wenig zu schreiben. Also, wenn wir durch den Pseudocode gehen wollen, wie gesagt, hefty Bill ist weniger als der Betrag. In diesem Fall, was wir tun werden, ist, dass wir diese Mindestzahl hier aktualisieren werden. Also, was wir tun werden, ist, die ganze Liste für jeden dieser Gürtel zu durchlaufen . Also werden wir zwei for-Schleifen ineinander verschachtelt haben. Die erste ist wird sein, wird die Rechnungen Schleife sein, und die zweite wird die minimale Zahl sein, die wir jedes Mal aktualisieren werden, wenn wir durch Nummer passieren. Und in diesem Fall, was wir tun werden, ist, die Mindestzahl jedes Mal zu aktualisieren , wenn die Rechnung kleiner oder gleich dem Betrag ist. In diesem Fall hatten wir zum Beispiel für die Prüfung 4, 3 Rechnung. Wir haben bereits diese 012 und es gibt kleiner als drei, so dass wir sie nicht aktualisieren müssen. Wir beginnen mit der Menge, die größer oder gleich ist, dieser Gürtel genau hier. Also, wie gesagt, wir beginnen von hier den ganzen Weg, dass das Ende für jeden einzelnen der Gürtel genau hier. Also, was wir tun werden, ist, das Minimum zwischen zwei Dingen zu überprüfen. Wie gesagt, das Minimum zwischen dieser Zahl direkt hier und der tatsächlichen Zahl, die wir aktualisieren können. Was wir also tun müssen, ist, die Mindestzahl zu ändern. Die Mindestanzahl bei diesem bestimmten Betrag sollte aktualisiert werden. In diesem Fall wird es gleich 2 sein, eines der Dinge, die das Minimum zwischen ihnen ist. So wird es den Männern zwischen dem ersten und dem anderen gleich sein. Und wie gesagt, das erste, was ist der tatsächliche Betrag, den wir bereits haben. So wird es die minimale Anzahl des Betrags sein. Also ist es das gleiche wie vorher, oder wir brauchen einen kleineren. Was wir eigentlich tun, ist einfach zu überprüfen ob unsere neue Lösung besser ist als die andere. Also, wie wir hier gesagt haben, haben wir bereits diese Lösung 01234567, und sie sind mit dieser $1 Rechnung vertreten. Allerdings können wir für den Betrag von drei, zum Beispiel, es mit dem Betrag von 3, 0, dem einen Drei-Dollar-Schein darstellen . In diesem Fall entfernen wir diese drei Glocken und wir haben gerade einen Gürtel hinzugefügt ist $3. Und in diesem Fall ist es viel besser und effizienter, 13 Dollar-Scheine anstelle von 3 $1 Scheine zu verwenden. Also, was wir genau hier gemacht haben, ist, dass wir diesen Betrag drei genommen haben und einfach den S3-Gesetzentwurf von hier aus angegriffen haben. Also sind wir mit 0 übergegangen. Und in diesem Fall gingen wir den ganzen Weg zurück die Menge von 0 und wir betrachten diese minimale Anzahl und in diesem Fall 0. Und was wir eigentlich getan haben, ist, dass wir hier nur eine Pille benutzt haben. Und dann prüfen wir nach diesem 0 Betrag. Und wir haben hier tatsächlich eine 0 Glocke benutzt. Und das wird uns mit einem Glockenantigen verlassen. Deshalb haben wir hier drei. Und das Gleiche gilt für diese sechs hier. Was wir tatsächlich gemacht haben, ist, dass wir 2 $3 Rechnungen verwendet haben. Also wir dieses x hier, minus zwei mal drei, was gleich 0 ist. Also diese drei wird zweimal verwendet. Also benutze Tupel. Und wir gingen den ganzen Weg zurück zur minimalen Zahl oder zur Menge von 0 und wir überprüften die minimale Zahl, das ist eigentlich 0. Also wir, wir verwenden 02 minus 0 bis plus 0, es tut mir leid, ist gleich zwei. Also mussten wir ihn mit Glocke schlagen. Das ist also die eigentliche Arbeit durch. Wenn Sie also auf andere Weise darüber nachdenken wollen, für diese sechs Gürtel hier, was wir tatsächlich getan haben, ist, dass wir gesagt haben, dass es entweder 6 $1 Scheine sind oder etwas anderes, das diese drei benutzt, Dahlberg hier. Und in diesem Fall, was wir tatsächlich getan haben, ist, dass wir gerade diese $3 Rechnung genommen haben. Also sind es sechs minus drei. Und dieser Fall sind wir mit drei gelandet, richtig? Also, das haben wir nur eine Rechnung von hier benutzt. Und dann haben wir bei der Menge von drei überprüft, was genau hier ist. Wie viele, was ist die Mindestzahl in diesem Fall, dass wir mit einer Rückkehr alle Beträge am Ende müssen , die wir in diesem Fall für drei haben, wir können deutlich sehen, dass eine ist. Und so haben wir eine Glocke plus 1 bekommen, was gleich zwei Rechnungen ist. Das ist es also. Das ist eine allgemeine Idee. Wenn wir in diesem Fall Multiplikation haben, können wir dies direkt verwenden. Dies ist jedoch der eigentliche Weg. Lassen Sie mich diese löschen und wir sind gut. Wir können weitermachen. Also hier haben wir Mr. gut, es tut mir leid. Also hier haben wir Bill. Also, wenn die Rechnung ist weniger als Berg, wie wir bereits gesagt, wir müssen die minimale Zahl aktualisieren, die gleich sein wird entweder die gleiche oder die, fügen wir ein, wie gesagt. Es ist also eine Rechnung plus die Mindestzahl bei dem Betrag abzüglich der Rechnung. Das macht Sinn. Also lass es mich schreiben und dann erkläre ich es. Also Minimum zwischen dem tatsächlichen Betrag, den wir haben minus dem Gürtel, den wir polstern, dass wir haben. Also, das ist es im Grunde. Nun, wenn wir durch dieses Beispiel mit dieser Formel gehen wollen, Lassen Sie uns voran und tun es. Und natürlich werde ich nicht das ganze Beispiel durchgehen. Ich werde nur bestimmte Situationen nehmen. Nehmen wir zum Beispiel an, wir sind bei diesen fünf genau hier. Und wir haben nur die 3 $1 Scheine, die wir diese 51 repräsentieren können und diesen Fall, was wir tun werden. Also sind wir in diesem Stadium genau hier. Und wir werden den Prozess durchdenken. Wir haben diese $3 Scheine. Und in diesem Fall, was wir tun werden, ist, dass wir eins hinzufügen. Also ist es entweder das Minimum zwischen zwei Dingen, oder? Also ist es entweder dieser hier, das ist fünf. Du siehst es jetzt nicht, weil wir es einfach vorher entfernen, aber es ist genau hier. Und das sind fünf. Also sind es entweder fünf oder etwas anderes. Und die Verwendung dieser Formel ist eins plus der Mindestbetrag, Minimum zwischen Menge, Geist, Geist. Und in diesem Fall, was wir tun werden ist, also sind es entweder fünf oder eins, plus. Wir werden den ganzen Weg bis zur minimalen Anzahl der Menge gehen. In diesem Fall beträgt der Betrag fünf. Der Baumeister Amor ist drei. Also die minimale Zahl addiert 5 minus 3, die minimale Zahl bei zwei ist. In diesem Fall werden wir uns das ansehen. Und wie wir sehen können, haben wir die Mindestzahl in diesem Fall ist zwei. Also 1 plus 2, das ist 3. Das Minimum zwischen 53 ist also eigentlich drei. Und das ist, was wir hier haben, ist die Nummer drei. So können wir die $5 Rechnungen mit einem Drei-Dollar-Schein und $1 Rechnungen repräsentieren. Das war's also. So können wir diese Formel verwenden. Und wenn es zum letzten Mal ausprobiert wird, können wir es für diesen hier ausprobieren. Also davor hatten wir eine Drei hier. Und in diesem Fall, was wir eigentlich tun , ist , dass wir einen für Dollar-Schein hinzufügen werden. Lassen Sie mich das einfach löschen und fahren Sie fort. Also das Minimum zwischen zwei Dingen, der tatsächliche Betrag, den wir haben, oder die tatsächliche Mindestzahl, die wir bereits haben, oder wir müssen es aktualisieren, indem wir einen für Dollar-Schein hinzufügen. Also hat er einen. Plus. Wir gehen zur Mindestzahl bei der Menge, die 7 minus wL ist, was 4 ist. Also 7 minus 4 ist 3. Also gehen wir den ganzen Weg zu den drei hier. Wir werden uns die Mindestzahl ansehen. In diesem Fall ist es eins. Wir werden hier eins hinzufügen, also ist es das Minimum zwischen 32. Die Antwort ist also zwei. Das war's. Im Grunde ist dies, wie wir diesen Pseudocode verwenden können, um uns zu helfen, unseren Code jetzt zu schreiben, das ist der schwierigste Teil. Wir kommen nur mit dieser tatsächlichen Methode oder tatsächlichen Algorithmus oder Idee, die wir verwenden können, um das spezifische Problem zu lösen. Und mit dieser Methode konnten wir die optimalste Lösung finden. Im Gegensatz zu dem gierigen Algorithmus, den wir zuerst hatten. In diesem Fall, wie wir sagten, können wir diese $7 mit einem für Dollar-Scheine und 13 leichtgläubigen gebaut repräsentieren. Und dieser Fall, die Antwort ist zwei. Und damit das gesagt wird, ist dies das Ende des Pseudocodes hier. Und das nächste Video werden wir unsere Funktion mit Java implementieren. So sehen wir uns dann. 8. die Java-Implementierung: Okay, jetzt, da wir wissen, wie dieser Algorithmus genau funktioniert, und wir haben den Pseudocode geschrieben, der uns in unserem Code Walk-through helfen wird. Sofort. Wir können mit dem Codieren beginnen. Und eigentlich ist dies eines der wichtigsten, aber Sie sollten immer damit beginnen, so etwas. So können Sie Ihren Code schreiben oder Ihre Gedanken auf ein Stück Papier schreiben und vielleicht einige Dinge zeichnen. In diesem Fall zeichnen wir diese Liste und wir haben jedes Mal aktualisiert, wenn wir durch eine Glocke gehen. Also waren Sie ein Bedürfnis, mit einem Stift und Papier zu arbeiten und nicht nur all die Dinge in Ihrem Kopf zu visualisieren. Vor allem in der dynamischen Programmierung. Weil Visualisierung etwas oder Sie hatten Arbeiten in der Regel Folie einfachere Probleme. Bei einigen tiefen oder komplexen Problemen müssen Sie jedoch immer einen Stift und Papier verwenden. Und dieser Fall, gehen wir zu unserer Eclipse. Und in diesem Fall, was wir tun werden, ist, mit der Erstellung der Funktion zu beginnen. Also werde ich einfach, wir müssen nur Min die minimale Anzahl der Änderung zurückgeben, die eine ganze Zahl und eine leere Funktion Mindestzahl ist, in diesem Fall, was wir nehmen werden, die Menge, die zurückkehren wird, und es wird von N bezeichnet. Und wie viele oder die Art der Gürtel, die wir haben. In diesem Fall werden wir sie Glocken nennen. Also lasst uns es öffnen und wir werden mit dem umgesetzten beginnen. Das erste, was wir tun werden, ist, diese Liste zu erstellen, über die wir früher gesprochen haben, und das ist die minimale Zahl. Um es zu erstellen, erstelle ich einfach eine minimale Zahlenliste. Und es ist eigentlich widerspricht der, es ist die gleiche wie die Methode, oder? Vier, so intim anders. Und in diesem Fall wird dies Größe, die Anzahl oder die Menge von plus eins sein, wie wir gesagt haben. Und was wir tun werden, ist zunächst, es mit dem maximalen Wert zu füllen, den wir können. Also werden wir Arrays verwenden, die sich gefühlt haben. Und was wir tun werden, ist, diese Glocken mit Integer zu füllen, diesen Maximalwert. Dies ist, wie wir das Maximum von Integer-Wert hier speichern können. Und es scheint, dass wir Arrays importieren müssen. Also versuchen wir einfach Kontrastraum, drücken Sie die Eingabetaste, und es wird es einfach hier nehmen. Nun, dieser Bereich, gut, dass wir die ganze Zahl noch nicht zurückgegeben haben, aber wir können später damit umgehen. Aber im Moment werden wir uns daran erinnern , dass wir immer mit einer Menge von 0 beginnen wollen. Die Mindestzahl sollte also 0 sein. In diesem Fall, was wir tun werden, ist zu speichern und die, tut mir leid, es ist nicht doppelt ist die minimale Zahl hier. Und wir werden bei minimaler Zahl bei 0 beginnen, wir werden 0 speichern. Das ist also der erste Schritt. Jetzt werden wir alle tatsächlichen Daten durchlaufen. Also, was wir tun werden, ist durch den Bus zu gehen und in jedem, na ja, wir werden die Menge in diesem Fall passieren. Also int ich gleich 0 den ganzen Weg zu den Glocken, diese Länge und dann aktualisiert. Nun wird die zweite j gleich 0 sein. Dann ist J kleiner als die minimale Zahl. Es tut mir Leid. Also hier habe ich aus Versehen S hinzugefügt. Und jetzt sind wir gut. Also werden wir den ganzen Weg zu der minimalen Anzahl dieser Länge gehen und dann aktualisiert. Nun, was wir tun werden, ist zu überprüfen, ob die Glocke kleiner ist als der Betrag. Also, wie machst du das? Wir überprüfen einfach, ob die Glocken bei I weniger als etwas ist, was die Menge ist. Und in diesem Fall ist der Betrag tatsächlich der Index. Wie wir sehen können, ist der Betrag der Index dieser minimalen Zahl Array oder weniger. Also ist es, wenn es kleiner oder gleich diesem Betrag ist, werden wir etwas tun. Wir werden, wir werden nichts tun. In diesem Fall. Was wir tun werden, ist, den Unterschied zwischen dieser Menge und der Glocke zu nehmen. So können wir sagen, dass diese j ist der Betrag und Rechnungen bei ISB tatsächlichen Glocke. So wird der Unterschied j minus Gürtel Satire sein. Und wir wollen auch die Glocke in diesem Fall berechnen. Also werde ich mit vielleicht bezeichnet, es könnte die minimale Zahl in diesem Fall sein, wieder, ich habe gerade mit B bezeichnet und was wir tun werden, ist, dieses plus den Betrag oder die Mindestzahl hinzuzufügen. Dieser Unterschied. Also, was wir hier tatsächlich gemacht haben, ist, dass wir die Formel berechnet haben. Die Formel besagt, dass es die minimale Zahl ist. Und das Minimum. Dies ist die aktualisierte neue. Es wird eins plus das hier sein. Und wie wir das berechnet haben, ist, dass wir tatsächlich die minimale Anzahl und Menge minus Glocke genommen haben und es trifft ihn. Also 1 plus 1 plus die minimale Zahl. So ist dies die Mindestzahl bei Betrag abzüglich der Rechnung. Und wir berechnen den Unterschied nur in der früheren Zeile. In diesem Fall haben wir diejenige, die aktualisiert werden könnte. Also in diesem Fall, was wir tun werden, ist, zurückzukehren. Sagte nur, dass Gürtel an ich die Mathematik sein wird, aber Männer. Es ist also eines von zwei Dingen. Es ist die Tut mir Leid, die Mindestzahl bei I und J es tut mir leid. Und es wird eines von zwei Dingen sein. Es wird entweder das gleiche sein wie zuvor und, oder das BI, das wir gerade erstellt haben. Und in diesem Fall können wir diese Mindestanzahl leicht aktualisieren. Was wir also tatsächlich gemacht haben, ist, dass wir den Unterschied zwischen dem Betrag und der Rechnung genommen haben, wir berechneten, dass die Mindestzahl, wir berechnen einfach diese Formel und wir haben das hier. Dann haben wir gesagt, dass die Mindestzahl in diesem Betrag gleich der Mindestzahl bei diesem um oder eins plus der Mindestanzahl von Betrag 2012 sein sollte . Und dieser Fall, wir haben ihn hier, wir haben ihn aktualisiert. Es ist also entweder dasselbe oder derjenige, der TBI ist. Nun, was wir tun werden, ist zu überprüfen, ob die Mindestzahl am Ende oder bei Ja. Also bei der Menge ist nicht gleich Emax-Wert. Und du wirst dir in einer Sekunde sagen, warum. Wir werden die Mindestzahl bei zurückgeben und andernfalls minus eins zurückgeben. Also, was wir hier tatsächlich getan haben, ist, dass wir überprüft haben, können wir tatsächlich tun oder zurückgeben diesen Betrag. In diesem Fall, wenn wir diesen letzten Wert erhalten können, sollte nicht der maximale Wert sein. Es sollte eine natürliche Zahl sein. Und wenn das der Fall ist, wir einfach diese Nummer zurück. Und wenn nicht, werden wir minus1 zurückgeben, dasselbe, was wir nicht berechnen können oder wir können diese Rendite nicht mit dieser Rechnungsstrategie haben. Und ein Beispiel dafür ist, stellen Sie sich vor, dass wir eine $5 Scheine oder $5 Betrag zurückgeben müssen und wir haben nur 78 Doppel. In diesem Fall können wir nicht fünf zurückgeben, weil wir nur 78 haben. Deshalb wird dies immer maximaler Wert sein und wir können den Betrag nicht zurückgeben, also geben wir einfach minus eins zurück. Das ist also die Implementierung. Ich denke, es ist ziemlich unkompliziert nach all der Erklärung, die wir hier gemacht haben und durchlaufen. Und das war's für dieses Video. Wir sehen uns im nächsten. 9. Einführung von Minimum: Okay, Also in diesem Video werden wir unsere Funktion oder den Pseudocode implementieren , den wir früher mit JavaScript erstellt haben. Also, ohne weitere Umschweife, lasst uns einfach direkt hineingehen. Das erste, was ich tun werde, ist, den Funktionsnamen bei minimaler Änderung zu erstellen. Und in diesem Fall wird es nehmen und Rechnungen als Parameter. Lass es uns öffnen. Und in diesem Fall, was wir tun werden, ist ein Array in JavaScript zu erstellen. können wir tun. Nennen wir es. Nennen wir es. Eigentlich die Menge. Und was wir nicht tun wollen, ist, diesen Betrag zu nehmen. Und natürlich werden wir das alles in ein bisschen durchmachen. Aber im Moment, was wir tun werden, ist es als ein Array von einem Plus 1 zu erstellen. Und wir werden es mit Unendlichkeit füllen. Also, das ist es, im Grunde so, wie wir ein Array in JavaScript erstellen können. Nun, was wir tun werden, ist, diesen Betrag in den ersten zu aktualisieren , sollte gleich 0 sein. Wenn wir also zu diesem zurückgehen, können wir sehen, dass dieser Betrag gleich 0 sein sollte. Eigentlich, nennen wir es minimale Zahlen, da wir das hier gemacht haben, minimale Zahl. Also werden wir nur, ich würde die Mindestzahl hören. Das Gleiche gilt hier. Nun, was wir tun werden, ist, unsere for-Schleife zu erstellen. Das erste, was wir schaffen werden, ist die for-Schleife für die Glocken. Was wir also tun werden, ist zu erschaffen, bauen und Glocken, Glocken und dann zu öffnen. Nun, die zweite wird für die tatsächliche Mindestzahl sein. Und wir werden diese Indizes nach Menge bezeichnen, wie wir hier gesagt haben. Also werden wir es hier für das Labor schaffen. Betrag gleich 0, dann sollte der Betrag kleiner als die Zahl, minimale Zahl dieser Länge sein. Und dann werden wir natürlich den Betrag erhöhen. Jetzt öffnen wir es und jetzt können wir mit unserem eigentlichen Code beginnen. Wir werden einfach den Pseudocode schreiben, den wir zuvor geschrieben haben. Es heißt also, dass, wenn der Betrag größer oder gleich der Rechnung ist, wir etwas tun müssen. In diesem Fall, was wir tun werden, ist, die minimale Zahl zu aktualisieren, die gleich sein wird, sollte auf dem Betrag gleich dem Minimum zwischen zwei Dingen sein. Also werden wir Methodenmänner verwenden. Und dieses Minimum wird die Anzahl der Mindestanzahl des Betrags und die Mindestanzahl des Betrags minus der Rechnung sein. Was wir jetzt tun werden, natürlich müssen wir hier eins hinzufügen. Es ist also die minimale Anzahl von Betrag minus p plus 1. Und in diesem Fall sind wir tatsächlich mit dieser Funktion fertig. So können wir es mit JavaScript mit diesem Pseudocode implementieren , den wir früher erstellt haben, nur das Wichtige verwenden, um das Minimum zwischen diesen beiden Dingen zu nehmen. Und natürlich füllen wir es mit Unendlichkeit aus. Und vergessen Sie nicht, das erste mit 0 zu füllen, da es sich hier um den Basisfall handelt. Nun, was wir tun werden, ist, diese einfach hier zurückzugeben. Denken Sie also daran, dass, wenn diese Funktion ordnungsgemäß funktioniert, die letzte aktualisiert werden sollte. Aber manchmal haben wir vielleicht die Unendlichkeit am Ende. Und in diesem Fall, wenn Sie Unendlichkeit haben, bedeutet das, dass wir das Problem nicht gelöst haben, es gibt keine richtige Lösung. Lassen Sie mich Ihnen also ein Beispiel für solche Dinge nennen, die annehmen, wir haben den Fünf-Dollar zu vertreten, und wir haben auch 678. In diesem Fall gibt es keine richtige Lösung und diese letzte Unendlichkeit wird nicht aktualisiert, da $5 nicht mit 67 oder entweder $8 Rechnungen dargestellt werden können. Also, was wir tun werden, ist zu überprüfen, ob diese letzte gleich Unendlichkeit ist, wir werden minus1 zurückgeben. Andernfalls werden wir die tatsächliche Mindestzahl zurückgeben, die wir erhalten haben. Also, jetzt, wenn wir das tatsächlich zurückgeben, lassen Sie mich es einfach hier zurückgeben, damit die Mindestanzahl bei zurückgegeben wird, und was wir getan haben, um eine einfach die letzte in der Liste zu bekommen. Das ist also die Liste, die wir 0, 1, 2, 1, 1, 2, 2, 2, 2 bekommen werden. Und wir werden die Mindestzahl bekommen. Nun, um es klarer zu machen, werde ich zuerst die ganze Liste zurückgeben und dann werden wir es besprechen. Die Variable n ist also gleich den tatsächlichen Daten hier, die sieben sind. Und der letzte wäre 1, 3, 4, also und gleich sieben. Und die Liste wird gleich der Liste 134 sein. Und in diesem Fall, was wir tun werden, ist, diese minimale Änderungsfunktion mit einem und Rechnungen zu nennen . Und natürlich werden wir uns einloggen. Also console.log und Glück diese Funktion. Jetzt, wenn wir wieder hierher gehen. Und gehen wir zu JavaScript, dynamische Programmierung. Und was wir tun werden, ist, einfach Knotenmänner zu verwenden, diesen JS zu ändern und wir werden 0, 1, 2, 1, 1, 2, 2, 2, was genau das gleiche ist, was wir früher manuell generiert haben. Um jetzt zu tun, ist, den letzten zurückzugeben, der die Mindestzahl bei verwendet. Und jetzt, wenn wir wieder zurück und Grand gehen, werden wir zwei als die minimale Anzahl von Änderungen, die wir brauchen, um eine bestimmte Zahl zu präsentieren. Wenn wir das jedoch zum Beispiel nicht haben. Angenommen, wir haben fünf. In diesem Fall. Angenommen, wir haben 678 als Gürtel. Was wir bekommen werden, ist eigentlich Unendlichkeit und das ist keine richtige Antwort. Wir müssen minus eins zurückkehren. In diesem Fall müssen wir einfach überprüfen, ob die Mindestzahl bei n gleich unendlich ist. Das ist jetzt der Fall. Wir werden es auf minus 1 aktualisieren. Es gibt also mehrere Möglichkeiten. Zum Beispiel, eine Möglichkeit, so zu tun, als ob diese minimale Zahl gleich unendlich ist, aber wir tun es nicht, einfach zurückzukehren oder zu aktualisieren. Also, wenn es gleich unendlich ist, werden wir, es tut mir leid, wir müssen die Klammern hinzufügen, so dass die Mindestzahl bei n gleich unendlich ist. Wir werden es in minus 1 aktualisieren. Wenn wir jetzt zurückgehen und „Refresh“ drücken, bekommen wir minus 17 f Unendlichkeit. Eine andere Möglichkeit, dies zu tun, besteht darin, einfach neben der return-Anweisung zu überprüfen. Um das zu tun, überprüfen wir einfach, ob diese minimale Zahl gleich unendlich ist. Wenn das der Fall ist, müssen wir etwas tun. Und um das zu tun, schreiben wir einfach dieses Fragezeichen und dann haben wir zwei Möglichkeiten. Diese Aussage ist also zufrieden. Die erste Option wird sein, also sieht es ungefähr so aus. Also, wenn diese Gleichung erfüllt ist, wenn sie wahr ist, werden wir diese Option erhalten. Sonst kriegen wir den zweiten. Also, wenn das wahr ist, aber wir werden tun, ist minus1 zurückzugeben. Andernfalls werden wir die Mindestzahl bei Penn zurückgeben. Und lasst es uns nochmal überprüfen. Wenn wir zurückgehen und wieder rennen, bekommen wir Minus1 wie zuvor. Nun, zum Beispiel, wenn wir das hier als Bräune haben, und gehen wir zurück, führen Sie es nochmal aus. Und natürlich sollte es nicht sein, sollte zum Beispiel ein Vielfaches von sechs sein. Nun, wenn wir zurückgehen und rennen, werden wir zwei als minimale Anzahl von Änderungen bekommen, die wir haben können, indem wir diese 12 und diese Rechnungen als Betrag verwenden. Also, das ist es im Grunde für diese Implementierung. So können wir es in JavaScript implementieren. Davon abgesehen, das ist das Ende dieses Videos. Wir sehen uns im nächsten. 10. Minimale Einführung: Okay, also in diesem Video, werden wir tun, ist die Python Funktion für unseren Pseudocode zu erstellen , den wir vorher ausgedacht haben. Also lassen Sie mich einfach ein paar Dinge hier hinzufügen, weil die gelöscht. Also, was wir tun werden, ist, die Mindestfunktion dieses hier zu bestimmen. Also lass mich einfach größer machen. Also haben wir $7 und die Änderungen oder tiefsten, die wir haben, sind 1, 3 und 4. Also, um das zu tun, Beginnen wir mit der Definition unserer Parameter sofort in Python. Also n gleich sieben. Und wir haben diese Liste, die 134 ist. Und diese werden die Seife der Menschen darstellen dels gleich 1, 3, 4. Jetzt können wir mit unserer Funktion beginnen. Was wir also tun werden, ist zunächst, wir müssen diese minimale Zahlenliste erstellen und sie sollte bis unendlich initialisiert werden. Und danach, was wir tun werden, ist es jedes Mal, wenn wir durch jedes einzelne dieser Elemente gehen, hinzuzufügen oder zu ändern. Also, was wir zuerst tun werden, ist die eigentliche Liste zu erstellen indem Sie einfach hinzufügen oder benennen sie minimale Anzahl. Und es wird gleich einem weniger sein als in diesem Fall, was wir tun werden, ist, es mit ihm auszufüllen. Und wie wir das tun können, können wir einfach eine for-Schleife im Bereich von n plus eins durchlaufen und dann füllen, füllen Sie die minimale Zahl, die wir an sie anhängen werden. Float, was anzeigt, dass dies eine Unendlichkeit ist. Also jetzt ein freier Weg voran und drucken Sie es aus. Das werden wir sehen. Also, wenn ich das hier ausdrucke, werden wir diese Unendlichkeit als Elemente in dieser Liste bekommen. Nun, um damit zu beginnen, gehen wir hier zurück und lassen Sie uns unsere Funktion, unseren, unseren Pseudocode sehen. Denken Sie nun daran, dass wir diese brauchen, die die erste ist, die gleich 0 sein wird. Bevor wir etwas tun, machen wir es einfach gleich 0. So minimale Zahl bei 0 gleich 0 zu sein. Jetzt können wir unseren Code durchlaufen, also lassen Sie mich ihn gleich hier wieder ausführen. Und wie Sie sehen können, ist der erste 0 und der Rest ist unendlich. Was wir jetzt tun werden, ist 24 Netz-verschachtelte Schleifen zu passieren. Und während wir das tun, werden wir alle diese durchlaufen und dann alle aktualisieren. Also lassen Sie mich einfach so für Bell und Gürtel erstellen, wir werden mit denen beginnen und dann gehen wir auf die Mindestzahl. Um dies zu tun, können wir einfach eine zweite for-Schleife mit einem Bereich der Länge dieser Zahl erstellen. Es ist also für die Menge und den Bereich der Länge dieser tatsächlichen Liste, die wir erstellt haben. Es ist die Mindestzahl. Und was wir zuerst tun werden, ist zu überprüfen, ob der Betrag größer oder gleich der Rechnung ist . In diesem Fall, wenn dies der Fall ist, müssen wir es aktualisieren. Und es ist eines von zwei Dingen nach unseren Formeln. Es ist das Minimum zwischen der tatsächlichen Mindestanzahl Menge und oder eins plus die Mindestzahl bei Menge minus Verschütten. Also lassen Sie mich einfach hier umsetzen. Wie machen wir das? Also ist es minimale Anzahl an der Menge sollte gleich zwei Dinge sein. Das Minimum zwischen dem Mindestzahlenbetrag und der Mindestzahl 1 plus der Mindestzahl bei Betrag minus der, das ist es. Grundsätzlich ist es, wie wir es umsetzen können. Nun, wenn wir zurück gehen und lassen Sie uns aktualisieren und diesen Code erneut ausführen. Wie Sie sehen können, haben wir 0, 1, 2, 1, 1, 2, 2, 2. Und wenn wir es hier betrachten, haben wir 0, 1, 2, 1, 1, 2, 2, 2. Es ist also genau das gleiche Ergebnis. Denken Sie nun daran, dass dies nicht das ist, was wir eigentlich brauchen. Die eigentliche Lösung dieses Problems besteht darin, das letzte hier genau zu bekommen. Also werden wir den letzten von hier zurückgeben. Nun, eine Sache, auf die wir achten müssen, ist, dass vielleicht einige, es gibt keine solche Kombination, die es uns ermöglicht, die spezifische Nummer zu erhalten. Nehmen wir an, wir haben die $5 und den ganzen Nenner, alles von den besten, die wir haben, unsere 678. Also in diesem Fall können wir fünf mit einer dieser Rechnungen vertreten. Also wird die Antwort unendlich bleiben. Nun, in diesem Fall, wenn die Antwort unendlich ist, wir nicht unendlich zurück, wir geben nur minus eins zurück, was darauf hinweist, dass es keine Lösung für ein solches Problem gibt. In diesem Fall müssen wir darauf achten und sicherstellen, dass wir diesen Edge-Fall erhalten. Also, wie machen wir das? Wir können einfach eine if-Anweisung erstellen, wenn die Anzahl der Münzen. Also, wenn die Mindestzahl der Betrag ist, oder vielleicht, wenn die Mindestzahl am letzten, die n ist, gleich unendlich ist. Was wir tun werden, ist, mich einfach versuchen zu lassen, versucht hier zu fließen. Und wenn dies gleich dieser Zahl ist, was wir tun werden, ist minus1, minus1 zurückzugeben. Andernfalls werden wir die genaue Anzahl, Mindestzahl bei drucken. Und das war's also. Im Grunde ist es, wie wir es tun können. Wenn wir nun zurückgehen, auf Refresh drücken und diesen Code erneut ausführen, denken wir, dass wir einen Einzug haben, der nicht mit dem anderen übereinstimmt. Alles klar, also lasst es uns schnell reparieren. Wir werden tun, ist, es so zu machen. Und jetzt denke ich, dass wir gut sind, wenn wir zurückgehen, fahren Sie es nochmal. Und die Antwort wäre zwei. Nun in diesem Fall, wenn wir das Beispiel haben, über das wir früher gesagt haben, haben wir 6, 7 und 8. Wenn wir zurückgehen und aktualisieren, bekommen wir minus eins, was anzeigt, dass es keine Möglichkeit gibt, diesen Betrag mit diesen drei Arten von Rechnungen zu bekommen , weil sie größer als fünf sind. Also das ist es im Grunde für dieses Problem, so können wir mit Python begegnet werden. Davon abgesehen, das ist das Ende dieses Videos. Wir sehen uns in der nächsten. 11. Anzahl von Möglichkeiten, einen Betrag zu zurückkommen: Alles klar, in diesem Beispiel wird es ein anderes Problem durchlaufen, nämlich die Anzahl der Möglichkeiten, wie wir eine Änderung für einen bestimmten Betrag vornehmen müssen. Also nehmen wir an, wir haben einen $5 Betrag, der genau hier ist. Und was wir tun werden, ist die Anzahl der Möglichkeiten zu berechnen wir diese fünf Dollar repräsentieren können, wenn wir diese Rechnungen hier haben. Also, wenn Sie 1.2.34 Rechnung haben, und in diesem Fall, was wir tun werden, ist die dynamische Programmierung zu verwenden, um die optimale Lösung zu haben oder die genaue Anzahl der Möglichkeiten, die wir mit diesen Rechnungen berechnen können, um diesen $5 Betrag zu haben. Um das zu tun, beginnen wir mit der Erstellung der Liste, die wir brauchen werden. Und wie wir bereits gesagt haben, dieser Fünf-Dollar, werden wir eine Liste erstellen, die bis zu $5 ausmachen kann. Um das zu tun, werden wir die Größe dieser Liste als fünf plus eins haben, das ist sechs. Und dieser Fall, lassen Sie mich einfach diese Liste hier erstellen. Also haben wir 123456 Elemente in dieser Liste. Die Indizes sind also wie folgt, 012, Tag 4 und 5. Diese Indizes stellen also den Betrag dar. Also lassen Sie mich es hier schreiben. Es tut mir leid. Also hier haben wir den Betrag. Und was wir hier haben werden, ist die Anzahl der Möglichkeiten. Also werde ich es einfach als Anzahl von Möglichkeiten bezeichnen. Was wir also tun werden, ist, die Basis, die wir haben, einzeln durchzugehen und dann die Anzahl der Möglichkeiten zu überprüfen, wie wir diesen Fünf-Dollar mit diesen Belk hier repräsentieren können . Also zuerst, was wir tun werden, ist, alle diese auf 0 zu initialisieren. Also 00000. Der erste wäre jedoch der Basisfall. Und es ist sicher zu sagen, dass dieser als eins initialisiert werden sollte. Denn wenn wir darüber nachdenken, wenn wir nicht oh haben, haben wir eine $1 oder $2 oder drei oder $4 Rechnungen und wir müssen die Menge der Nullen präsentieren. Es gibt nur eine Möglichkeit, diesen Betrag darzustellen, indem Sie einfach keinen dieser Beträge haben oder nicht verwenden. Es ist also sicher zu sagen, dass wir die Anzahl der Möglichkeiten als eins für die Menge 0 verwenden können. Richtig? Wenn wir es uns ansehen, fangen wir mit diesem hier an. Also lassen Sie mich die Farbe ändern. Also jetzt arbeiten wir mit dieser $1 Rechnung. Wie viele Möglichkeiten können wir den Betrag eines mit einer $1-Rechnung darstellen? Und es ist ziemlich unkompliziert. Wir können es auf eine Weise repräsentieren. Also statt 0 hier zu haben, werden wir eine haben. Nun, gehen wir auf den $2 Betrag. Wie viele Möglichkeiten können wir diese $2 Betrag mit dieser $1 Rechnung darstellen? Und natürlich ist es das Gleiche. Wir haben nur einen Weg, der ist, 2 $1 Rechnungen zu verwenden. Dasselbe hier. Also werden wir 111 haben. Also, was wir sagen, ist, dass wir diesen 34 oder $5 Betrag mit $1 Rechnung auf eine und einzige Weise darstellen können . Und das ist zu verwenden, zum Beispiel, hier, wenn wir $3 Betrag haben, so wie wir können, wie können wir diesen $3 Betrag bekommen? Wir können 3 $1 am besten von hier aus verwenden. Und es ist das Gleiche für 4 $5. Jetzt gehen wir zum zweiten. Das heißt, wir haben diese $2, aber jetzt, was wir tun werden, ist, einfach überspringen 01 Betrag, da wir diese Beträge mit einem $2 Rechnung präsentieren können, weil zwei größer als 01 ist. Also gehen wir den ganzen Weg zu diesem $2 Betrag. Nun, lasst uns darüber nachdenken. Was haben wir? Wir haben diese $2 Menge, richtig? Und das haben wir auch diese $2 Rechnungen. So können wir diese $2 Betrag mit 1 $2 Rechnung von hier repräsentieren. Und natürlich wollen wir nicht vergessen, dass wir es auf eine Weise darstellen können , indem wir diese $1 Rechnungen verwenden. Also, was wir tun werden, ist, das zu entfernen und zwei hier hinzuzufügen, weil wir es jetzt auf zwei Arten darstellen können. Und wir werden die Formel in ein bisschen herausfinden, aber lassen Sie es uns jetzt klären. So zum Beispiel, jetzt haben wir diesen $3 Betrag. Also, was wir tun werden, ist, auch auf zwei Arten zu vertreten, oder? Lassen Sie mich auch hier schreiben, und lassen Sie uns darüber nachdenken, wie wir diesen Betrag drei repräsentieren können. Also, wenn wir $3 haben, können wir entweder zwei, äh, 3 $1 Scheine benutzen . Also 3 mal 1 oder 2, oder 1 zu Dollar-Scheine und 1 $1 Rechnung, richtig? Also 12. Rechnungen und 1 $1 Rechnung. Und wir werden den Betrag bekommen, der drei ist wie zuvor. Nun, wenn wir zurück hierher gehen und herausfinden, wie viele Möglichkeiten wir diesen Betrag repräsentieren können. Also, wenn wir $4 haben und wir werden entweder für $1 Scheine oder zwei Dollar-Scheine, oder 1 $2 Rechnung plus 2 $1 Scheine brauchen entweder für $1 Scheine oder zwei Dollar-Scheine, . Also, wenn das Sinn ergibt, ist es okay, wenn nicht, lassen Sie uns darüber nachdenken, dass wir hier für $1 Rechnungen haben. Und hier haben wir, oder wir müssen, zu Dollar-Scheine, oder wir haben 1 $2 Rechnungen und zu $1 Rechnung. Also alle diese werden die gleichen sein, wie Sie hier sehen können. Wenn ich es zeichne. Wir werden auch hier haben, und hier, das Gleiche und wir haben für $1 Scheine. Also, das ist es im Grunde. Lasst uns jetzt über die Formel nachdenken. Wie können wir das bekommen? Wir haben hier drei Wege. Wir haben also drei Möglichkeiten, diese Nummer vier darzustellen. Und anstatt eines hier zu haben, werden wir es entfernen und drei hinzufügen. Also, wenn wir darüber nachdenken, können wir sehen, dass, wenn wir diese $2,2 Dollar-Scheine hier haben, was wir tatsächlich getan haben, ist, dass wir eins zu der Anzahl der Möglichkeiten hinzugefügt haben, auf die wir hineingegangen sind. Also, um es klarzustellen, lassen Sie mich einfach die Formel hier schreiben. Was wir sagen, ist, dass wir diese Zahl aktualisieren müssen, die Anzahl von Möglichkeiten bei einem bestimmten Index ist. Angenommen, es ist Anzeige I. Es wird gleich eins plus die Anzahl der Möglichkeiten sein. Und lassen Sie mich das alles löschen. Und es ist die Anzahl der Wege bei dieser spezifischen Menge, die vier minus dem, was wir von hier bekommen. Und wir werden das nennen, diese Liste als Rechnungen und jeden einzelnen von ihnen als Rechnung bezeichnen. Also ist es Betrag minus Gürtel. Also in diesem Fall, wenn wir uns dieses Beispiel ansehen, sind wir auf dem Berg vor und der Build Nummer zwei. Also, was wir tatsächlich getan haben, ist, dass wir diesen von hier hinzugefügt haben. Also hier ist es nicht einer, es ist die Anzahl der Möglichkeiten. Also ist es plus 0 gleich. Und lassen Sie mich das einfach löschen. Also ist es tatsächlich gleich dieser eine Anzahl von Wegen bei I, gleich der Anzahl der Wege bei i. Also, was wir bereits haben, die tatsächliche Anzahl der Wege plus die Anzahl der Wege. Lassen Sie uns diese Anzahl von Möglichkeiten bei Betrag minus Rechnungen hören. Das ist also die Formel, die wir jetzt verwenden werden, wenn Sie es hier verwenden, Lasst uns darüber nachdenken. Wir haben schon eins hier. Also die Anzahl der Wege bei, schreibe ich hier, es wird gleich der eins plus Anzahl von Möglichkeiten bei 4 minus 2, die gleich 2 ist. Also, wenn wir zurück zu dem Index gehen, um zu sehen, dass wir bereits zwei hier. Also werden wir 1 plus 2 haben, was gleich 3 ist. Und das haben wir mit dem Denken oder mit dem Beispiel, das wir vorher getan haben, bekommen. Wir haben also herausgefunden, dass wir drei Möglichkeiten haben, diese vier zu repräsentieren. Wir haben 1 $2 Rechnungen. Nun, gehen wir zum letzten, der fünf ist. Und mit dieser Formel können wir berechnen, dass, wenn wir den $5 Betrag haben und wir diese, diese Tupel haben, wir einen Weg plus die Anzahl der Wege bei fünf minus zwei haben können, was die Anzahl der Möglichkeiten an diesem Index genau hier, drei ist. Also ist es zwei, also 1 plus 2 wird 3. Nun, wenn wir genau dasselbe für die 34 tun, die wir bekommen können. Also lassen Sie mich einfach die Farbe ändern. Lassen Sie mich es einfach blauer Tinte machen. Also, was wir tun werden, ist, diese von hier zu beschneiden und sie hier einzufügen. Lassen Sie uns das löschen und fahren Sie fort. Was wir sagen, ist, dass wir jetzt bei drei sind. Wie gesagt, können wir 012 überspringen, weil sie kleiner als drei sind. Wir werden den ganzen Weg bis drei gehen. Und jetzt, was wir tun werden, ist zu sagen, dass wir diesen Amar drei mit zwei Möglichkeiten und die Anzahl der Wege bei drei minus drei repräsentieren können . Also dieser Betrag minus diese drei hier, das ist der Gürtel. Und wenn wir auf die Anzahl der Wege gehen, drei Monate heute bei 0, also haben wir einen. Also statt drei hier zu haben, werden wir 2 plus 1 haben, das ist 3. Jetzt werden wir genau das Gleiche für diesen hier tun. Also ist es 3 plus die Anzahl der Möglichkeiten bei Menge minus mil, die vier minus drei ist, was tatsächlich eins ist. Also werden wir dies in 3 plus 1 ändern, das ist 4. Jetzt werden wir mit dieser Datei enden, das heißt, wir haben 3 plus die Anzahl der Möglichkeiten in Höhe, die 5 minus die Anzahl der Wörter, die Anzahl der Glocken oder der eigentliche Gürtel ist , was großartig ist. Also 5 minus 3 wird uns 2 geben. Und wir werden uns ansehen, um hier die Anzahl der Möglichkeiten zu haben, das ist zwei. Also werden wir das in drei plus zwei bis fünf aktualisieren. Also hoffe ich, dass das Sinn ergibt. Wir werden mit diesem letzten, der vier ist, fortfahren. Jetzt haben wir die vier Rechnungsbetrag zum Abendessen nur für diese beiden berechnet, weil es keinen Sinn macht, diese vier in 0123 zu haben, da sie kleiner sind. Also, was wir tun werden, ist, diese 4 zu nehmen. Wir haben diese vier, das ist die Anzahl der Möglichkeiten bei I plus die Anzahl der Wege bei Betrag minus 12. Also 4. Dies ist der Betrag minus vor Bill. Also werden wir die Anzahl der Wege bei 0 bekommen. So können wir sehen, dass es vier plus eins ist fünf. Dann nehmen wir diese fünf gleich hier. Plus die Anzahl der Wege bei der Menge minus gut, die auch bei einem ist, weil die Anzahl der Wege von 5 minus 4, die gleich eins ist. So Anzahl der Wege an einem, zu überprüfen, ob es gleich eins ist. Also werden wir das auf fünf plus eins aktualisieren. Wir werden mit sechs enden. Das war's also. Grundsätzlich ist dies, wie wir die Anzahl der Möglichkeiten mit der dynamischen Programmiermethode mit diesem spezifischen Betrag erhalten können. Nun, was wir tun werden, ist, dass das aussehen würde, wenn das genau ist, ist dies die richtige Anzahl von Möglichkeiten. Also, wenn Sie diesen $5 Betrag haben und wir diese vier Arten von Bill haben, was wir tun werden, ist, diese Datei mit diesen manuell darzustellen . Also lasst uns darüber nachdenken. Wir können entweder vier oder 5 $1 Rechnungen haben, oder wir können 2122 Doppel plus 1 $1 Rechnung haben. Oder wir können auch zwei oder 1 $2 Rechnungen und 3 $1 Rechnungen haben. Oder wir können auch 32 haben. Also 1 $3 Rechnung und 23 Dollar-Scheine und 12 Dollar Geschäftsseite. Oder wir können auch und 1, also 1, 4 Dollar-Scheine und 1 $1 Rechnung. Also diese fünf oder wir können auch die 311, also 13 Dollar-Scheine und $1 Scheine. Und das, wenn wir sie zählen, 123456. Also werden wir am Ende mit sechs Möglichkeiten, diesen $5 Betrag mit diesen vier Arten von Menschen darzustellen . Also hoffe ich, dass das Sinn ergibt. Im nächsten Video werden wir einfach den Pseudocode schreiben und dann werden wir es in unseren Sprachen implementieren. So sehen wir uns dann. 12. Anzahl der Arten: Alles klar, in diesem Video werden wir tun, ist, unsere Gedanken zusammenzufassen und tatsächlich einen Pseudocode zu schreiben, den wir verwenden werden, wenn wir diese Größenordnung implementieren, diesen Algorithmus jetzt Code. Also lassen Sie mich einfach alle löschen. Und natürlich all das auch. So können wir jetzt weitermachen. Jetzt lassen Sie uns eine Sekunde darüber nachdenken. Also, was wir tatsächlich getan haben, ist, dass jedes Mal, wenn wir eine Arbeit mit einem Gürtel benutzen werden. Also lass mich die Pillen hier schnell schreiben. Jedes Mal, wenn wir von hier aus mit einer Rechnung arbeiten, werden wir diese Anzahl von Möglichkeiten hinzufügen oder aktualisieren. Also, was wir sagen werden, ist, dass, wenn der Betrag kleiner ist als diese Glocke, wir werden nichts tun. Wir werden es einfach überspringen. Also sollte der Pseudocode so gehen. Das erste, was wir tun werden, ist zu überprüfen, ob die Menge größer ist als der Gürtel. Aber das ist der Fall. Wir werden weitermachen. So ist der Betrag größer oder gleich der Rechnung, die wir haben. Wir werden etwas tun. In diesem Fall, was wir tun werden, ist, die Anzahl der Möglichkeiten an diesem Gürtel zu aktualisieren , oder? Also, was wir tun werden, tut mir leid, bei diesem tatsächlichen Betrag. Also, was wir tun werden, ist, die Anzahl der Möglichkeiten zu aktualisieren. Und in diesem Fall wird es auf die tatsächliche Menge sein. Wir werden es in aktualisieren. Es wird gleich zwei Dinge sein, die zusammen addiert werden, um gleich der tatsächlichen Anzahl von Möglichkeiten zu sein, die wir jetzt tatsächlich haben. So wird es gleich der Anzahl der Wege in Höhe sein. Wir können etwas Neues hinzufügen, das ist die Anzahl der Möglichkeiten in Höhe minus eins. So wird es gleich der Anzahl der Wege in Höhe minus der Glocke, die wir haben. Nun, wenn Sie sicherstellen wollen, dass dieser Algorithmus tatsächlich funktioniert, Lassen Sie uns das einfach tun, zum Beispiel, um vier und können Sie den letzten hier verwenden, der auch die Glocke für ist. Wir werden also davon ausgehen, dass wir hier sind. Also befinden wir uns jetzt in der Phase, in der wir die Anzahl der Möglichkeiten haben, das ist vier, und wir werden sie aktualisieren. Also werden wir schauen, ob der Betrag größer oder gleich der Rechnung ist. Und in diesem Fall ist die Menge vier, die gleich vier ist. Das funktioniert also tatsächlich. Was wir jetzt tun werden, ist, die Anzahl der Möglichkeiten zu dem bestimmten Betrag zu aktualisieren. So Anzahl der Wege bei vier wäre gleich der Anzahl der Wege bei vier, was vier plus die Anzahl der Wege bei Menge minus verschütten ist. Also die Anzahl der Wege in Höhe meines Zaubers , der 4 minus 4 ist, gleich 0 zu sein. Wir werden auf die Anzahl der Wege gehen. Nehmen Sie diese hinzugefügt, um die 4 wird uns 5 geben. So, jetzt können wir, wir wissen, dass unsere tatsächliche Formel genau hier, die wir erzeugt haben, tatsächlich wahr ist und genau funktioniert. Das war's also. Im Grunde liegt das tief vor Gericht. Und eigentlich ist das eigentlich ziemlich unkompliziert. Sobald Sie die Methode kennen, können Sie diesen Pseudocode finden. Also ermutige ich jedes Mal, wenn Sie das dynamische Programmierproblem lösen, zu schreiben, es so aufzuschreiben und zu versuchen, eine Lösung zu finden. Und versuchen Sie, die tatsächliche Methode oder die tatsächliche Formel zu finden, die TB in diesem Problem verwendet wird. Als erster Teil des Problems wussten wir nicht, dass die Formel einfach mit dem Fluss gehen würde. So zum Beispiel, hier, haben wir gerade gesagt, dass wir bei Menge 0 in keiner Weise anders als eine und einzige Weise vertreten können , die heißt, keinen Geldbetrag verwenden. Jetzt bei Menge Nummer eins, können wir es repräsentieren, wenn wir diese $1 haben, aber wir können es durch eins darstellen. Und hier genau das Gleiche für die anderen. Und dann kannten wir erst mit dieser Nummer drei die Formel. Es tut mir Leid. Erst mit der Summe von Nummer vier kannten wir diese Formel. Und wir berechneten anhand dieses Beispiels direkt hier. Fangen Sie also immer mit einem Beispiel an und versuchen Sie später, eine Formel zu finden. Das war's also. Grundsätzlich ist dies für den Pseudocode. Beim nächsten Video werden wir es und unseren eigentlichen Code implementieren. Dann, um dich zu sehen. 13. Anzahl der Arten der Java-Implementierung: Alles klar, in diesem Video werden wir unsere Funktion implementieren, Funktion, die wir zuvor ausgedacht haben. Und ich habe diese Methode bereits öffentliche statische int Anzahl von Wegen instanziiert. Und wir haben zwei Parameter. Der erste ist der tatsächliche Betrag, der mit N bezeichnet wird, und der zweite ist die tatsächlichen Glocken. Das ist also eine Reihe von denen hier. Was wir also tun werden, ist, dass wir wie zuvor ein neues Array erstellen werden, , das heißt,die Anzahl der Möglichkeiten zu jedem einzelnen Betrag zu implementieren oder hinzuzufügen. Also lassen Sie mich nur instanziiert, wie es gleich 0 und plus eins sein wird, wie wir gesagt haben. Nun, was wir tun werden, ist, den ersten zu bezeichnen oder hinzuzufügen, wie wir hier gesagt haben, ist der erste sollte gleich eins sein. Also Abfall bei 0, um gleich eins zu sein. Und der andere wird gleich 0 sein, was die Standardnummer oder die Standardmethode ist, um in einem Array instanziiert zu werden. Wie gesagt, wir haben jetzt schon eins hier. Was wir tun werden, ist, all diese hier durchzugehen , ist von irgendwie durch all das, was ich gebaut habe. Und dann werden wir natürlich die Anzahl der Möglichkeiten hier aktualisieren. Also gehen wir zurück. Nun, wenn wir darüber nachdenken, was wir tun werden, ist, die for-Schleife zu bezahlen, beginnend mit 0 bis zu den Rechnungen, die Länge und aktualisiert. Und die zweite, wir werden auch 0 haben. Den ganzen Weg zu, es tut mir leid, hier können wir tatsächlich sagen, dass es eins ist. Und die beiden werden den ganzen Weg zu den Wegen sein. Diese Größe Punktlänge, es tut mir leid, ich und j plus, plus. Nun, was wir zuerst tun werden, ist zu überprüfen, ob dieser Betrag größer oder gleich der Rechnung ist. Und wie gesagt, ist dieser Betrag tatsächlich in der zweiten for-Schleife als j bezeichnet. Wir können tatsächlich dieses j in Menge davon ändern wird uns machen, machen es einfacher. Also lassen Sie mich das ganz schnell ändern. Und dann haben wir auch Betrag. Nun, was wir tun werden, ist zu überprüfen, ob dieser Betrag größer oder gleich der tatsächlichen Rechnung ist . Und was haben wir gesagt? Wir sagten, dieser wird als Rechnungen vermerkt werden. Und die tatsächliche Rechnungsbandbreite wird bestenfalls bei I liegen, was 0, 1, 2, 3 und 4 ist , so weiter, so weiter. Und in diesem Fall, was wir tun werden, ist zu überprüfen, ob der Betrag größer oder gleich dem, was gleich Rechnungen sein wird. Ich weiß, dass das der Fall ist. Wir müssen die Anzahl der Möglichkeiten aktualisieren. Also die Art und Weise, wie ich, oder die Art und Weise, die eine Website belaufen, wird auf zwei Arten aktualisiert werden, um die Menge plus Möglichkeiten , wie wir sagten, wir werden die Formel verwenden, Betrag minus dies genau hier. Also, wie haben wir diese Rechnung bekommen? Es werden die Glocken bei I. Also in diesem Fall, was wir gesagt haben, dass wir dies berechnen können, indem wir Glocken an i verwenden. Also werde ich es einfach hier bei I schreiben und wir haben erfolgreich aktualisiert. Nun, was wir tun werden, ist, einfach die Anzahl der Wege zurückzugeben, die wir haben. Also, wenn wir hier zurück gehen, brauchen wir nur dieses von seinem. Das ist also die Zahl der sechs. Denken Sie daran, dass der Zweck dieses Problems ist, dass, wenn wir einen Betrag von 5$ haben, wie viele Möglichkeiten können wir diesen Fünf-Dollar repräsentieren? Und wir haben alle diese getan, um die endgültige Lösung zu finden, nämlich eine Sechs. Also, wie können wir das nehmen? Wir können einfach nach der Anzahl der Wege in unserem Anfangsbetrag, der fünf ist, fragen. Und es wird sechs Möglichkeiten gleich sein. Also, das ist es im Grunde jetzt, das ist, was wir hier zurückkehren sollten. Also, nachdem wir von diesen beiden for-Schleifen verschachtelt für Schleifen beendet haben, werden wir die Wege bei darstellen. Das war's also. Grundsätzlich ist dies für dieses Problem. Nun, wenn wir es testen, können wir einfach eine Hauptfunktion verwenden. Also werde ich einfach ein Hauptfunktionskriterium erstellen. Und was wir tun werden, ist die Anzahl der Wellen mit n und Rechnungen zu nennen. Und davor werden wir das hier initialisieren. So wird n gleich der tatsächlichen Stichprobe sein, die fünf ist. Und Endrechnungen werden gleich diesem tatsächlichen, das 12341 ist. Gut. Nun, wenn wir es ausdrucken wollen, lassen Sie es mir nur leid tun. Sonnensystem dot out, dot, drucken Sie hier aus. Und lassen Sie es uns laufen. Und wie wir hier bei diesem Problem sehen können, werde ich sechs bekommen, was die letzte ist. Nun, wenn wir all dies für jetzt zurückgeben wollen, sehen Sie, dass die letzte hier genau. Also, was wir tun werden, ist eine Liste zurückzugeben. Und wenn wir es noch einmal ausführen, werden wir, es tut mir leid, wir können das nicht ausführen. Natürlich müssen wir hier nur eine for-Schleife erstellen. Also für ich gleich 0, ich bin weniger als das Ende und ich gehe. Also, ich denke, wir können ausdrucken, was wir haben. Also lass mich einfach diesen Ort hier erschaffen, um gleich der Anzahl von Wegen zu sein. Also denke ich, dass wir gut sind. Wir können das hier löschen. Und natürlich können wir bei jedem einzelnen von ihnen Wege ausdrucken. Mit ADD drucke ich es einfach aus. Und wir werden es ausdrucken. So an irgendeinem Raum könnte weitergehen. Wenn wir es ausführen, werden wir 11 bis 35 bekommen. Wenn wir hier gehen, können wir sehen, dass wir 1, 1 bis 5 haben. Natürlich haben wir den letzten vergessen, vergessen, dass es und plus eins ist. Jetzt, wenn wir es noch einmal ausführen, bekommen wir eins, 1, 2, 3, 5, 6. Und es ist genau das gleiche weniger, das genaue Array, das wir mit diesem Beispiel direkt hier manuell finden. Also, das ist es im Grunde für die Implementierung. Auf diese Weise können wir sie umsetzen. Und natürlich brauchst du das alles nicht. Dies dient zur Visualisierung. Wir brauchen nur den letzten Index oder das letzte Element in der Anzahl der Wege weniger. Das ist, um die Menge fünf zu repräsentieren, mit wie vielen Möglichkeiten, diese hier zu verwenden. Also, das ist es im Grunde für dieses Beispiel, sehen Sie im nächsten Video. 14. Anzahl der Arten: Alles klar, also in diesem Video, wer kann unsere Funktion mit einem JavaScript implementieren. Wie wir bereits gesagt haben, werden wir es mit dieser Anzahl von Möglichkeiten als Array implementieren. Und wir können zwei Dinge haben. Der tatsächliche Betrag, der $5 ist, und die Anzahl der Betten, oder die Arten von Glocken und ein Array oder eine Liste. Was wir also tun werden, ist einfach mit der Erstellung der Funktion zu beginnen. Also wird die Funktion eine Reihe von Möglichkeiten sein und was wir nicht tun und was ist die Menge. Und dann haben wir auch von Haustieren genau hier bezeichnet. Und wir können mit der Erstellung des Arrays beginnen und es zwei Möglichkeiten nennen, um einem neuen Array gleich zu sein. Und wie gesagt, wir brauchen n plus eins als Größe. Und wir werden es mit Nullen füllen. Nun, wie wir bereits gesagt haben. Aber wir müssen tun, ist, diesen Betrag bei 0 nach Anzahl von Wegen zu spüren, was eins ist. Um das zu tun, werden wir einfach Wege bei 0 schreiben, um gleich eins zu sein. Und jetzt können wir damit beginnen, unsere beiden verschachtelten for-Schleifen zu erstellen. also auf dieses Beispiel zurückgehen, können wir sehen, dass wir mit einer for-Schleife beginnen werden, die für die Glocken sein wird. Und dann werden wir die Anzahl der Möglichkeiten aktualisieren, jedes Mal, wenn wir eine neue Rechnung durchlaufen. Also wird der erste für die Geburt sein. Denn wir haben einen variablen Betrag oder der erste wird weniger gleich sein es tatsächlich, und es wird gleich 0 auf den ersten. Und dann, was wir tun werden, ist, es zu aktualisieren. Natürlich wird es bis und plus eins sein. Und dann werden wir bauen. Also, das ist es im Grunde. Und jetzt, was wir tun werden, tut mir leid, nicht bis zum n plus eins. Es ist schuldig und die eigentliche Liste. Und in diesem Fall, was wir schreiben werden, ist Bills Punktlänge. Also das ist es für die erste for-Schleife. Der andere wäre verschachtelt, wird variabler Betrag sein , der gleich 1 sein wird. Und in diesem Fall werden wir den ganzen Weg zu Betrag suchen , der gleich kleiner als und plus eins sein wird. Nun, was wir tun werden, ist, diesen Betrag jedes Mal zu aktualisieren, wenn wir es durchmachen. Jetzt können wir mit der eigentlichen Funktion beginnen. Also, was wir sagen werden ist, dass wir uns genau hier ansehen werden. Also, wenn der Betrag größer oder gleich Bett ist, und wie Sie sagten, Bill ist kein Index, wie wir es früher initialisieren, ist es tatsächlich der beste bei diesem tatsächlichen Index. So zum Beispiel, hier bei 0 werden wir eine bekommen, dieses wir werden 2 und so weiter und so weiter bekommen und so weiter. Also zu implementieren, aber wir müssen tun, ist zu überprüfen, ob der Betrag als oder gleich ist. Diese Glocken an diesem Index, der gebaut werden wird. Jetzt, um es einfacher zu machen, was ich tun werde, ist, einfach all dies zu entfernen und eine andere Methode für Schleife zu verwenden , die aus Rechnungen gebaut wird. Also, was ich sagen werde, ist, dass wir Bill, Rechnungen lassen werden. Und jetzt können wir Glocke und statt dieser bei diesem Index verwenden. Das ist also eine andere Funktion. Also, was wir hier einfach sagen ist , dass Gürtel der Geburt ist eigentlich nicht ersetzen Rechnungen, 0 von Rechnungen auf einem und so weiter und so weiter und so weiter. Also brauchen wir das nicht mehr. Wir können es einfach als verwenden. Nun, was wir tun werden, ist, die Anzahl der Möglichkeiten zu dem bestimmten Betrag zu aktualisieren indem wir einfach diese Anzahl von Möglichkeiten in der bestimmten Menge zu einer neuen Sache hinzufügen. Das ist die Anzahl der Möglichkeiten zum Betrag abzüglich der tatsächlichen Rechnung. Das ist also die Formel, die wir hier finden. Und wir haben bereits gesagt, dass dieser Gesetzentwurf bei i gebaut ist . Dies ist die tatsächliche Formel, die fortgesetzt wird. Und jetzt müssen wir nur die Anzahl der Möglichkeiten beim letzten Index zurückgeben. Also, das ist sechs. Wir müssen nur die Anzahl der Wege in Höhe von fünf zurückgeben. In diesem Fall haben wir es so bezeichnet wie n. So werden wir einfach Wege zurückgeben. Und jetzt sind wir gut. Ich denke, wir können damit arbeiten. Das ist unsere eigentliche Formel. Nun, wenn wir es verwenden oder getestet wollen, können wir es tatsächlich hier tun. Also lassen Sie uns bezeichnen, lassen Sie n gleich fünf und führen zu einer Fläche von 12345. Nun, was wir tun werden, ist, die Anzahl der Möglichkeiten zu drucken , die wir mit diesem Betrag erstellen können und gefüllt ist. Also jetzt, wenn wir tatsächlich getestet haben, Ordnung, also hier haben wir Tonsillen Zweig konsultiert. Und in diesem Fall, was ich zu CMD gehen werde und was ich verwenden werde, um das JavaScript auszuführen. Ich werde NodeJS-Server verwenden. Wenn Sie es noch nicht installiert haben. Sie können voran gehen und es jetzt installieren. Kann einfach auf den Kopf gehen, um zu notieren. Und wie gesagt, können Sie es von hier herunterladen. Also gehen Sie weiter und laden Sie es herunter. Dann, was Sie tun, ist, zu Ihrer Dynamik oder zu Ihrem Verzeichnis zu gehen. In diesem Fall werde ich es JavaScript-dynamische Programmierung nennen. Und in dieser dynamischen Programmierung werde ich diese Anzahl von Möglichkeiten haben, die ich früher erstellt habe. Und Sie können es einfach von seinem laufen. Also werde ich diese Knoten verwenden und einfach die Anzahl der Möglichkeiten schreiben, Betrag Punkt js. Und ich werde sechs als die Anzahl der Möglichkeiten bekommen. Denken Sie daran, dass wir nur diesen letzten haben wollten. Nun, wenn wir diese Anzahl von Möglichkeiten visualisieren wollen, weniger. Also, mit anderen Worten, wir wollen diese Liste visualisieren wie 1, 2, 3, 1, 1, 2, 3, 5, 6. Denken Sie daran, dass wir etwas anderes zurückgeben sollten. Hier geben wir Wege zurück, wie wir schriftliche Wege konkurrieren können. Nun, wenn wir es wieder ausführen, werden wir das weniger als 112357 bekommen. Denken Sie nun daran, dass wir nur die letzte brauchen, die repräsentieren soll, um diese $5 Betrag mit diesen vier Arten von Gürtel zu repräsentieren. Also haben wir sechs Möglichkeiten, das zu tun. Also, das ist es im Grunde, das ist es für dieses Problem. Wir sehen uns im nächsten Video. 15. Anzahl der Methoden Ways: Alles klar, in diesem Video werden wir fortfahren oder inkrementelle Funktion mit Python verwenden. Wie wir bereits gesagt haben, haben wir die Anzahl der Möglichkeiten, die eine Liste ist, die wir speichern werden. Die Anzahl der Möglichkeiten für jeden einzelnen Betrag bis zum Endbetrag oder den Betrag, den wir wollen. Also tun Sie das, beginnen wir mit der Erstellung einer Liste in Python. Gehen wir also zu unserem Visual Studio. Und in diesem Fall werde ich tun, ist eine Liste zu erstellen. Ich werde es benennen. Und es wird einfach Liste sein, wie diese oder ich kann es einfach eckige Klammern machen. Und in diesem Fall werde ich diese Liste bis zum Ende füllen , genau hier. Lassen Sie uns zunächst unsere beiden Parameter definieren. Also das erste ist und es wird gleich fünf sein. Und die zweite wird gebaut, die auch eine Liste ist. Und es wird gleich 1, 2, 3 und 4 sein. Und in diesem Fall, was ich tun werde, ist, diese Liste L oder LastName zu erstellen. Es wiegt tatsächlich, da wir es als Abfall verwenden werden. Und natürlich werde ich es mit Nullen füllen. Also für ich im Bereich von vielleicht n plus eins, werden wir tun, ist es, an diese 0 anzuhängen. Verschwendung, die anhängen. Und ich werde 0 direkt hier anhängen. Und natürlich, wenn wir es ausdrucken, werden wir unsere Liste mit Nullen füllen lassen. Also, wenn wir hier und rechts gehen, nach der Anzahl der Möglichkeiten, die wir 000, 000, 000 bekommen werden, und das ist die Liste leer. Also haben wir 012345 Elemente oder fünf Indizes, die sechs sind, seit wir mit 0 begonnen haben. Nun, was wir tun werden, ist zum dritten, der erste war eins mit eins. Was ich also tun werde, ist einfach zu sagen, dass ich bei 0 es mit einem füllen werde. Ich werde es nochmal laufen lassen. Wir kriegen einen hier. So können wir jetzt mit unserer Funktion beginnen. Wir haben alles bereit für uns. Wir können unsere for-Schleifen lösen. Da wir diese Funktion haben, was wir tun werden, ist, durch alle Elemente oder das ganze Ende der Zahlen hier in den Glocken zu schleifen , und dann dasselbe für die Anzahl der Möglichkeiten zu tun und aktualisiert. Also werde ich Marke löschen und ich werde mit der Erstellung eines Build aus den Rechnungen fortsetzen . Jetzt, da wir fortfahren können, können wir den Betrag jetzt für diese spezifische Art und Weise erstellen. Was wir also tun werden, ist, dass wir von einem den ganzen Weg bis zum n plus 1 beginnen werden. Und wie wir das tun können, können wir die Reichweite von eins bis zum Ende plus eins nutzen. Und dann werden wir natürlich diesen Blick öffnen. Und wir werden überprüfen, wie wir bereits gesagt haben, ob der Betrag größer ist als die Rechnung, wir werden die Anzahl der Möglichkeiten aktualisieren. Also, wie machst du das? Wir überprüfen einfach, ob die Menge größer oder gleich den Glocken ist oder die Spannung erzeugt wird. Wenn dies der Fall ist, müssen wir die Anzahl der Möglichkeiten aktualisieren. So wird eine Reihe von Möglichkeiten zur Menge gleich sein, wie wir sagten, mit der Formel, die wir im Pseudocode erzeugt haben, Anzahl der Wege gleich der Anzahl der Wege plus Anzahl der Wege bei Betrag minus minus1. Also in diesem Fall, die Anzahl der Wege Bei der Menge gleich zwei Wege bei der Menge plus Wege bei der Menge minus dem Gürtel. Denken Sie nun daran, dass diese Rechnung tatsächlich ist, dass wir gebaut und gebaut sind. Und das wird uns Glocken bei 0 geben, Glocken bei I und so weiter und so weiter. Das ist also nur vielleicht eine Abkürzungslösung für die for-Schleife, anstatt sie in Reichweite und Zugriff zu haben und Glocken bei i für bestimmte Indizes, die wir verwenden können, Rechnung und Glocken. Das war's also. Im Grunde ist es, wie wir es aktualisieren können. Nun, was wir tun werden, ist einfach hier auszudrucken. Also, wenn wir Wege drucken, und jetzt gehen wir zurück. Und wie Sie sehen können, haben wir das gleiche exakte Ergebnis wie erwartet 1, 2, 3, 5 und 6. Also hier dieses, 1, 2, 3, 5 und 6. Wir wissen also, dass unser Programm funktioniert. Nun, was wir wollen zu tun oder was unser Ziel war, die Anzahl der Möglichkeiten zu generieren, die wir angeben können, oder wir können $5 als Gegenleistung $5 mit der Annahme erstellen , dass wir nur diese vier Arten von Rechnungen haben. Also, wie machen wir das? Wir geben einfach das letzte zurück, weil das letzte Element in der Liste anzeigt, dass es für den Betrag von 5 ist. Das war's also. Grundsätzlich haben wir gerade die Wege bei zurückgegeben. Und jetzt, wenn wir zurückgehen und es wieder ausführen, werden wir sechs geben an, dass wir sechs Möglichkeiten haben, zu implementieren oder zu MD ja, um diese Funktion zu implementieren oder $5 von diesen vier Arten von Rechnungen zu haben. Das ist es im Grunde für die Python Implementierung. Davon abgesehen, das ist das Ende dieses Videos. Wir sehen uns in der nächsten. 16. Knapsack: Also, in diesem Video, was wir tun werden, ist eines der bekanntesten Probleme in der dynamischen Programmierung zu übergehen . Und es ist bekannt als das Rucksackproblem. Und dieses Problem hat eigentlich zwei Versionen davon. Die erste ist die Bruchversion und die andere ist die diskrete. Nun, was wir tun werden, ist ein Beispiel zu durchlaufen. Und wir werden diese beiden Versionen besprechen und wir werden etwas über eine von ihnen lernen. Und es ist tatsächlich mit dynamischer Programmierung gelöst worden. Also, um es zu gehen, Lassen Sie uns mit Beispiel beginnen. Die Idee dieses Problems ist, dass Sie einige Artikel oder Produkte haben, und jeder einzelne dieser Artikel hat ein Gewicht und einen Wert. Nehmen wir an, dass wir vier Elemente haben. Die erste, also schreibe ich sie einfach hier. Also wird der erste ein Gewicht fünf sein. Die zweite wird von Gewicht sein, für die dritte wird drei erwartet werden, und die letzte wird auch von Gewicht sein. Also hier sind wir. Wir haben vier Produkte, die alle diese Möglichkeiten haben. Jetzt müssen wir die Menge oder den Wert dieser Produkte hinzufügen. Der erste wird also ein Wert 28 sein. Also $28, der zweite wird ein Wert 20 sein. Der dritte wird bei 18 sein, und der letzte wird 11 sein. Also 18 und 11. Nun, das eigentliche Problem ist, dass Sie gehen, um diese Elemente neben einem bestimmten Gewicht, das Sie halten können gegeben werden. Nehmen wir zum Beispiel an, dass Sie eine Tasche haben. Und in dieser Tasche können Sie nur bis zu 10 Gewicht halten. Sie müssen also alle diese Produkte erhalten und bis zu 10 addieren. Also nehmen wir an, dass Sie hier Tasche haben. Und in dieser Tasche können Sie nur zehn halten. So kann jetzt die fraktionierte Version dieses Problems tatsächlich mit gierigen Algorithmen gelöst werden. Und in diesem Fall sehen wir es hier. Also, was wir tun werden, ist, dass wir einen Bruchteil dieser Gegenstände in Gewicht nehmen können. Also, anstatt den ganzen Gegenstand zu nehmen, so haben wir hier das Gewicht für wir tatsächlich Bruchteile davon nehmen können. Also zum Beispiel, wenn wir das von hier aus haben wollen, also haben wir 10, was wir tun werden, ist, diese Beträge über die Werte zu teilen und das Maximum davon zu nehmen. Zum Beispiel, wenn Sie 28 über fünf haben, werden wir etwas wie 5.6 bekommen. Lassen Sie mich es hier schreiben. Der zweite wird fünf sein. Der dritte wird 18 über drei sein, das wird sechs sein. Und der letzte wird eigentlich 5,5 sein. Jetzt können wir es immer mit der maximalen Menge lösen. Also, um dieses Gewicht von 10 zu füllen, was wir tun werden, ist, all diese drei von hier zu nehmen. Also werden wir diese drei nehmen, da sie den höchsten Wert in Bezug auf die Menge über Gewicht haben . Und diesen Fall werden wir all diese nehmen, also summieren Sie sich auf $18. Nun, wir werden fortfahren, indem wir dieses, das fünf ist, nehmen. Also, wenn wir hier zurück gehen und diese fünf hinzufügen, die ungefähr $28 sein wird. Und weil es den höchsten Wert hat. Denken Sie nun daran, dass der Zweck dieses Problems darin besteht, es zu lösen oder ein Gewicht von zehn mit einer maximalen Menge an Geld zu haben. Jetzt in diesem Fall haben wir 18 plus 28. Und schließlich, was wir tun werden, ist, diese 5.5 zu nehmen. Also, wenn du dich hier erinnerst, haben wir 532. Nun, wenn wir 11 nehmen, werden wir mit etwas wie 11 oder 18 plus 28 plus 11. Also das ist, das Gewicht ist drei plus fünf plus zwei, und es ist gleich 10. Nehmen wir an, wir haben kein Gewicht von zehn. Also, anstatt ein Gewicht von 10 zu haben, werden wir ein Gewicht von neun in diesem Fall haben. Und wenn wir dieses Problem mit einem Gewicht von neun lösen wollen, werden wir am Ende dasselbe haben wie zuvor. Allerdings wollen nicht hier zwei tut zwei plus drei plus fünf ist neun. In diesem Fall. Wenn wir zu dieser Position kommen, werden wir einen Bruchteil dieser beiden nehmen. Anstatt Net als Ganzes zu nehmen, können wir einen Bruchteil davon nehmen. Also werden wir einen Bruchteil von zwei nehmen. Also werden wir nicht das ganze Werkzeug nehmen, um einen Bruchteil zu nehmen, das heißt, Sie können einen nehmen. Und in diesem Fall wird der Wert 5,5 sein. Also sind es 11 über 2, das ist 525. Jetzt ist die ganze Menge oder das ganze Gewicht 3 plus 5 plus 1, was ist. Eigentlich gleich neun. Und in diesem Fall können wir einen gierigen Algorithmus verwenden, der nach etwas oder dem Wert sucht, dem größten Wert, den wir haben. So zum Beispiel, hier haben wir sechs, Good Nimm all diese. Dann prüfen wir, ob wir noch einen Platz haben. Natürlich werden wir einen Platz haben, da wir nur das Gewicht von drei hinzugefügt haben. Also neun minus drei, wir haben noch sechs übrig. Wir werden all das nehmen. Dann haben wir nur noch einen übrig. Wir gehen und suchen zwischen 55.55,5 ist größer und wir werden es als die größte nehmen. Und natürlich können wir einen Bruchteil davon nehmen, nicht den ganzen Betrag. Das ist also die Idee eines Bruchrucksacks. Und das ist eigentlich, das funktioniert eigentlich nicht, wenn wir einen diskreten haben. Stellen Sie sich vor, wir haben einen diskreten Rucksack. Und in diesem Fall können wir damit arbeiten, denn sobald wir diese Phase hier erreicht und wir 35 haben, dann haben wir noch eine übrig. Und diesen Fall können wir diesen hier nicht teilen. Also die optimale Lösung tatsächlich Haze vier plus fünf zu verwenden und zu warten. Und natürlich werden wir am Ende mit 48 statt 18 plus 28. In diesem Fall. Wie wir sehen können, die diskrete Version dieses Problems muss die diskrete Version dieses Problemsverwendet werden, um dynamische Programmierung als Lösung dafür zu haben. Und das heißt im Grunde für den fraktionierten Rucksack, Sie können immer den gierigen Algorithmus damit verwenden, aber wir behandeln das Merkmal nicht jetzt, wir wollen eigentlich nur mit der diskreten Version arbeiten, wo wir die dynamische Programmierung haben. Also lassen Sie mich das alles von hier löschen. Nun, für die diskrete Version, haben wir hier auch zwei Versionen. Wir haben die unbegrenzte Menge und die begrenzte Menge. Also hier, wenn es als ohne Wiederholung bekannt ist. Lassen Sie uns kurz darüber reden. Für die unbegrenzte Menge bedeuten sie, dass wir eine unbegrenzte Menge an diesem Artikel, diesem Artikel, diesem Artikel und diesem Artikel haben. Bis zur begrenzten Menge, die ohne Wiederholung ist,haben wir jedoch die ohne Wiederholung ist, nur eines dieser Artikel, E1, Produkt dieses Artikels, eines davon und eines davon. Also können wir das hier nicht mehr als einmal benutzen. Nun, was wir tun werden, ist, dass wir ein Beispiel haben und die unbegrenzte Menge neben der begrenzten oder ohne Wiederholung durchlaufen werden. Also lassen Sie uns eine Sekunde darüber nachdenken. Wenn wir dieses Beispiel hier haben, lassen Sie mich es Ihnen beibringen. Und lassen Sie mich eigentlich all diese nehmen und sie kleiner machen und hierher kommen. Und ich werde genau das gleiche tun, auch dafür. Und ich habe sie hier hingelegt. Jetzt können wir unsere Arbeit fortsetzen. Nun stellen wir uns vor, dass wir unbegrenzt oder die ohne die Petition, eine, die mit der saß, ohne die Wiederholung. Also ohne Wiederholung, was wir tun werden. Also hier haben wir ohne, wir werden diese drei nehmen, die die höchste ist. Also nochmal, nimm diese drei. Denken Sie nun daran, dass wir ein Gewicht von zehn brauchen. Also haben wir diese drei plus diesen, plus diesen einen von fünf. Nun, wenn wir alle diese hinzufügen möchten, so hier haben wir 18.11.28. In diesem Fall werden wir mit $57 als endgültigen Wert enden. Und es wird das höchste für das ohne die Wiederholung LFO sein. Und berechnen Sie einfach diese 13 plus zwei plus fünf, was gleich 10 ist. Also sind wir jetzt gut mit unbegrenzter Menge, aber wir können tun, ist, also lassen Sie mich einfach die Farbe hier ändern. Also hier haben wir die unbegrenzte. Schauen wir uns mal an. Stellen Sie sich also vor, dass wir mehr als 13 haben, also haben wir 3 plus. Kann auch weitere drei verwenden, die bis zu sechs addieren. Und wir können in diesem Fall auch zwei zwei verwenden. Also, jetzt, wenn wir es berechnen, so hier haben wir drei plus drei, so dass drei $18 ist. Hier auch 18, wir haben 11 und 11. Wie Sie sehen können, wird sich dies in $58 verwandeln, was besser als die alte sein wird, wenn wir unbegrenzte Menge haben. Und unter der Annahme, dass wir die gleiche Anzahl oder die gleichen Gewichte und die gleichen Mengen haben. In diesem Fall ist es, wie Sie sehen können, besser, die unbegrenzte Menge oder die Breitenwiederholung hier zu verwenden. Das sind also die beiden Versionen, die wir in der diskreten Version des Rucksackproblems haben. Und wir werden uns auf sie konzentrieren. Und wir können sie auch mit dynamischer Programmierung und den nächsten paar Videos lösen. So sehen wir uns dann. 17. Knapsack: Alles klar, in diesem Video werden wir uns auf die diskrete mit unbegrenzter Anzahl der Version des Rucksackproblems konzentrieren . Um das zu tun, lassen Sie mich das alles von hier löschen. Und er ist auch ein Indikator. Und lass mich das alles nehmen, sie kleiner machen und sie hier weglegen. Und ich mache genau das Gleiche. Diese Sorte ließ mich sie einfach mitnehmen und sie hier platzieren. So können wir jetzt mit unserem Rucksackproblem mit Wiederholung mit unbegrenzter Menge oder Artikeln beginnen. Also in diesem Fall, wenn wir es betrachten wollen, schauen Sie es sich an, auf diese Weise werden wir mit etwas enden, das gleich ist. Also hier haben wir $58 insgesamt. Bedenken Sie also diese Nummer für Daten. Nun, was wir tun werden, ist, dass wir ein Array oder eine Liste verwenden, um zu versuchen, dieses Problem zu lösen und eine richtige Lösung mit dynamischer Programmierung zu finden. Also, was wir tun werden, ist, dass wir die Menge oder das maximale Gewicht, das wir haben, nehmen , das ist 10, und erstellen eine Liste, zehn plus eins als Größe. Lassen Sie mich einfach erstellen, und das ist unsere Liste. Und was wir tun werden ist, dass wir all diese aktualisieren werden, jedes Mal, wenn wir sie durchlaufen. Jetzt lasst uns darüber nachdenken. Was wir tun wollen ist, dass wir können, wir müssen die maximale Menge an Geld mit diesen haben, vorausgesetzt, wir haben 10 als Gewicht. Also werden wir all diese nutzen. Wir haben eine begrenzte Menge und wir werden unbegrenzte Menge zu verwenden , und wir müssen die maximale Menge an Geld zu finden. Fangen wir mit 01 an. So hoch wir sehen können, wir haben nichts und wir verwenden kein Bruchteil, also können wir das teilen. Also, was wir tun werden, ist einfach 00 hier zu schreiben. Lassen Sie mich die Farbe ändern. Jetzt haben wir zwei und wie wir sehen können, können wir verwenden, und die Kosten werden $11 sein. Denken Sie nun daran, dass wir für jetzt diskutiert maximieren müssen, können wir nichts anderes als diese 11 für die beiden verwenden. Nun, wenn wir den ganzen Weg bis 2, 3 gehen , und schauen wir uns die drei an. Wir haben 18 Dollar, die größer als 11 sind, also können wir hier mit 18 arbeiten. Entschuldigen Sie, lassen Sie es mir besser schreiben. Also haben wir drei, die insgesamt 18 sein werden. Nun, wenn wir in den Vordergrund gehen, wie wir für die, zum einen sehen können, haben wir hier den Wert von 20. Jetzt in diesem Fall zwanziger Jahre größer als 11 und 18. Also werden wir hier 20 schreiben. Wenn wir jetzt zu den fünf gehen, haben wir mehr als eine Option. Schauen wir uns in diesem Fall an. Wir können entweder zwei haben und eine drei hinzufügen, die 11 plus 18 sein wird, was tatsächlich 29 sein wird. Oder, es tut mir leid, oder wenn wir drei haben und wir hinzufügen, werden zwei auch das Ergebnis von 29. Also, was wir tun werden, ist, einfach hier zu schreiben 29. Denken Sie also daran, was wir getan haben, ist entweder 2 plus 3 oder 3 plus 2. Und wir werden 29. Jetzt, wie das Geschlecht, der Gesamtwert oder der Maximalwert, den wir bekommen können, um 3600 sein. Erklären Sie es in einer Minute. Mile, denk so darüber nach. Sie können auch alle diese Informationen direkt hier haben. Also lasst uns über diese fünf und diese fünf nachdenken. Beachten Sie, dass diese Datei die optimale Lösung für die maximale Menge ist, die 29. Denk jetzt darüber nach, als ob wir eine Fünf haben und wir werden eins hinzufügen, um es zu einem Gewicht von sechs zu machen. Und in diesem Fall gibt es nichts, was wir hinzufügen können, um auf diese Weise mehr als 29. Und in diesem Fall werden wir uns vier ansehen. Also schauen wir uns vier an. Wenn wir hier 20 haben, was können wir dann von hier aus hinzufügen, um es größer als 29 zu machen? In diesem Fall, wenn wir es betrachten, können wir zwei von hier hinzufügen, die den Wert 11 hat. Also 20 plus 11, wird es gleich 31 Nazi sein. Lasst uns jetzt über diese Reise nachdenken. Also haben wir drei. Was können wir vielleicht zu drei hinzufügen? Sex als Menge zu haben war oder als Gewicht. In diesem Fall, was wir weitere drei hinzufügen können, die auch insgesamt $18. Also 18 plus 18 zu 36 sein, das ist größer als 31. Also werden wir das löschen und Sie werden 36 verwenden. Jetzt werden wir auch den ganzen Weg zurück zu diesem gehen. Also werden wir uns die gleiche Frage stellen. Was können wir hinzufügen, zu, um es sechs zu machen? Und zum Glück haben wir diese vier hier, was der Wert von 20. Also, wenn wir es verwenden wollen, können wir den Wert von zwei hinzufügen, 11 plus 20 ist, um uns auch 31 zu geben, was nicht der optimale Wert ist, haben bereits einen optimalen Wert, der 36. So können wir das berechnen. Nun, zum siebten, und wie wir sehen können, haben wir 36, aber wir können nichts hinzufügen. Also, wenn wir es hier benutzen wollen, können wir es. Also lass mich das vorerst versuchen, 36. Nun, wenn wir zu dieser Datei zurückgehen, wenn wir 29 haben, und wir fügen diese zwei hinzu, also fünf plus zwei, um uns sieben zu geben. Also 2029 plus 11, es wird uns tatsächlich 40 geben, die größer als 36 ist. Also werden wir es benutzen. Und natürlich können wir den ganzen Weg zurück zu den 4, 3 und 2 gehen , aber das ist die optimale Lösung und Sie können es selbst ausprobieren. Jetzt gehen wir zur Hilfe. Diese Hilfe, die optimale Lösung wird 47 sein und es wird tatsächlich 36 plus diese aus den beiden, die 11 ist, also 36 plus 11 ist 47. Dann haben wir die optimale Lösung für das Gewicht von neun, das 454 ist. Und schließlich 58 für die letzte, die tatsächlich diese Kante von hier verwendet, die optimale Lösung von acht plus Hinzufügen dieser beiden von hier, die einen Wert von 11 hat, also 47 plus 11, die wird uns 58. Und wie Sie sehen können, haben wir das gleiche exakte Ergebnis wie zuvor. Das war's also. So können wir den maximalen Betrag mit der dynamischen Programmiermethode erhalten. Ich weiß, dass, wenn Sie gehen, um das Rucksackproblem zu lösen, und wenn es ein kleines Problem hat, kann es einfach durch Kopf lösen. Du brauchst das nicht wirklich. Aber was passiert, wenn Sie vielleicht 10 oder 15 Produkte oder Artikel hier haben? Man kann nicht wirklich nur darüber nachdenken und die richtige Lösung finden. Das ist also der richtige Weg. So können wir es mit der optimalen Lösung berechnen, die wir bekommen können. Also, das ist es im Grunde für dieses Video. Und der nächste werden wir Pseudocode schreiben. Und wir werden tatsächlich eine Formel finden, die wir hier verwendet haben. Das ist also das Ende dieses Videos. Wir sehen uns im nächsten. 18. Knapsack: Okay, jetzt, da wir eine Vorstellung über das Rucksackproblem mit Wiederholung haben, lassen Sie uns eine tatsächliche Formel oder Lösung für dieses Problem in Form von Pseudocode einfallen . Nun, in diesem Fall, was wir tun werden, ist zuerst definieren unsere Parameter. Was wir also bekommen werden, sind drei oder vier Parameter. Ich werde über sie reden. Also der erste wird eigentlich das Gewicht sein, das wir brauchen werden. Also, was wir tun werden, ist, hier w zu tippen also das ist der erste Parameter. Der zweite wird die tatsächlichen Werte wie 54 sein, es tut mir leid, wie 282809, 11. Das wird also ein Array sein. In diesem Fall bezeichnen ich sie einfach mit Val. Es ist also eine Liste oder ein Array. Nun, dieser dritte wird die tatsächlichen Gewichte sein. Also werde ich nur versuchen und Breite. Und natürlich wird es ein weiteres Listenfeld sein. Und natürlich wäre das endgültige die Größe der Länge dieser Datei und Gewichte. Also werde ich einfach mit n. in Ordnung, also wofür steht das? Also Val und Wellen sollten gleich sein. Beispiel: val bei 0. Wir haben, in diesem speziellen Beispiel, wir haben den Wert 28 und wartet auf 0. Wir haben den Wert von fünf. So können wir auf sie zugreifen, da sie den gleichen Index haben. Also 28, 524, 18, 3, 11 und 2. Das ist also ein, im Grunde das ist, was wir jetzt bekommen werden, lassen Sie uns darüber in einer dynamischen Programmierung nachdenken. Das erste, was wir tun werden, ist, dieses Array zu erstellen, richtig? Und die Semi ist eigentlich von Größe w plus eins, wie wir gesagt haben. Also habe ich einfach als eine Bezeichnung bezeichnet, die die maximale Kapazität ist, die wir bekommen können. Also wird unser Array MA sein, und natürlich sollte seine Größe sein. Also das ist das Array oder die Liste und der Größe Tune dieses Gewicht plus 1. Also w plus eins. Nun erinnern Sie sich, dass, als wir den Stempel als Gewicht hatten, wir dieses Array von Länge zehn plus eins erstellt haben. Also das ist Länge 11, den ganzen Weg von Index 1, Index 0, tut mir leid, bis zum Ende von Index 10. Nun, das ist unser Array namens MA. Jetzt können wir anfangen, zwei verschachtelte for-Schleifen zu formulieren oder durchzugehen und diese Werte hier zu aktualisieren. Also lassen Sie mich einfach ein paar davon auflisten. Löschen Sie diese. Ich werde all diese nehmen und sie kleiner machen. Ich glaube, wir brauchen sie vorerst nicht. Ich füge sie einfach hier hinzu. Jetzt wird das zweite sein. Das ist also das erste, was wir tun werden und unser Code. Denken Sie nun daran, dass wir eine Liste oder ein Array erstellen möchten , das die optimalen Werte für jedes spezifische Gewicht enthält. Der optimale Wert hier für dieses Gewicht von 0 ist beispielsweise 0. Die optimale Rate von eins ist 0. Das optimale Gewicht von 2 beträgt 11 und so weiter und so weiter. Also natürlich, wenn wir zu diesem Punkt kommen, und das ist die Sechs. Und wir haben den Bildschirm von hier aus verwendet, wir verwenden 18 plus weitere 3, das ist 36. Wir wussten, dass dies der optimale Weg ist, den wir für diesen Wert von drei bekommen können. Und natürlich ist das sehr wichtig, weil die Werte voneinander abhängig sind. Also zum Beispiel, wenn dies nicht der optimale Weg für diesen Wert von drei ist, und wir haben es im Sex verwendet als, daher ist diese sechs nicht der optimale Weg auch. Das heißt, das ist die Idee dahinter. Wir wollen nur den optimalen Weg für jedes Gewicht bis zum Ende machen. Und natürlich werden wir auch mit einem optimalen Weg enden. Was wir jetzt tun werden, ist mit unseren for-Schleifen zu beginnen. Der erste, wir gehen von 0 bis zum Ende dieses Gewichts. Also wird es von 0 bis W. Nun, natürlich ist das Kapital W. Und dann, was wir tun werden, ist zu gehen und eine andere for-Schleife. Und diese Formel wird ein Wert j sein. Jetzt wird dieses j von 0 bis zum Ende gehen. Also werde ich in einer Sekunde darüber reden. Wenn du darüber nachdenkst, was wir im Grunde tun, ist, dass wir uns durchmachen. All diese eins nach dem anderen. Und jedes Mal, wenn Sie zum Beispiel ein Zweier sind, werden wir alles hier durchschauen. Also werden wir 5, 4, 3 und 2 durchschauen. Also sollten diese Gewichte, wir sollten auf sie zugreifen. Und wir können auch auf diese Werte zugreifen, indem wir die gültigen, über die wir zuvor gesprochen haben. Das war's also. Grundsätzlich haben wir unser Val und Abfälle und wir können auf sie innerhalb dieser beiden for-Schleifen zugreifen. Und was wir tun werden, ist zu überprüfen, ob dieses Gewicht bei einem bestimmten Index von j, richtig? So Gliedmaße, denken Sie daran, dass wir loppen , durchschleifen dies mit j Also auf diese Weise, bei einem bestimmten Index ist kleiner oder gleich den tatsächlichen Gewichten, die wir durchmachen, dann können wir etwas tun. Sonst spielt es keine Rolle und macht keinen Sinn, sich zu ändern. Lassen Sie uns zum Beispiel eines der Beispiele durchgehen. Nehmen wir an, wir sind hier auf einem. Was wir tun werden, ist, all diese zu durchlaufen. Nun, was wir sagen werden, ist, wenn diese fünf kleiner oder gleich eins sind, dann werden wir etwas tun. Jetzt. Daran erinnern, dass fünf nicht größer als und nicht weniger als eins ist. Was wir also tun werden, ist, es einfach zu ignorieren, da wir die S1 davon abhalten können, diese fünf zu verwenden. Nun, was du tun wirst, ist, all das bis jetzt durchzugehen, 432. Und wir werden sehen, dass sie nicht weniger als eins sind. Also natürlich werden wir es ignorieren, so dass die 0 ruhen, wie sie sind. Nun, was wir tun werden, ist ein anderes Beispiel zu durchlaufen. wir uns, ob diese zwei weniger als fünf sind, tut es Also fragenwir uns, ob diese zwei weniger als fünf sind, tut esmir leid, wenn diese zwei größer als fünf sind, dann wird es nichts tun. Diese beiden sind größer als vier oder drei. Nein. Dann ist diese zwei größer als oder gleich 2. Ja. Also können wir das hier nutzen. Also fügen wir den Wert hinzu, den wir hier haben , der 0 tatsächlich zu diesem Wert von hier hinzugefügt wurde. Das war's also. Im Grunde ist es, wie wir es tun können. Versuchen wir es nun mit dem letzten Beispiel. Nehmen wir zum Beispiel an, wir sind bei vier. Lassen Sie uns fragen, dass es 4 größer als 5 ist? Nein, wir können es nicht benutzen. Ist für größer als vier, größer als oder gleich Eigentlich, ja, ist es. Also, was wir tun werden, ist, diese 4 zu nehmen und darauf zuzugreifen. Natürlich, mit der, so zum Beispiel, wir sind hier bei diesem, für das, was wir tun werden, ist zu schreiben, lassen Sie mich die Formel schreiben. Was wir also bekommen, ist, dass wir diesen Wert um vier in etwas anderes aktualisieren werden. Das ist MA, bei dem Gewicht, das wir hatten. Das ist also die Art und Weise, mit der wir arbeiten, abzüglich des Gewichts, das wir nehmen werden. Und in diesem Fall ist es vorher. Natürlich ist dies nicht definiert Formel. Wir müssen diesen Wert hier von der Standardeinstellung hinzufügen, die wir erhalten. Also ist es plus 20, ich bin ein f bei 0 tatsächlich. Das ist also 0 MA bei 0. Wir werden es anschauen und es ist 0. Also 0 plus 20, wir werden 20. Lassen Sie uns eine Sekunde darüber nachdenken. Was haben wir hier gemacht? Nun, wenn Sie es tatsächlich getan haben, ist, dass wir auf Gewicht für jetzt, denken Sie daran, dass Sie ein Gewicht von vier brauchen. Und natürlich, wenn Sie das Gewicht von vier von hier bekommen wollen, müssen Sie tatsächlich 0 Gewichte haben und diese vier hinzufügen, um ein 284 zu sein, oder? Also zum Beispiel, wenn Sie das Gewicht von drei hinzufügen, müssen Sie ein Gewicht von eins haben, dann fügen Sie es drei hinzu, wir bekommen dieses Gewicht von vier, oder? Das war's also. Im Grunde ist es, wie Sie es berechnen können. Denken Sie nur darüber nach, dass, wenn Sie dieses Gewicht von vier hinzufügen wollen, woher würden Sie lieber vorher beamen, um diese Position genau hier anzukommen? Und die eigentlich, die, die eigentliche Lösung ist ziemlich unkompliziert. Sie sollten sich bei Index 0 befinden. Fügen Sie ihm diese vier hinzu. Von hier aus kommen wir zu ihm. Deshalb fügen wir diesen Wert von hier in den von hier. Und dann werden wir es um 20 Uhr hier haben. Das ist also die Idee dahinter, wie wir uns versammeln können. Jetzt denken wir an eine andere, eine andere Schleife. Nehmen wir an, wir sind bei drei. Wir werden uns fragen, ob vier größer oder gleich drei ist. Ja, das ist es. Was wir tun werden, ist, um vier Uhr MA zu nehmen. Wir werden es aktualisieren. Natürlich werden wir es nicht tun, wenn es weniger ist als diese 20 von hier. Natürlich. Also haben wir hier unsere 20. Lassen Sie mich es einfach hier zeigen. Also hier haben wir, wir hatten schon 0, richtig? Nun denken wir darüber nach, da es 20 größer als 0 ist. Ja, wir sollten es aktualisieren. Also hier haben wir 20. Nun, wenn wir an diesem Baum sind, werden Sie uns fragen, es größer als vier ist? Es tut mir leid, Es ist großartig für größer als oder gleich drei. Ja, das ist es. Wir können es aktualisieren. Jetzt müssen wir den Wert überprüfen. Wenn es größer als 20 ist , können wir diese aktualisieren. Wenn nicht, dann macht es keinen Sinn, zu aktualisieren. Jetzt schauen wir es uns an. Was werden wir tun? Also sagen wir, dass MA bei vier gleich MA bei diesen vier minus drei plus dem Wert, den wir von hier bekommen, der 18 ist. Jetzt ist der Wert bei M, ein vier minus drei, was ein 01 ist, es tut mir leid, auch 0. Also werden wir 0 plus 8 hinzufügen, was gleich A1 ist. Jetzt werden wir überprüfen, ob 20, weniger als 18. Nein, ist es nicht. Also werden wir den Schweiß 20 behalten und diesen ignorieren. Und natürlich werden wir weitermachen. Also haben wir diesen noch übrig. Und natürlich werden wir sagen, dass MA bei, für vielleicht gleich MA bei 4 minus 2 plus den Wert, den wir hatten, der 11 ist. Also, ist das der Fall? Also bin ich ein zu zwei, es ist eigentlich elf. Also werden wir 11 plus 11 bekommen, was eigentlich 22 ist, was auch größer ist als diese 20. Damit wir es hier aktualisieren können. Das war's also. Im Grunde ist das die ganze Idee darüber. Dies ist die allgemeine Idee über dieses Rucksackproblem. Nun, was wir tun werden, ist, es einfach besser und absoluter Code aussehen zu lassen. Also haben wir bereits diese Formel hier, aber glücklich, nur gelöscht und nochmals schreiben. Und nette Art und Weise. Was wir sagen werden ist, dass wir alle Gewichte durchschleifen. Dann schleifen wir uns durch alle Abfälle von hier für jeden Weg, den wir in unserem Array haben. Und wir werden überprüfen, ob das Gewicht von hier an diesem spezifischen Index. Also Gewichte und j als oder gleich der Art, wie wir hier haben, was ich eigentlich ist . Wenn dies der Fall ist, werden wir etwas aktualisieren. Aber wir werden zu aktualisieren ist eigentlich die Art und Weise, wie wir MDMA haben, um es zu erstellen. Also MA und dieser spezifische Index, der ich ist, sollten gleich dem Maximum zwischen zwei Dingen sein. Es sollte also gleich dem Maximum zwischen dem ersten sein, der MA bei i ist. Es ist also das Maximum zwischen sich selbst oder dem MA bei I minus den Gewichten bei j. Natürlich, nachdem wir von diesem beendet haben, werden wir zu Fügen Sie den Wert hinzu, der im Array val von hier ist. Also werden wir einen Wert bei j hinzufügen. Nun lassen Sie uns eine Sekunde darüber nachdenken. In diesem Fall werden wir sagen, dass wir es sind, wenn wir zum Beispiel dabei sind, und wir sind hier bei diesen vier. Also vier ist größer als oder gleich vier. Dies ist es mit einem J, das ist, wie wir auf die Partitur zugreifen, ist 4. Dieser ist größer als oder gleich den Gewichten bei j. Ja, wir werden sie a bei vier aktualisieren. In diesem Fall sollte die MA bei vier, es sollte gleich dem tatsächlichen Wert und der MA bei vier sein, oder der MA bei vier minus vier, das ist 0, plus dem Wert an diesem spezifischen Index, der 20 ist. Das war's also. Im Grunde ist das die Formel. Und natürlich sollten Sie immer damit beginnen, über das Array nachzudenken, das Sie zuvor entworfen haben, dann eine tatsächliche Lösung finden. Versucht, darüber nachzudenken, wie wir die Werte von vorher und unsere tatsächlichen Indizes hier verwenden. Und tatsächlich müssen Sie wirklich alle Beispiele durchlaufen , um das eigentliche Muster dieser Formel zu sehen. Das ist also das Ende dieses Videos. Wir sehen uns. 19. Knapsack: Oh, okay, in diesem Video werden wir das Rucksackproblem mit Wiederholungen lösen. Also das erste, was ich tun werde, ist eine Funktion zu erstellen. Es wird also öffentlich, statisch sein. Und ich werde ihn Rucksäcke nennen. Dann werden wir die Parameter auf die erste bekommen sollte das Gewicht sein, wie gesagt, der zweite sollte die Länge der Werte und der Elemente sein. Dann haben wir den Wert, Werte, und dann haben wir das Gewicht. Öffnen wir es jetzt. Und jetzt, was wir tun werden, ist, unsere eigentliche Liste zu erstellen. Das ist die, MA. Wir werden es als Array definieren. In diesem Fall eine intime. Und um Zeichen von W plus eins zu haben, sagten wir. Und natürlich sollten alle diese in Java standardmäßig Nullen sein. Also kümmern wir uns nicht wirklich darum, die erste auf 0 zu setzen und so weiter und so weiter. So können wir dies überspringen und direkt mit unserer for-Schleife beginnen. Für die erste wird bei I gleich 0 und den ganzen Weg bis zum Ende und inkrementiert sein. Dann sollte die zweite for-Schleife halb j sein und in diesem Fall werden wir den ganzen Weg bis zum Ende der Werte und Gewichte gehen. Dann werden wir es aktualisieren. Und natürlich, was wir jetzt tun werden, ist zu überprüfen, ob diese Gewichte kleiner oder gleich der Art sind, wie wir durchmachen. Dann werden wir den Wert innerhalb dieser Formel aktualisieren, innerhalb dieser Liste. Das ist es also. Wir werden nur das benutzen, das wir vorher benutzt haben. Also lass mich einfach zurückgehen und es hier aufschreiben. Also, wenn Gewichte bei j kleiner oder gleich dem Gewicht oder dem Auge ist. Denken Sie nun daran, dass ich für das Gewicht, das tatsächliche Gewicht steht. Also, wenn wir bei mir gleich vier sind, bedeutet das, dass wir haben, das heißt, dies ist der Weg, der repräsentiert. Schließlich werden wir mit dem letzten Weg enden, den wir brauchen, der zehn ist. Und das ist es, was wir eigentlich anstreben. Also, wenn das Warten, es tut mir leid, wir haben einen Tippfehler. Also, wenn Gewichte bei j kleiner oder gleich ist, I, kann PMAs für Bürgermeister Krawatte aktualisieren sollte gleich Maximum zwischen zwei sein. Also, was wir tun werden, ist Mad Max zu benutzen. Und natürlich werden wir es benutzen. Entweder bin ich ein at i oder etwas anderes, das bei i. Wie wir gesagt haben, fünf, subtrahieren wir einfach die Gewichte bei j und natürlich werden wir den Wert von den Werten bei j hinzufügen . Im Grunde ist es, wie wir es aktualisieren können. Und hier haben wir einen Tippfehler. Lassen Sie mich es einfach klären. Sie sagten, im Grunde ist dies unsere Formel, so können wir es aktualisieren, verwenden Sie einfach diese Formel von hier. Nun, was wir tun werden, ist, einfach die letzten in der Liste zurückzugeben. Also geben Sie ein a bei dem tatsächlichen Gewicht zurück, das wir wollen. Jetzt lasst es uns hier benutzen. Also, um einfach eine Hauptfunktion zu erstellen, werde ich nur einige Parameter definieren. Nehmen wir an, lassen Sie uns das gleiche genaue Problem oder die gleichen genauen Parameter von hier aus verwenden . Also haben wir das Gewicht gleich 10, dann haben wir die Werte, die 5, 4, 3 und 2. Es ist also ein geringeres Array. Die Werte sollten 5, 4, 3 und 2 lauten. Dann werden wir zu den tatsächlichen Gewichten zu bewegen, die auch ich kann einfach kopieren, dass von hier, 28201811, also 2828 und 11. Dann werden wir am Ende mit den Werten, die Länge. Und natürlich, das ist natürlich, was wir jetzt tun werden, ist, die eigentliche Funktion aufzurufen. Also lassen Sie mich einfach hier ausdrucken. Also System dot out, dot print zu drucken ist tatsächlich der Rucksack. Also werde ich diese Funktion direkt hier mit, neben den folgenden Parametern, also w-Werten aufrufen. Und jetzt, was wir sagen, nun, wir haben ein Problem hier. Lassen Sie mich es einfach überprüfen. Methode. Es ist kein Spielbuch. Ok. In Ordnung. Also haben wir sie einfach vergessen. Wir sollten diese öde hinzufügen Grundsätzlich jetzt, wenn wir voran gehen und dieses hier laufen. Also haben wir 0, lassen Sie mich Werte und Gewichte überprüfen. Ok? Also ich, okay, hier haben wir Gewichte und Sie werden Werte haben. Ist nur irrtümlich umgeschaltet. Wenn wir es jetzt noch einmal ausführen, werden wir 58 bekommen, was genau das gleiche Ergebnis ist, das wir hier und hier gefunden haben. Also sahen wir das auf drei Arten. Der erste ist, unsere Gedanken zu benutzen und nur darüber nachzudenken. Dann benutzen wir das hier und wir haben 58. Und schließlich haben wir es in unserem Code verwendet. Also höchstwahrscheinlich ist dies der richtige Weg. Nun, was wir tun werden, ist, es nur ein letztes Mal zu visualisieren. Wir werden das ganze Array visualisieren. Anstatt zurückzukehren, rufen Sie einfach eins an, ich werde ein Array zurückgeben. Und natürlich werde ich eine for-Schleife erstellen, oder? - Ja. Entschuldigung. Zu lange ist es also, all dies zu durchlaufen. Also werde ich es auch hier nennen, MHC2, und ich bin ein Rucksack von W und Werten und Gewichten. Jetzt gehen Sie den ganzen Weg, um eine Länge zu sein. Und natürlich drucken wir sie aus. Also werde ich einfach ausdrucken und mit dem Subraum Ihres Laufs es wieder, werden wir genau das gleiche bekommen, was wir von hier bekommen haben. So haben wir vierundvierzig siebenhundert vierundfünfzig und achtundfünfzig. Also sagten sie im Grunde, dies ist für das Rucksackproblem mit Java. 20. Knapsack: Okay, Also in diesem Video werden wir den Rucksack mit Manipulationsproblem mit JavaScript lösen . Das erste, was ich tun werde, ist, unsere Funktion zu schaffen. Also die Funktion und nennen Sie es Knapsack. Ich werde die Parameter bekommen, damit wir die Länge der Gegenstände warten müssen. Du hast Werte und E. Jetzt lass es uns öffnen. Nun, wir werden tun, ist es, tatsächlich diese Methode oder diese weniger dehnbar und a. Also lassen Sie mich zurück und lassen Sie ihn ein neues Array von Größe n. Wir sagten, die Größe sollte das Gewicht, das wir plus 1 haben. Nun, was wir tun werden, ist, es mit Nullen zu füllen. Dann fangen wir mit unseren beiden verschachtelten for-Schleifen an. Also lass ich gleich 0, ich ist kleiner oder gleich dem Gewicht. Und ich plus Plus. Also machen wir nichts, aber dieses B wird hier diskutiert, also bekommen wir nur diese beiden for-Schleifen. Die erste von 0 bis w, Die zweite ist zwei. Und so dass N1, wir haben j gleich 0 den ganzen Weg bis zum Ende und j plus, plus. Dann werden wir überprüfen, ob die Gewichte, mit denen wir es zu tun tatsächlich kleiner oder gleich dem Abfall sind, den wir auf dieser Liste sind. Und das ist der Fall, dann müssen wir es aktualisieren mit sind nur kommen, um dies in JavaScript zu tun. Also, wenn Gewicht an der spezifischen und das ist kleiner als oder gleich dem Index, Ich erweiche es. Wir werden den MBA aktualisieren, wenn ich gleich dem Maximum zwischen zwei Dingen sein sollte. Sollte gleich dem Maximum zwischen sich selbst sein. Oder ich bin bei mir minus P-Wellen. Wie wir vorhin gesagt haben. Und natürlich werden wir auch den Wert aus der Werteliste bei i j hinzufügen. Also gibt es eine, im Grunde ist dies unsere eigentliche Funktion. Nun, was Sie tun werden, ist, nachdem Sie von diesen beiden for-Schleifen beendet haben, den MA am WWW zurückzugeben. Nun, wenn wir es einfach ausprobieren wollen, lassen Sie es uns laufen. Lasst uns eigentlich definieren. Also lassen Sie w gleich 10, werde das gleiche exakte Beispiel von ihm nehmen. Also w gleich 10, wir werden Werte haben, die gleich sind. Der tatsächliche Wert ist 28, 2018 und 11. Also Werte gleich 2828 und 11. Dann haben wir die Gewichte. Gewichtungen gleich ihm ist gleich tatsächlich 5, 4, 3 und 2. Dann werden wir n haben, was Werte Punktlänge ist. Dann, was wir tun werden, ist, die Funktion zusammen mit diesen Parametern aufzurufen. Also W und Werte und Gewichte. Und natürlich werden wir es auslegen. Also Konsolenprotokoll. Und wir bekommen, nachdem wir tun, ist tatsächlich nur oben und unten Eingabeaufforderung. Und dann werde ich zu meinem Verzeichnis in diesem Task-Desktop gehen, ich habe JavaScript genau hier. Ich kopiere das irgendwie und gehe rüber zu ihm. Und dann werde ich dieses Problem mit Knoten ausführen. So Knoten Rucksack mit Wiederholungen, die ab.js und wir haben ein und als Ergebnis, was darauf hinweist, dass dies keine Zahl ist. Also lassen Sie mich es mir überprüfen. Alles sieht gut aus für Haare und Maximum. Das Problem ist also, okay, also ist das Problem genau hier. Also haben wir, wir müssen es als Pluspunkt schließen. Nur so ist das die eigentliche Formel. Wenn wir jetzt zurückgehen und Annette wieder 58 als die maximale Zahl bekommen , die wir von dieser Formel bekommen können. Nun, was wir tun werden, ist, das alles auszudrucken. Also, anstatt nur den letzten zu haben, werde ich nur um dieses Problem willen. So, wie wir sehen können, was 000 011, 1822 betrifft. Und wenn wir hierher zurückgehen, können wir 000 011, 1822 sehen. Und natürlich ist es der ganze Weg zu 2936404912, das ist genau ein 293640 siebenundfünfzig vierundfünfzig achtundfünfzig. Damit können wir sicherstellen, dass unser Problem funktioniert und wir haben das gleiche Ergebnis wie das, das wir hier in dieser Liste manuell durchgeführt haben. Also das ist es, im Grunde ist es, um den Rucksack mit ihrer Petition mit Java-Skript zu implementieren. 21. Knapsack: Okay, Also in diesem Video werden wir den Rucksack mit Wiederholungsproblem mit Python lösen . Das erste, was ich tun werde, ist, die Definition oder die Funktion zu erstellen. Ich werde es Rucksäcke nennen. Und neben den Parametern, die wir verwenden werden. So wn-Werte und Gewichte. Jetzt lass es uns öffnen. Das erste, was in dieser Funktion, werden wir das eigentliche Listenfeld visualisieren, das MA hat, Organismus es, MA, und wer es nicht im Bereich von haben kann. So wird es von Nullen sein und es wird für mich im Bereich von w plus eins sein. So können wir diese Liste mit einer Codezeile in Python erstellen. Dann werden wir mit unseren beiden verschachtelten for-Schleifen beginnen. Also für ich im Bereich von W, Schwan, werden wir eine andere for-Schleife erstellen, die für j im Bereich von AMP ist. Dann fangen wir mit dem Zustand an. Also haben wir vorerst nichts getan. Wir haben gerade diese beiden for-Schleifen erstellt. Jetzt werden wir überprüfen, ob die Gewichte bei j kleiner oder gleich I ist. Also, wenn Gewichte bei j kleiner oder gleich i ist, wir die AMA bei I aktualisieren. Also kann ich hinzufügen, ich sollte gleich einem von zwei Dingen sein. Es ist das Maximum zwischen dem tatsächlichen Wert, den wir haben , oder dem Maximum oder dem anderen, das MA bei Pi minus Gewichte bei j plus dem Wert von j ist. Also max entweder bei MA bei oder bei der zweiten, die MA bei Gewichten bei j ist. Dann werden wir natürlich die Werte bei j hinzufügen. Das ist es im Grunde. Nun, was wir tun werden, ist, einfach den MA beim letzten zurückzugeben, der bei W ist da wir diesen hier einfach brauchen werden. Also werden wir es einfach zurückgeben, wie es jetzt ist, um es auszuprobieren, lassen Sie mich einfach Ihre Sachen erstellen. Wir werden das gleiche exakte Beispiel verwenden, das wir hier verwendet haben. Also w gleich 10, die Gewichte sind 5432. So Gewicht gleich einer Liste von 5432. Dann haben wir die Werte, die 28201811 sind. Dann haben wir schließlich die Länge dieser Gewichtswerte. Nun, was wir tun werden, ist, diese Funktion zu nennen und auszudrucken. So können Sie diesen Rucksack einfach neben diesen W-Werten und Gewichten drucken. Jetzt, wenn wir hier gehen und es ausführen, also werde ich Python neben dem Rucksack mit Wiederholungen eingeben und es ausführen. Und wir werden 58 als die maximal zulässige Anzahl für dieses spezifische Beispiel bekommen. Nun, um die tatsächliche Liste zu visualisieren, die wir hier erstellt haben, lassen Sie mich einfach anstelle von MA drucken und dann komme ich zurück und eine, die ganze Liste, anstatt das letzte Element zurückzugeben. Wenn wir jetzt zurückgehen und wieder auffrischen und laufen, werden wir 0011182258 bekommen. Und wenn Sie sie vergleichen, sind sie genau das gleiche wie das Beispiel, das wir zuvor getan haben. 01118, zweiundzwanzig neununddreißig sechsundvierzig, dann siebenundvierzig, vierundfünfzig und achtundfünfzig. Das heißt im Grunde, so können wir Python verwenden, um diese Funktion zu erstellen, den Rucksack ohne Wiederholung. So sehen wir uns im nächsten Video. 22. Knapsack: In diesem Video werden wir den Rucksack ohne Wiederholungsproblem besprechen . Nun, dieses spezifische Problem funktioniert nicht mit dieser Methode, die wir hier für die unbegrenzte Menge oder die unbegrenzte Menge von Artikeln erstellt haben, die wir haben. Also werden wir ein 2D-Array verwenden und wir werden in einer Sekunde darüber sprechen. Aber bevor wir genau das gleiche Problem verwenden oder dieses Beispiel ausüben. Denken Sie also daran, dass wir mit der , ohne Version, 57 als endgültige Antwort bekamen. Wir werden genau das gleiche Beispiel verwenden. Und wir werden sehen, ob wir das bekommen und 57 als Ergebnis. Um das zu tun, lassen Sie mich einfach alle diese löschen und diese auch nebenbei löschen. Jetzt können wir anfangen, was wir tun werden, ist ein 2D-Array zu erstellen. Also lassen Sie mich es einfach erstellen und sehen Sie in ein wenig. Wie wir wissen, ist dies die Liste oder das Array , das wir erstellen werden und kann über diese als das Gewicht denken. Da wir ein Gewicht von 10 brauchen, werden wir eigentlich diese leeren Plätze um einige Werte hochziehen. Bezüglich, sind, wenn man bedenkt, dass wir haben, zum Beispiel, diese Röhre. Also gibt es zwei SD-Warten, lass mich sie einfach hier schreiben. Wie wir vorhin gesagt haben. Wir haben zum Beispiel bereits diese beiden. Und es hat den Wert oder die Menge von 11. Wir haben drei mit 18, wir haben vier mit 20 und fünf mit 28. Also lassen Sie mich sie hier schnell ausprobieren. Also hier haben wir den Betrag. Wir haben 11, 18 und 20 und 28. Also, was wir hier machen werden, also lass mich einfach, okay. Das erste, worüber wir in diesem Problem nachdenken werden, ist, dass wir diese leeren Orte füllen werden, indem wir annehmen, dass wir nur diesen Artikel zu füllen haben. Also zum Beispiel hier, wenn wir das Gewicht von 0 mit diesem Artikel füllen wollen, können wir es nicht, also lassen wir es einfach leer mit 0. Jetzt wieder, wenn wir ein Gewicht von eins haben und wir nur diesen Artikel haben. Jetzt können wir uns das Gewicht dieses Artikels ansehen, das zwei ist, was größer als eins ist, dann können wir nicht mit tatsächlich tun. Nun dann fragen wir uns, wenn wir ein Gewicht von zwei haben, haben Sie einen Artikel, der ein Gewicht von zwei hat. Können wir prüfen? Und wir lagern sie hier? Ja, das können wir. Also nur gehen, um seinen Wert zu speichern, der 11. In Ordnung, also lass mich die Farbe auf Grün ändern und lass mich einfach alle löschen, schreibe sie nochmal mit dem Grün. Also, wie wir gesagt haben, hier haben wir 0, 0, und hier können wir auch das passen. Also werden wir es passen. Es ist 11. Nun, wie Sie sehen können, werden wir uns fragen, ob wir ein Gewicht von drei haben und wir nur ein Stück der Breite zwei haben, können wir es speichern? Ja, das können wir. Also Bio-Geschäft 11 hier. Und es ist das gleiche für alle, wir werden uns die gleiche Frage stellen. Also, wenn Sie ein Gewicht von 10 haben, zum Beispiel, und wir haben nur einen Artikel, der ein Gewicht von zwei hat. Können wir sie aufbewahren? Ja, wir stornieren. Wir werden seinen Wert speichern. Dann gehen wir weiter zu dem. Jetzt sind wir hier nicht nur auf der Suche nach diesem Gewicht von drei, auf der Suche nach beiden 32. Also, was wir tun werden, ist 000 zu schreiben. Und hier werden wir keine Nullen speichern. Denn denken Sie daran, dass wir diese beiden Dinge zusammen haben. Entweder können wir zwei oder drei oder beides gleichzeitig speichern. Jetzt, da wir dies nur als ein Gewicht von zwei haben, werden wir diesen Artikel speichern, der 11 ist. Dann werden wir zu drei gehen. Jetzt werden wir uns fragen, wir das hier aufbewahren können? Ja, weil es gleich einem ist. Also, was wir tun werden, geht hier dreimal zurück. Also sind wir die 11, wir gehen 1, 2 und 3 gehen zu diesem, was 0 ist. Und hier haben wir 18. Also werden wir überprüfen mit 18 plus 0 ist größer als dieser. Dann werden wir es hinzufügen. In diesem Fall ist es. Also werde ich 18 ihn hinzufügen. Denk so darüber nach. So können Sie entweder speichern oder Sie können drei speichern. Wenn Sie in diesem Fall starten möchten, können Sie es einfach mit dem Wert 11 speichern. Also werden wir hier hinzufügen 11. Wenn Sie dies jedoch nicht tun, müssen Sie den Wert 18 speichern. Denken Sie nun daran, dass, wenn wir mit diesem 2D-Array arbeiten, wenn wir Antworten haben wollen oder wenn wir sicherstellen wollen , dass wir hier ein Gewicht von drei übrig sind, wir dreimal zurückgehen müssen, wie wir es im 1D-Array getan haben im Beispiel des Breitenwiederholungsproblems. Also in diesem Fall, was wir tun werden, ist, den ganzen Weg nach oben zu gehen und wir werden es dreimal vorher überprüfen. Und in diesem Fall, wenn Sie an dieser Stelle genau hier sind, können wir immer eine Breite von drei hinzufügen und am Ende mit dieser Zeile direkt hier. Also sind wir gut. Wir sind hier. Wir werden 0 plus 80 bekommen und wir werden 18 als Antwort haben. Jetzt gehen wir vorerst zu diesem Thema, wir werden uns fragen. Also, wer 11 hat, oder wir haben 18 plus diese vier minus eins. Also werden wir 4 minus 3 bekommen, das ist 1. Wir werden zu diesem Punkt kommen, der 0 ist. Also werden wir 18 aufbewahren. Ok? Also 0 plus 18 gleich 18 ist größer als 11. Wir werden es aufbewahren. Dann gehen wir zu dieser Akte. Wir werden uns fragen, ob fünf größer als drei sind? Ja, das ist es. Damit wir drei anfangen können. Was wir tun werden, ist nach links zu gehen, lassen Sie uns zuerst darüber nachdenken und r Hut. Also, wenn wir ein Gewicht von fünf haben, können wir sicher beide Artikel speichern, mit denen 23 sind. Ordnung, also werden wir ihnen die hinzufügen, 11 plus 18, es wird 29 sein. Jetzt lasst uns darüber nachdenken. Die Art und Weise, wie wir es mit diesem Problem zu tun haben, ist, dass wir, wenn wir fünf sind, wir werden einfach drei davon subtrahieren, also sind es 2. Wir gehen den ganzen Weg zu zwei, schauen uns den Wert hier an, und es ist 11. Also werden wir entweder diese 11 speichern, einfach hier hinzufügen, oder wir nehmen 11 plus 80, das ist 29, und 11 plus 80 Meter 29, was größer ist. Dann fangen wir mit 29 an. Jetzt werden wir genau das Gleiche für diesen hier tun. So ist es entweder 11 plus 18 oder 11, also würde es sicherlich 29 wählen. Also 29, den ganzen Weg bis zum Ende. Jetzt machen wir genau das Gleiche hier. Wir werden uns fragen, hier können wir alles aufbewahren. Da wir jedoch bereits 11 haben, werden wir es hinzufügen. Und wir werden zu diesem Punkt kommen, wo wir vier haben. Wir werden überprüfen, ob das 20 plus die 4 minus 4. Wir gehen den ganzen Weg zurück zu 0. Also 0 plus 20 ist größer als 18. Ja, das ist es. Also werden wir 20 speichern, dann gehen wir auf 20. Wir werden auch überprüfen, ist 20 plus 5 minus 4, was bei einem ist. Also hier haben wir diese 0 ist 20 plus 0. Da ist es nicht. Also werde ich stattdessen nur 29 speichern. Also, was wir hier sagen, ist, dass wir das nicht wirklich brauchen, wenn wir wollen. Wenn Sie nur eine Breite von fünf haben, können wir 32 speichern und sie werden uns eine bessere Antwort von 29 geben , anstatt nur diesen Herbst mit einer Antwort von 20. Wenn wir über diese sechs nachdenken, können wir 24 mit einem Wert von 31 lösen. Lassen Sie uns mit der Formel darüber nachdenken. Also halten wir uns an sechs, wir nehmen sechs minus vier, das ist zwei, Sie werden sich 211 plus 20, 31 größer als 9029 ansehen . Also werden wir es hier den ganzen Weg aufbewahren, wir werden darüber nachdenken, mit den Sieben. Also um sieben, können wir 20 plus die 7 minus 4 speichern, das ist 3. Wir haben 18, also 20 plus 1838. So können wir entweder 38 oder den obigen Wert speichern , der 29 ist, gehen 38 zu wählen. Und wir haben sie alle benutzt. Hier, wo wir neun haben. Jetzt lasst uns darüber nachdenken. Wenn wir 20 plus neun minus vier haben, was eigentlich fünf ist. Also nehmen wir 29 plus 20, das sind 49. So können wir entweder wählen 49 oder 29 zeigt Ihnen wählen 2049, die Picker ist. Und schließlich, für die 10, werden wir die gleiche genaue 49 haben wie zuvor. Nun, was diesen betrifft, werden wir die gleichen genauen Werte bis zur Datei haben. Jetzt werden wir überprüfen, ist 28 größer als 29? Nein, tut es nicht. Also werden wir einfach 2009 speichern. Nun, als ich sagte, dass, wenn es 28 ist größer als 29, Sie können, müssen Sie 28 plus das tun. Fünf minus fünf, gehen den ganzen Weg zu 0. Wir werden uns die obige ansehen, die hier 0 ist. Also 0 plus 28 ist größer als 29. Nein, also werden wir 29 aufbewahren. Jetzt in diesem Fall um sechs, werden wir auch nur 31 speichern, da es hier nichts auf auch 0 gibt. Tut mir Leid, genau hier. Dann schauen wir uns die Sieben an. Also hier haben wir 38 und den Wert von diesem, das ist Check it out. Wir haben 28 plus sieben minus fünf, das ist um zwei. Also 28 plus 11, es ist eigentlich 39, das ist größer als 38. Also gehen wir mit 39. Endlich werden wir tun, für die letzten paar, wir sind bei 8. Wir nehmen entweder 38 oder 28 plus 8 minus 5, das ist 29. Also 28 plus 29 wird uns 46. Wir werden es dann 9 minus 5 wählen, das ist 4. Also haben wir im Herbst 20 oder 20 plus 28 oder 49. Also haben wir 48 oder 49, wir gehen mit 49, was größer ist. Dann schließlich, für den letzten, werden wir überprüfen, ob wir 49 nehmen oder wir nehmen 8 plus 10 minus 5, was auch bei fünf ist. Also haben wir 29 plus 28, was eigentlich 57 ist. Und das sind die größten oder größten Sensoren, die wir haben können. Und wie wir sehen können, haben wir genau das gleiche Ergebnis wie bei der Verwendung unserer 1000. Und dieser Fall, was wir getan haben, wir haben die fünf plus zwei plus drei verwendet. Und wenn wir sicherstellen wollen, dass in diesem Beispiel, kann immer tun, indem Sie einfach sagen, dass Sie hier bei dieser 57. Wie hast du es bekommen? Sie haben gerade 28 hinzugefügt, das ist das Gewicht fünf in die zehn minus fünf, die hier war, Diese 29. In Ordnung? Und das 29 bedeutet, dass Sie nicht 4 hinzugefügt haben, Sie fügen einfach die oben, die bei drei ist, richtig? Also hier haben wir fünf bis jetzt. Und jetzt werden wir überprüfen, ist 29 und 11 das gleiche? Nein, Dies bedeutet, dass Sie hinzugefügt 32 auch. Das ist es im Grunde für das begehbare Beispiel dieses Problems. Das nächste Video werden wir diskutieren oder arbeiten mit dem Pseudocode, den wir verwenden werden, und der Code-Implementierung. So sehen wir uns. 23. Knapsack: Alles klar, was wir jetzt tun, ist, dass wir den Pseudocode dieses Problems durchlaufen werden. Nachdem wir nun eine Lösung implementiert oder erarbeitet haben und an diesem Problem durch ein Beispiel gearbeitet haben, können wir tatsächlich die Formeln entwickeln, die wir verwenden werden, um den Pseudocode auszuschreiben. Das erste, was wir tun werden, ist unser Array oder unsere 2D-Matrix zu erstellen. In diesem Fall gehen wir davon aus, dass wir zuerst hier eine leere Liste haben. Also, was wir sagen werden, ist, dass der erste geleert wird. Der zweite wird diesen Gegenstand haben. Die dritte, die hier ist, wird diesen Punkt neben diesem Punkt auch haben, die vierte Zeile würde diese drei Elemente haben und die letzte wäre mit all diesen Elementen. Und wenn ich sage, dass sie diese Gegenstände haben würden, meine ich, dass sie von diesen Gegenständen wählen können, wo sie wollen. Das war's also. Grundsätzlich beginnen wir mit einem leeren Array. Natürlich werden wir es mit Nullen füllen. Und natürlich wird der erste hier auch alle Nullen sein. Also, das ist es im Grunde. Nun, was wir tun werden, ist unsere eigentliche 2D-Matrix zu erstellen, die ein und dann ein Bild ist, MA. Nun, was wir tun werden, ist, die Größen zu spezifizieren. Denken Sie daran, dass wir hier eine leere brauchen. Also, was wir tun werden, ist, eins zu ihm hinzuzufügen. Anstatt zum Beispiel die Länge von vier zu haben, nehmen wir dieses Beispiel an. Wir haben 2345. Also haben wir die Länge von vier, die wir tun werden, ist diese 2D-Matrix als eine Länge oder eine Größe von fünf anstelle von vier zu erstellen , da wir das hier leer hinzufügen müssen. Was wir also tun werden, ist zu sagen, dass die Größen n plus eins für die Zeilen und W plus eins für die Spalte sein sollten , was darauf hinweist, dass wir hier 11 Spalten brauchen, den ganzen Weg bis zum Tanz, den wir extrahieren müssen. Nun, was wir tun werden, ist, mit unseren beiden for-Schleifen zu beginnen. Der erste wird von beginnen, also werde ich von 0 bis zum Ende sein. Und das ist inklusive. Dann werden wir eine andere for-Schleife erstellen. Ich werde es benennen. W wird von 0 bis zum großen W sein. Und auch dieser ist inklusive. Nun, was wir tun werden, ist zu überprüfen, ob wir an einer bestimmten Position sind, wo wir I gleich 0 haben. Also, wenn das Rho I gleich 0 ist oder die Spalte gleich 0 ist. Also könnte ich 0 oder w gleich 0 sein. Was wir tun werden, ist, dies auf 0 zu setzen. Wie gesagt, wir haben diese Werte, Nullen hier, und diese werden später verwendet werden. Also, wann immer wir zur vorherigen Position zurückkehren wollen. Stellen Sie sich also vor, wir sind bei diesem 1112 und wir fragen nach der vorherigen Position von diesem und es existiert nicht. Daher müssen wir etwas vor einer Bestellung haben damit wir keinen Fehler haben, während ich unseren Code schreibe. Deshalb haben wir das zunächst leer angenommen, was nur Nullen sein wird. Also, wenn ich zu 0 oder w gleich 0 gehe, was wir tun werden, ist zu sagen, dass ich bei I bin und w gleich 0 sein sollte. Das ist also die erste Bedingung. Nun, die zweite Bedingung, wenn die Gewichte, die wir haben, während wir durch diese Gewichte gehen , kleiner oder gleich dem tatsächlichen Weg sind, der es passieren könnte. Nun, in diesem Fall, was wir tun werden, ist, die MA oder diese 2D-Matrix zu aktualisieren. Also lassen Sie uns eine Sekunde darüber nachdenken. Nehmen wir an, wir sind an dieser Stelle vier, und wir sind hier genau hier. Wir haben Temp drei. Also kennen wir diesen Wert noch nicht. Also werden wir es überprüfen. Das erste, was wir überprüfen werden, ist, dass, während wir das durchlaufen, also wenn diese drei kleiner oder gleich vier sind, jetzt ist dies der Fall, es ist wahr, dann können wir es aktualisieren. Wie können wir es aktualisieren? Wir können entweder um 4 minus 3 gehen, was eins sein wird, und fügen Sie diesen Wert von drei hinzu , der 18 plus 0 sein wird. Oder wir werden den Wert darüber nehmen, der 11 ist. Deshalb müssen wir überprüfen, ob die Gewichte tatsächlich kleiner oder gleich dieser Form sind. Und natürlich, wenn das nicht der Fall ist, was wir tun werden, ist, einfach den Wert von oben zu nehmen. Und natürlich könnte eines der Beispiele dafür sein, dass wir bei diesem Gewicht drei sind. Ich werde überprüfen, ob dieses Gewicht kleiner oder gleich zwei ist und es nicht kleiner als oder gleich zwei ist. Was wir tun werden, ist, einfach den Wert von oben zu nehmen. Also gehen wir auf die gleiche und ein mit dem gleichen Gewicht zugreifen. Wir werden jedoch mit einem Index minus1 darauf zugreifen, um den Wert von oben zu haben. Also, das ist es im Grunde lassen Sie mich einfach all diese nehmen und sie ein bisschen kleiner machen. Und ich werde sie hier schreiben. Dann lassen Sie uns mit unserem Code fortfahren. Also haben wir gesagt, dass, wenn f gleich 0 oder w gleich 0, wir werden dies tun. Jetzt. Die zweite Bedingung besteht darin, zu überprüfen, ob die Gewichte bei dem spezifischen Gewicht kleiner oder gleich dem Gewicht ist, das wir hier haben. Und wenn dies der Fall ist, müssen wir die eigentliche 2D-Matrix aktualisieren. Also, was wir tun werden, ist zu überprüfen, ob dieses Gewicht, also Gewicht bei einem bestimmten Index, ich werde es für jetzt leer lassen, kleiner oder gleich w ist, wenn diese Bedingung erfüllt ist. Aber wir werden tun, ist, dieses spezifische i w zu aktualisieren, um entweder gleich zu sein, Also das Maximum zwischen zwei Dingen. Also ist es entweder das K i, also werde ich es hier schreiben. Also ist es entweder bei I minus 1 w. Es ist also entweder der Wert oben oder der Wert der Liste. Also sind wir an dieser 2D-Matrix, wir werden, wie gesagt, wir werden um eins zurückrollen. Und wie für die Spalten, wir gehen von w. Also dies, Nehmen wir an, dass wir bei diesem Wert vier sind und wir sind bei diesem drei Gewicht. Und ich mache vier minus drei, was gleich eins ist. Also machen wir w, das sind vier minus die Gewichte bei einem bestimmten Index, mit dem wir es zu tun haben. Und dann, was wir tun werden, ist, diesen Wert aus Werten hinzuzufügen. Also werden wir den Wert unseres neuen Gewichts hinzufügen. Das ist zum Beispiel dieser, 18 oder 20 oder 28 oder so weiter. Es ist also das Maximum zwischen dem obigen oder dem von hier. Also, das ist im Grunde das ist die Formel, die wir verwenden werden. Jetzt haben wir noch die letzte Bedingung. Also, wenn diese beiden Bedingungen erfüllt sind, ist die letzte, nur den Wert von oben zu nehmen. Und wie gesagt, das ist nicht größer. Es tut mir leid, es ist nicht weniger als oder gleich unserem Gewicht. Wir werden nur den Wert von oben kopieren. Also sonst, was wir tun werden, ist zu spezifizieren, dass der Index bei i, w, es tut mir leid, der Wert von a sollte gleich dem Wert bei I minus 1 w , also das ist es im Grunde für unseren Pseudocode für dieses Problem. In den nächsten Videos werden wir sie in unserem Code oder in unseren Sprachen implementieren. So sehen wir uns. 24. Knapsack: In diesem Video werden wir unsere Funktion mit Java implementieren. Das erste, was ich tun werde, ist, unsere Funktion zu initialisieren, die eine öffentliche Statik ist. Und so kann ich die ganze Zahl zurückgeben? Ich gehe den Rucksackenrucksack. Und es wird einige Parameter wie das Warten nehmen. Und ich nehme eine Reihe von Gewicht, dann werden wir auch tiefe Werte als Array nehmen. Und schließlich, Sie, werde ich die Kapazität oder die Länge dieser Werte und Gewichte nehmen . Nun, was wir tun werden, ist, auf den ersten und sie lügt und w. Dann werden wir unsere 2D-Matrix zu bauen, die ein genannt werden wird. Und es wird n plus eins und W plus eins als die Größe der Länge n. Also erinnern wir uns, dass wir gesagt haben, dass wir n plus eins brauchen weil wir hier ein leeres Array oder eine leere Liste erstellt haben. Und jedes Mal, wenn wir durchgehen, zum Beispiel, wenn Sie hier und als nächstes sind, wird es eine leere Liste plus diese haben. Oder wenn du dabei bist, hey, wir werden diesen und diesen haben, und so weiter und so weiter. Deshalb haben wir n plus 1 hier hinzugefügt, was anzeigt, dass wir haben und plus eins wächst. Okay, was wir jetzt tun werden, ist mit unserer for-Schleife zu beginnen. Also der erste, den wir gesagt haben, dass es mich den ganzen Weg nennen wird. Und der zweite wird j sein, so weiter. Entschuldigung, W. Also w ist gleich 0, dann w kleiner als oder gleich, erstellen Sie eine w. Also w ist kleiner oder gleich groß W und W plus Taste. Dann können wir überprüfen, ob i o w gleich 0 ist. Wir werden einfach ignorieren, aber indem wir bei I und w den Wert 0 speichern. Jetzt ist der zweite Fall, dass, wenn das Gewicht bei i minus1, und wir werden sehen, warum es I minus 1 ist kleiner als oder gleich w Wenn dies der Fall ist, dann werden wir diese zu aktualisieren und das Maximum zwischen zwei Dingen zu tun. Das heißt, der erste sollte der tatsächliche Wert sein, den wir haben. Also bin ich ein bei w und dieser p-Wert darüber. Oder was wir tun werden, ist, oben zu gehen. Und was das W betrifft, werden wir w minus die Gewichte bei I minus 1 hinzufügen. Das war's also. Im Grunde ist es, wie wir es tun können. Natürlich müssen wir ein hinzufügen, etwas, das der Wert oder der Wert der Elemente ist, die wir haben. Und wir werden es in ein bisschen sehen. Aber für jetzt werde ich einfach Werte bei I minus 1 hinzufügen. Also lassen Sie uns eine Minute darüber nachdenken. Was sagen wir hier? Also sagen wir, dass, wenn die Gewichte bei I minus 1 kleiner oder gleich w ist. Nun, lassen Sie uns dies mit minus eins beziehen. Warum verwenden wir I minus1 Satz von KI? Erinnern Sie sich, dass wir hier eine leere Liste hinzugefügt haben. Also, wenn ein Wert, zum Beispiel, wenn wir mit diesem zu tun haben, wird es einen Index von eins haben. Aber in der Liste, die wir bekommen werden, werden wir sie als 2345 haben. Nehmen wir an, sie sind so. So 2345 und ihre Werte oder Beträge sind wie folgt. A 11182028. Das sind also die Indizes. Also haben wir Index 0, 1, 2 und 3. Also, wenn Sie von hier aus auf sie zugreifen wollen, hier haben wir die Gewichte und hier haben wir die Werte. Und natürlich, wenn wir sie in der Liste speichern wollen, müssen wir uns sortieren. Nehmen wir zum Beispiel an, wir sind hier bei I wenn wir auf diesen zugreifen wollen, sind wir jetzt auf Index eins. Dieser Index ist jedoch bei 0 und diese Liste der Gewichtungen, da wir diese leere Liste hinzugefügt haben, die einen Platz belegt hat. Wenn wir also mit I und w auf diese Gewichte und Werte zugreifen wollen, müssen wir uns an diese leere Liste erinnern oder sich erinnern. Deshalb werden wir auf sie mit Minus eins zugreifen. Das war's also. Grundsätzlich verwenden wir deshalb I minus1 hier, hier, und auch hier, wenn wir auf die Werte bei I minus 1 zugreifen. So können wir es ändern. Und wir haben immer noch die letzte Bedingung, das ist, wenn diese beiden Bedingungen nicht mit gerade eine Rückkehr erfüllt sind. Platzieren Sie den gleichen Wert wie oben. Und das ist es im Grunde. Jetzt, wenn wir diese while-Schleife beenden, werden wir nur den Wert bei und zurückgeben, und Kapital W. Also, das ist es im Grunde für dieses Problem. Jetzt gehen wir weiter und probieren es hier aus. Was ich also tun werde, ist eine Hauptfunktion zu erstellen, bei der ich einen Wert haben werde. Nehmen wir also an, wir weisen Werte als Liste zu. Ich werde eine geteilte 2345 haben. Dann werde ich Gewichte haben. Tut mir leid, ich komme gerade rauf. Also hier haben wir die Gewichte. Und die Werte sollten wie folgt lauten, 11182028. Und natürlich brauchen wir das W, das ist zehn. Und dann werden wir n haben, was Werte Punktlänge ist. Also, das ist es im Grunde, jetzt müssen wir noch den Rucksack rufen. Also werde ich es in Ergebnisse des Rucksackproblems mit, neben diesen, all diesen, zurückgeben . Nun, was ich tun werde, ist, es einfach hier auszudrucken. Also werde ich das Ergebnis drucken. Nun, wenn ich voran und führe es hier, und ich werde als den Wert 57 bekommen , der tatsächlich der gleiche Wert ist, den wir von diesem bekommen haben. Es ist genau hier, 57 mit diesem Beispiel und mit unserer Erziehung , wo wir 57 auch mit drei plus zwei plus fünf haben. Also, das ist es im Grunde für dieses Problem. Wenn Sie diese beiden sehen möchten, das Array, können Sie es einfach erstellen oder es dort zurückgeben, es tut mir leid. So können wir es einfach hier in einem 2D-Array zurückgeben. Und anstatt dieses spezifische zurückzugeben, kann man dies einfach entfernen und hier dieses 2D-Array zurückgeben, wie folgt. Und natürlich, das, was wir tun werden, ist, sie in einem Ergebnis zu speichern. Dann können wir in eine for-Schleife gehen, beginnend mit dem Ergebnis, dieser Länge. Und wir werden das Ergebnis nach der Länge hinzufügen. Dann drucken wir sie einfach aus. So Ergebnis. Und dann fügen Sie j plus etwas Platz und drucken Sie dann eine Zeile r1. Und wir werden dieses 2D-Array bekommen. Und natürlich, wenn wir das hier, das wir gebaut haben, überprüfen, sieht es genau gleich aus. Also haben wir 000 bis 11, dann haben wir 001111, und dann 929, 000, 011, 820, 29, 31, und dann achtunddreißig, neunundvierzig. neunundvierzig. Also ist es richtig. Und die Endung mit 46, 4957, und wir haben sie genau hier. Das ist also das genaue 2D-Array, das wir manuell haben. Unsere Lösung ist also korrekt, und dies ist der richtige Weg, um dieses Problem mit Java zu implementieren. Verkaufen Sie den Problemrucksack ohne Wiederholung. Also, das ist es im Grunde für dieses Video. Wir sehen uns im nächsten. 25. Knapsack: Okay, Also in diesem Video werden wir unsere Funktion für das Problem des Rucksacks ohne Wiederholung mit JavaScript implementieren . Also das erste, was ich tun werde, ist, unsere Funktion zu schaffen, die Rucksäcke ist. Und es wird die folgenden Parameter nehmen. Also das W, das Gewicht, die tatsächlichen Gewichtswerte. Und dann können wir es öffnen. Nun, was wir tun werden, ist, beide Indizes zu definieren, die wir verwenden werden. Dann werden wir unsere funktionale oder das 2D-Array erstellen. Und in diesem Fall wird es ein Array und plus eins sein, wie wir sagten. Dann können wir mit unserer for-Schleife beginnen. Also werde ich gleich 0 sein, wie wir gesagt haben, es wird den ganzen Weg bis zum Ende gehen. Und dann werde ich datieren, dann werden wir p w habenIn diesem Fall ist w gleich 0, dann den ganzen Weg bis zur Hauptstadt W und aktualisiert. Jetzt jedes Mal, wenn wir diese Schleife betreten, aber wir werden tun, ist, ein neues Array mit einem bestimmten Index von I zu erstellen. So wird es ein neues Array von Länge w plus eins sein, um es zu füllen. Und jetzt werden wir in diesem Fall überprüfen, ob ich gleich 0 oder w gleich 0 ist. Was Sie tun werden, ist, einfach bei diesem und ich W einen Wert von 0 hinzuzufügen. Jetzt ist die zweite Bedingung, wenn die Gewichtungen an einem bestimmten Index und ich werde mit I minus 1 bezeichnet. Wir werden darüber reden im Bett, ist kleiner oder gleich w das ist der Fall. Dann müssen wir dieses W in eines von zwei Dingen aktualisieren. Also das Maximum zwischen dem Wert darüber. Also ist es, bin ich minus 1 w? Oder die zweite Sache, die ist, wie wir sagten, wir gehen nach oben und gehen dann nach links, indem w minus die Gewichte am spezifischen Index verwenden, also ist es bei I minus 1. Und natürlich, was wir tun werden, ist, den Wert zu addieren. Also die Werte bei I minus eins. Und dann werden wir das am Ende haben. Die letzte Bedingung ist, dass diese beiden Bedingungen nicht erfüllt sind, aber wir werden tun, ist einfach geben diese spezifische Position, den Wert darüber. Also, ich minus 1 w , also das ist es im Grunde. Lassen Sie uns nun darüber sprechen, warum wir in diesem Fall das I minus 1 anstelle von I verwenden. Und die Antwort ist, dass, denken Sie daran, dass wir hier ein leeres Array verwenden. Also eine leere Liste Kriterien. Und was wir tatsächlich getan haben, ist, dass wir den Index von 0 dafür haben, dann haben wir den Index von eins für diese, eins, Index von zwei dafür und so weiter und so weiter. Wenn wir jedoch die Eingaben erhalten, werden wir sie wie folgt erhalten. So zu 11 hat den Wert des Index von 0. Und wenn Sie es in diesem Fall betrachten, haben wir es als Index von eins und der 2D-Matrix. Also, was wir tun werden, wenn wir darauf zugreifen wollen, werden wir I minus 1 verwenden, das ist 1 minus 1. Wir werden 0 haben und wir können Set richtig hinzufügen. Das Gleiche gilt für alle. Wenn wir also bei Index 2 sind, wie können wir mit zwei minus eins darauf zugreifen, was Index eins ist. Also das ist es Grundsätzlich deshalb haben wir von minus1 hier, hier und da benutzt. Also das ist es im Grunde für dieses Problem, das letzte, was wir tun werden, ist, einfach die letzte hier zurückzugeben, die bei und ist, und die große w. Jetzt lasst es uns ausprobieren. Also werde ich Werte von 2345 erstellen, es tut mir leid. Die Gewichte. Dann werde ich die Werte von 11182028 haben. Dann werde ich das Gewicht von zehn haben. Und schließlich, am Ende dieser Länge, so Werte, dass die Länge. Und jetzt rufen wir den Rucksack an. Also werde ich ihn aus dem Rucksack einloggen. Und neben diesen, also w Gewichte, dann Werte, und dann, okay, also lassen Sie uns jetzt dieses Problem oder Programm ausgeben. Also, was wir tun werden, ist, zu diesem Verzeichnis zu navigieren und wir werden anrufen, Lassen Sie mich es einfach hier nennen. Also Knotenrucksack ohne Wiederholung, ab.js wird es ausführen und ich werde 57 als definierenden Wert bekommen, der das gleiche ist, wie wir hier haben. Und natürlich hier. Das ist es, so können wir es lösen. Nun, das Letzte, was ich tun werde, ist, das ganze 2D-Array zu visualisieren. Anstatt also eine bestimmte Ganzzahl zurückzugeben, werde ich das ganze Array zurückgeben. Nun, wenn ich es wieder laufen und ich werde zu bekommen, ist ein Array und wir haben den ersten Schlaganfall, zweiten, dritten, vierten und 550. Nun, was wir tun werden, ist, sie einfach zu vergleichen. Also für Schlaganfall, eigentlich alle Nullen, was im Grunde das ist, was wir hier erwartet haben. Dann haben wir 000 und dann sind sie alle 11. Hey, wir haben den Rest 29, also werden wir korrigieren. Dann haben wir hier 3849 Diagramm. Und schließlich haben wir 46, 4957. Und hier sind sie. Also, das ist im Grunde für dieses Problem. Auf diese Weise können wir sicherstellen, dass es korrekt ist und unsere Implementierung unseres Codes tatsächlich korrekt ist. Das ist es also für den Knapsack ohne Wiederholung mit JavaScript. Davon abgesehen, das ist das Ende dieses Videos. Wir sehen uns in der nächsten. 26. Knapsack: Okay, in diesem Video werden wir den Rucksack ohne Permutationsproblem mit Python lösen. Der erste Schritt, den ich machen werde, ist, eine Funktion zu erstellen und sie einfach zu benennen. Und es war ein großer Gong, einige Parameter wie das Gewicht, die Gewichtswerte und n. Also lasst es uns öffnen. Und das erste, was wir tun werden, ist, unsere 2D-Matrix zu erstellen. Und diese Matrix sollte zwei Parameter annehmen. Wie können wir es nun mit einer Codezeile erstellen? Wir wollen das einfach für die Zeile angeben. Also für x im Bereich von W plus eins. Und dann was die Spalten betrifft, tut mir leid, das ist für die Spalten und was die Zeile betrifft, werde ich es für Bereich und Plus1 machen, wie wir sagten. Jetzt können wir mit unserer for-Schleife beginnen. Die erste for-Schleife sollte also in 0 beginnen und mit n plus 1 enden. Also für ich in Bereich und plus eins, dann sollte die zweite for-Schleife einen Bereich von 0 bis W plus eins starten. Tut mir leid, wir haben Kapital W. und fangen wir mit unserem Code an. Also das erste, was wir tun werden, ist zu überprüfen, ob ich gleich 0 oder w gleich 0 ist. Das ist der Fall. Dann wollen wir einfach aktualisieren oder fügen Sie einfach 0 in diesen Wert hinzu. Also, das ist es im Grunde jetzt anders. Also, was wir tun werden, ist zu überprüfen, ob die Gewichte bei I minus 1. Wir werden darüber reden, ich minus1 Libanon Bit. Aber jetzt lassen Sie uns darüber nachdenken, wie dies. Also, wenn es kleiner als oder gleich w ist, was wir tun werden, ist das Auge zu aktualisieren, das 2D-Array an den spezifischen Indizes in das Maximum zwischen zwei Dingen. Der erste ist der tatsächliche Wert, den wir über ihm haben. Also ich minus1, wie es ist, Ich zeige die Straße und w oder etwas anderes, das ist der MA bei I minus eins. Und was die Säule angeht, sagten wir, dass wir von W subtrahieren müssen, den Abfall, den wir bekommen werden. Also dieser Pi minus eins in diesem Fall. Und natürlich werden wir den Wert davon hinzufügen, der bei I minus eins auch ist. Und schließlich ist das nicht der Fall. Außerdem werden wir etwas anderes tun. Das ist, um einfach den Wert darüber zu nehmen und ihn zu diesem hier hinzuzufügen. Also bin ich bei mir minus eins, was darüber ist. Also, das ist es im Grunde jetzt hinzufügen Punktzahl diese ich minus1 in der, warten. Warum haben wir es benutzt? Denn wenn wir zu unserem Pseudocode zurückkehren, wie wir sehen können, haben wir gesagt, dass wir hier ein leeres Array haben. Und wenn wir über unsere Gewichte und Werte denken, haben wir Gewichte, Werte und ihre Indizes sind wie folgt, 0123. jedoch in unserem 2D-Array Wenn Siejedoch in unserem 2D-Arrayauf dieses zugreifen möchten, liegt es nicht bei Index 0, index1. Hier haben wir den Index 0, 1, 2, 3, 4 und 5. Wenn Sie also darauf zugreifen möchten, ist es hier bei Index 2. Es ist jedoch am Index eins und unser Input. Deshalb, wenn wir auf diese zugreifen wollen, subtrahieren wir einfach von einem. Wenn wir also bei Index 3 sind, nehmen wir an, dass wir 0, 1, 2 und 3 haben , sind wir hier. Also bei Index 3, wie man darauf zugreifen kann, um unsere Empathie zu nutzen. Also machen wir Index 3 minus 1, was 2. Jetzt können wir darauf zugreifen, indem wir Gewichte und Werte bei Index zwei verwenden. Das ist also die ganze Idee über das i1 x1 und wie man sie benutzt. Und natürlich, wenn Sie damit verwechselt sind, können wir einfach immer 0 hier und hier hinzufügen. Dies wird also bei 0 beginnen, und dies wird bei 1, 2, 3. Aber weil wir nicht komplex sind oder nicht, machen Sie es kompliziert, ich habe einfach i minus eins anstelle von I. hinzugefügt. Also das ist jetzt, was wir tun werden, ist, einfach den MA an der tatsächlichen UND zurückzugeben, und w, also ist dies die letzte Eingabe. Probieren wir es jetzt aus. Also sind die Werte hier tatsächlich, wie wir gesagt haben, wir haben 11182028. Dann haben wir die Gewichte, die 2, 3 und 4 und 5 sind. Dann haben wir das W, das Gewicht, das wir brauchen, gleich 10, und nur die Länge der Werte. Probieren wir es jetzt aus. Also werde ich den Rucksack drucken. In diesem Fall werde ich w Gewichte haben, dann Werte, dann. Und jetzt, wenn wir weitergehen und zu unserem CMD gehen, was wir tun werden, ist Python Rucksack ohne Wiederholung auszuführen. Ich leite es. Und hier haben wir dann gültigen Index. Sie haben ein schmales Sprichwort, dass 0 für x und Gewinne von 0. Okay, hier haben wir also, wir haben uns nicht verlobt, es ist nur verlobt. Jetzt versuchen wir es noch einmal. Das ist ein Tippfehler. Wir haben eine Länge, wir haben vergessen, die n hier gleich jetzt hinzuzufügen, denke ich, wir sind gut. Jetzt wieder magnetisch, wir werden dieses Ergebnis von 57 bekommen, wie Sie hier sehen können. Das deutet also darauf hin, dass wir unser Ziel erreicht haben. Nun, was wir tun werden, ist, das gesamte 2D-Array zu visualisieren. Anstatt diesen letzten Wert zurückzugeben, werde ich nur das ganze Array zurückgeben. Wenn ich das nochmal versuche, bekomme ich das, wie gesagt. Also werden wir die erste Zeile, zweite Spalte haben. Und natürlich, wenn Sie sicherstellen wollen, dass dies richtig ist, was wir nicht tun, ist es, sie einfach mit diesen zu vergleichen. Also sollte die erste Reihe, wie wir gesagt haben, alle Nullen sein. Die zweite Reihe ist 0, 0, den ganzen Weg bis 11. Und der dritte wäre 000 011, 1818, und dann alle, 29, dann haben wir 000 011, 1820, 29. Dann landen wir mit 49 und 49. Und die letzte Reihe wird enden mit sechsundvierzig, neunundvierzig und siebenundfünfzig. Wenn wir es uns ansehen, haben wir 46 4957. Dies deutet also darauf hin, dass unsere Lösung korrekt ist. Also, das ist es im Grunde für dieses Video. Wir sehen uns im nächsten. 27. Anzahl von Subsets die zu einer bestimmten Nummer hinzufügen: Hallo und willkommen zurück. In diesem Video werden wir das Problem der Suche nach der Anzahl der Teilmengen diskutieren , die sich zu einer bestimmten Zahl addieren können. Jetzt in diesem Beispiel haben wir eine Reihe von vier Zahlen, 1345, und wir haben die Nummer neun, die wir jetzt verwenden werden. Was wir also tun werden, ist zu überprüfen, ob wir eine Teilmenge oder mehr als eine Teilmenge haben , die bis zu neun addieren kann. Und in diesem Beispiel haben wir zwei Teilmengen. Die erste ist 135, und die zweite ist für N5. Und beide addieren sich bis zu 90. Wenn Sie alle Elementindizes innerhalb der Teilmenge addieren, und Sie erhalten neun als endlichen Wert. Lassen Sie uns eine Sekunde darüber nachdenken. Der erste Ansatz, den wir tun können, ist, alles mit Rekursion gelöst zu haben. Und der Grund, warum ich das sage, ist, dass, wenn du darüber nachdenken willst oder wir es mit einem Stück Papier lösen willst. Lasst uns zum Beispiel darüber nachdenken. Wenn wir hier ein leeres Set haben. Also lassen Sie mich es hier zeichnen. Was wir tun werden, ist durch jedes Element zu kommen und es einmal einschließen und es das andere loswerden. So zum Beispiel, Zuerst haben wir eine leere Menge. Wir werden überprüfen, ob das gleich 9 ist. Ist es nicht. Was du tun wirst, ist, dieses von hier hinzuzufügen. Also lassen Sie mich die Farbe ändern. Wir werden diese Nummer 5200 auf einmal hinzufügen. Und wir werden es einfach zum zweiten Mal so behalten, wie es ist. Nun, was wir tun werden, ist zu überprüfen, dass auch dies gleich 9 ist. Ist es nicht. Was wir tun werden, ist zu der anderen Nummer zu gehen, die vier ist. Wir werden es einmal hinzufügen. Und behalte nur fünf, den anderen Begriff. Und hier werden wir es hinzufügen und es leer halten. Jetzt können wir zur dritten Zahl übergehen, die 3. Und die Arbeit, die wir tun werden, ist genau das Gleiche. Also hier haben wir 5, 4, 3, und hier haben wir es mir leid. Ja. In Ordnung. So 54. Und natürlich werden wir hier 53 haben und wir werden es fünf behalten, genau hier, und so weiter und so weiter, bis alle möglichen Kombinationen bekommen, die wir bekommen können. Und natürlich werden wir jedes Mal überprüfen, wenn wir einen Bildschirm erstellt haben, wir werden überprüfen, ob das gleich vier ist. 29 zum Beispiel, oder das ist gleich neun. So haben wir 54 ist gleich neun. Also, dann erhöhe ich den Zähler. Vielleicht haben Sie also einen variablen Zähler oder etwas, und dies wird inkrementiert. Also haben wir neun vorerst. Dann werden wir zum Beispiel überprüfen, die andere Lösung, die 1, 3 und 5 ist , sie enthält fünf, ist hier, fünf, 53. Und wir werden eine 531 haben, was auch wahr sein wird. Und wir werden den Zähler einschließen oder inkrementieren. Und wie wir sehen können, um dieses q zu erstellen, müssen wir Rekursion verwenden, oder es ist der logischste Weg, dies zu tun. Nun, was wir tun werden, ist den Pseudocode für diese Rekursionsmethode zu schreiben. Dann werden wir versuchen, es mit dynamischer Programmierung oder Auswendiglernen zu optimieren. Also lasst uns voran gehen und es genau hier machen. In Ordnung, also nimmt eine Funktion drei Parameter an. Die erste ist die Liste, die wir haben werden. Also nenne ich es einfach Liste. Dann nehmen wir eine Gesamtsumme. Ich werde es in einer Sekunde erklären. Und dann endlich ein Index I. Also lassen Sie uns eine Sekunde darüber nachdenken. Was werden wir tun? Zuerst werden wir dieses Array bauen, das leer oder weniger ist, das leer ist. Und dann werden wir 52 auf einmal hinzufügen und wir werden es so halten, wie es dafür ist. Und wie sollen wir das machen? Lassen Sie es mich einfach hier setzen. Lassen Sie mich das löschen und fahren Sie fort. Was wir also haben werden, ist ein Index, der auf diese Nummer fünf hinweist. Das erste Mal, wenn wir beginnen, dann, was wir tun werden, ist, diese Datei, zum Beispiel, in die Liste hinzuzufügen . Danach, was wir tun werden, wir eins nach dem anderen zurückziehen, bis wir alle Elemente durchlaufen. Und nehmen wir an, wir fügen dieses Element hinzu, das vier ist. Also lassen Sie mich einfach rot bezeichnen. Nehmen wir an, hier wollen wir überprüfen, ob wir eine Liste erstellen oder diese Nummer neun mit dieser Liste erstellen können , nur die Elemente, die vier und davor enthält. Also, was wir tun werden, ist zu überprüfen oder eine Funktion zu erstellen, die uns diese genaue Zahl zu bekommen, wie viele Sätze, die wir tun können und dass Sie zwei haben können damit wir diese Nummer neun mit nur diesen Elementen erhalten. Also, wenn der Index diese drei hier hinzufügen, haben wir die Liste von nur 13. Also wollen wir 45 einschließen. Das ist also, was wir meinen, indem ich es dekrementieren werde. Und. Überprüfen Sie, wie viele Listen wir eine Bestellung haben können, um diese Nummer neun zu haben. Jetzt in Bezug auf die Summe, aber wir wollen nicht tun, ist jedes Mal um die Zahl am spezifischen Index zu verringern. Und Sie können in einer Sekunde verstehen, wenn wir saßen mit dem Code schreiben. Und was wir tun wollen, ist, endlich die Nummer des Möglichen zu bekommen , so dass wir einen Befehl haben können, um diese Nummer neun zu bekommen. Also lassen Sie mich das einfach löschen. Und fangen wir mit unserem Code exemplarisch an. Und wir werden es unterhalten und erklären, während wir es durchmachen. Das erste, was ich tun werde, ist, also ist das unsere Funktion. Also lassen Sie mich diese Parameter einfach als diese bezeichnen. Und was wir tun werden, ist zu überprüfen, sobald wir insgesamt 0 erreicht haben, das bedeutet, dass wir all diese Zahl konsumiert haben. Wir haben insgesamt 0, dann ist es okay. Wir können einen zurückgeben. Da dies wie ein Basisfall ist. Zum Beispiel, hier, wenn wir auf die Summe von 0, die fünf plus vier ist, ist gleich neun, dann wird die Summe davon bleiben oder wird in diesem Fall 0 sein, da wir neun um fünf verringern werden, dann um vier reduziert, werden wir hier eine Summe erhalten, die gleich 0 ist. Was wir tun werden, ist einfach hier zu stoppen und unsere Funktion zu erhöhen. Also lassen Sie mich es einfach Rekursion nennen. Also nenn es wiederkehrend. Und in diesem Fall, wenn die Summe gleich 0 ist, bedeutet dies, dass wir in der Lage waren, zu einer Teilmenge zu gelangen, die bis zu neun addiert. Und dieser Fall, was wir tun werden, um einfach einen zurückzugeben. Nun, lassen Sie uns darüber nachdenken, ob die Summe in diesem Fall kleiner als 0 ist, wie dieses Beispiel, oder vielleicht dieses hier. Okay, also haben wir keinen Punkt behandelt, wo die Summe weniger als 0 ist, außer diesem. Also vielleicht nehmen wir einfach diese 5 plus 4, die gleich neun plus drei ist, was gleich 12 ist. Und in diesem Fall, wenn die Summe kleiner als 0 ist, dann, was wir tun werden, ist einfach 0 zurückzugeben. Wenn also die Summe kleiner als 0 ist, können wir 0 nicht zurückgeben. Denken Sie nun daran, wir wollen, tatsächlich zu diesem Punkt kommen. Wir könnten zu einem Punkt kommen, wo die Summe kleiner als 0 ist und andere Fälle, in denen 54 keine Teilmenge einer möglichen Teilmenge sind. Also zum Beispiel, vielleicht haben wir einen anderen, vielleicht Sex hier und wir haben 6 plus 5. Plus 6 plus 5 ist eigentlich 11 und das ist größer als vier, größer als neun, es tut mir leid. Also in diesem Fall werden wir 0 zurückgeben. Das war's also. Dies ist für den zweiten Basisfall. Nun gehen wir zum dritten Basisfall über, was ist, wenn wir zu einem Punkt gekommen sind, an dem wir den minimalen Index erreicht haben, in dem der Index kleiner als 0 ist, ich weniger als 0. Was wir tun werden, ist, einfach auch 0 zurückzugeben, was anzeigt, dass wir das ganz links unseres Arrays erreicht haben. Und in diesem Fall haben wir keine Teilmenge gefunden, die bis zu neun summieren kann. Also, wenn ich kleiner als 0 ist, geben Sie einfach 0 zurück. Also das ist es für die Basisfälle. Jetzt können wir mit unserer Rekursionsfunktion beginnen. Also, was ich tun werde, ist, sie einfach hier zu platzieren. Und das hier auch, ich werde sie als seinen Erben platzieren. Und jetzt gehen wir zum zweiten oder zum lustigen Teil hier. Das ist eigentlich die Rekursion. Also, jetzt, was wir tun werden, ist zu überprüfen, wie ich will, Insgesamt ist weniger als eine bestimmte Zahl. Also zum Beispiel, wenn wir an dieser Nummer vier sind, alles klar, was wir tun werden, ist zu überprüfen, ob die Summe, die wir übrig haben, das ist neun minus fünf, das ist vier, kleiner ist als diese Zahl. Wenn das der Fall ist, können wir keine vier hinzufügen. Vier ist jedoch nicht weniger als vier, es ist tatsächlich gleich. So können wir hier einen Trend einbeziehen. Also haben wir zwei Fälle. Die erste ist, wenn diese Zahl kleiner als vier ist, also n ist kleiner als die Zahl, die wir insgesamt haben. Also lassen Sie mich es einfach schreiben und es dann weiter erklären. Also, wenn die Gesamtzahl, die wir übrig haben, kleiner ist als die tatsächliche Zahl in dieser Liste, so ist weniger als die Liste in einem bestimmten Index I und das ist der Fall. Dies bedeutet, dass wir unsere addieren können, wir können diese Nummer 4 zu unserer Liste oder unserer Teilmenge hinzufügen. Also, was wir tun werden, ist, einfach den Pfeil in die anderen Elemente zu bewegen. Wie machst du das? Wir geben einfach die gleiche Funktion zurück. So. Rekursion in der Liste. Die gleiche Summe, da wir diese Summe nicht verwendet haben und ich minus1 anzeigt, dass wir dies nicht mehr brauchen. Wenn das nicht der Fall ist, werden wir zwei Dinge zurückgeben. Das erste ist, dass wir dies für die zweite hinzufügen, ist, dass wir es nicht hinzufügen, wie wir hier gesagt haben. Also zum Beispiel, wenn Sie in diesem bestimmten Moment sind wo wir fünf haben und dann haben wir zu dem Index, an diesem Element ist, für das, was wir tun werden, wird zuerst hinzugefügt und dann halten Sie die Liste so, wie es ist. Und was wir tun werden, ist, die möglichen Teilmengen aus diesem Teil des Baums und alle möglichen Teilmengen von diesem positiven kzu erhalten diesem Teil des Baums und alle möglichen Teilmengen von diesem positiven k und dann fügen Sie sie hinzu, addieren Sie sie und erhalten alle möglichen Teilmengen. In diesem Fall haben wir hier einen. Also haben wir einen hier und wir haben einen hier. Was wir tun werden, ist, eins plus eins hinzuzufügen und das wird zwei dauern. Und dann werden wir als die mögliche Qualität Endwert zurückkehren, die wir haben. Also, wie machen wir das? Wir werden zu Rekursionsfunktionen nehmen und sie zusammen hinzufügen. Die erste ist, dass wir diese vier einschließen, und die zweite ist nur, dass wir die Liste so geben, wie sie ist. Also, was wir tun werden, ist es mir leid, wir können einfach anders sagen. Aber wir werden tun, ist, zwei Dinge zurückzugeben. Das ist die Rekursion in dieser Liste. Das erste Mal, dass wir es einbeziehen, werden wir einfach von der Summe abnehmen. Also werden wir auf die Dekrementliste bei i und einfach unseren Zähler dekrementieren. Also, was du tun wirst, ist, es einzubeziehen und dann zu diesen drei hier zu gehen. Und wir werden genau das Gleiche mit allen Elementen hier tun. Dies ist also die erste und wir werden es zur gleichen Rekursion hinzufügen. Aber dieses Mal werden wir die Liste hinzufügen, ist, wie würden wir das tun? Wir geben einfach insgesamt statt durch dieses Element dekrementiert. Also werden wir fünf geben, was neun minus eins ist, wird insgesamt bleiben, und dieser Fall werden wir auch abnehmen. Also, das ist im Grunde, das ist unsere Formel. Wenn du darüber nachdenkst, was wir sagen, ist, dass wir die ganze Liste von rechts nach links durchlaufen werden. Und dann werden wir prüfen, ob einer der Basis-Fälle zutrifft. Wenn dies der Fall ist, werden wir die entsprechende Nummer zurückgeben. Also, wenn die Summe gleich 0 ist, wie in diesem Fall, was wir zurückgeben werden, ist eins. Andernfalls können Sie 0 nicht zurückgeben. Jetzt für die Rekursion, Rekursionsteil, aber wir werden tun, ist zu überprüfen, ob unsere Summe kleiner ist als die Summe hier, das Element genau hier. Nehmen wir also an, wir haben insgesamt drei und wir haben die Nummer vier. Es gibt also keine Möglichkeit, dass wir etwas zur Form hinzufügen können , das bis zu dieser Summe drei ausmachen kann, weil drei weniger als vier sind. Was wir also tun werden, ist, diesen Index oder diesen Pfeil einfach in den davor zu verschieben . Das haben wir also hier gemacht. Und wenn das nicht der Fall ist, wenn wir das einfach für unser Set setzen können. Aber wir werden tun, ist, zwei Dinge hinzuzufügen und einander. Die erste, die tatsächlich in unserem Set enthalten ist, und die zweite ist, das Set so zu halten, wie es ist. Und dann sehen wir die tatsächlichen Zahlen von hier und hier und addieren sie. Wir werden die endgültige Zahl mit dieser Methode Rekursion erhalten. Also, das ist es im Grunde für dieses Problem. Nun, was wir im nächsten Video tun werden, ist zu versuchen, es mit dynamischer Programmierung und Auswendiglernen zu optimieren . So sehen wir uns dann. 28. Verbesserte Lösung: In diesem Video werden wir versuchen, unsere Lösung dafür zu optimieren. Ermitteln der Anzahl der Teilmengen, die sich an ein bestimmtes Zahlenproblem anpassen können. Der Hauptnachteil unserer rekursiven Lösung ist also , dass wir die gleiche rekursive, rekursive Funktion immer und immer wieder aufrufen werden. Und warum ist das? Weil du darüber nachdenkst. Wenn wir zum Beispiel an der bestimmten Nummer sind , hier nur um fünf, was wir tun werden, ist, sie noch einmal für 54 zu nennen, dann nennen Sie es noch einmal, 45403. Was wir also im Grunde tun, ist, dass wir diese vier hier hinzufügen werden. Dann fügen wir es hier hinzu. Und dann werden wir es natürlich jedes Mal hinzufügen, wenn wir durch diese hier gehen, zum Beispiel, diese drei, werden wir hier genannt werden, hier. Und dann haben wir diese linke Dr. Chris. Und in diesem Fall wird es immer wieder aufgerufen werden. Was wir also tun werden, ist, diese Werte in einer Liste, einem Hashmap-Wörterbuch zu speichern , alles, mit dem wir es lösen können. Und was wir tun werden, ist jedes Mal, wenn wir diese Funktion ausführen oder sie aufrufen, wir werden überprüfen, ob dieser spezifische Parameter oder diese spezifischen Parameter tatsächlich in der Liste enthalten sind. Also, wenn dies der Fall ist, dann haben wir sie bereits aufgenommen und wir haben bereits die Anzahl der Teilmengen berechnet. Und in diesem Fall müssen wir es nicht wirklich noch einmal überlegen. Eine Möglichkeit, das zu tun, ist, also zum Beispiel, wenn wir hier sind und wir fünf hinzugefügt haben, dann haben wir für die eingedrungenen drei hinzugefügt. In diesem Fall, wenn wir diese drei direkt hier hinzufügen, was wir tun werden, ist es, zum Beispiel, um sie der Liste hinzuzufügen. Und dann jedes Mal, wenn wir diese 3 nennen, zum Beispiel hier, wenn das tatsächlich die drei in der Liste waren, dann haben wir bereits berechnet Es ist die Anzahl der Teilmengen, dann müssen wir es nicht wirklich wieder berechnen. Und das ist, das wird uns erlauben, tatsächlich viel Zeit zu sparen. Denn wenn wir zum Beispiel hinzufügen, wenn Sie hier sind und wir bereit sind, finden wir heraus, dass wir dies bereits getan haben. Was wir tun werden, ist, einfach den Rest des Baumes zu ignorieren, der hier ist. Um damit zu beginnen, müssen wir zunächst einen neuen Parameter innerhalb unserer Funktion definieren, das ist die eigentliche HashMap oder die Liste, die wir verwenden werden. In diesem Fall werde ich es einfach hier nennen und es als Auswendiglernen benennen. Also nenne ich es Memo. Was wir also tun werden, ist, einen Schlüssel und einen Wert zu erstellen und sie in diesem Memo zu speichern. Es wird also entweder ein Wörterbuch oder eine HashMap sein, die einen Schlüssel und einen Wert enthält. Was wir also tun werden, ist, den Schlüssel als Summe und die Index-Subsumme zu speichern. Und werden wir einen Weg finden, sie im Schlüssel zu sortieren? Und der Wert sollte die Anzahl der Teilmengen sein, die wir eine gegebene diese spezifische Zahl haben können. Nehmen wir an, wir fügen an diesem hinzu. Was wir tun werden, ist, einen Schlüssel dafür zu speichern. Und natürlich werden wir zum Beispiel bei dem Wert speichern, der 0 dafür ist , weil Wir dieses und neun nicht wirklich aus der Teilmenge bekommen haben. Also, um das zu tun, was wir anfangen werden, ist, unser Memo an einem bestimmten Punkt zu konstruieren. Also, wenn wir diese Funktion aufrufen, werden wir tun, ist es, den Schlüssel zuerst zu konstruieren. Und der Schlüssel, was ich als String verwenden werde. Also werde ich eine Schnur verwenden. Außerdem werde ich das gesamte Komma speichern, das Auge, das ist der Index. Also in dem Schema sollte wie die sein, so zum Beispiel, was wir in diesem Schlüssel haben, ist ein. Angenommen, wir sind an diesem Punkt, der hier ist, was wir bekommen werden, ist neun minus fünf, also ist die Summe vier. Also werden wir vier speichern, kommen und der Index ist 0, 1 auf den Index ist zwei. Das ist also unser Schlüssel. Und unser Wert sollte eigentlich die Anzahl der Teilmengen sein, die wir tun können, um diesen gegebenen Punkt zu sagen. Und wie können wir berechnen? Und es wird den ganzen Weg zurück bei dieser Nummer gehen, spezifische Nummer eins. Und dann funktioniert die Rekursion. Was wir also tun werden, ist zunächst zu überprüfen, ob dieser Schlüssel tatsächlich in unserem Memo ist, dann haben wir bereits berechnet. Also müssen wir es nicht wirklich durchgehen, also geben wir es einfach zurück. Also, um das zu tun, werden wir einfach hier hinzufügen, wenn der Schlüssel, also lassen Sie mich das einfach ein bisschen kleiner machen. Und was wir tun werden, ist zu überprüfen, ob der Schlüssel ein Memo ist. Aber wir werden tun, ist einfach den Wert innerhalb des Schemas zurückzugeben, innerhalb des Memos. Also geben Sie Memo an bestimmten Schlüssel, den wir erstellt haben. Nun, wenn dies nicht der Fall ist, dann fahren wir fort, wir werden unsere rekursive Funktion fortsetzen. Was wir hier jedoch tun werden, ist, anstatt sie sofort zurückzugeben, wir werden sie einfach in einem Wert speichern und ich werde es nennen, um zurückzukehren. Also werden wir sie in einer zwei Rückkehr speichern, die eine einfache Variable ist. Und bevor wir sie zurückgeben, werden wir sie im Memo aufbewahren. Also, wie machen wir das? Wir schreiben den Code hier weiter. Also werden wir bei diesem Memo speichern, bei Schlüssel. Wir werden speichern, was wir haben, also werden wir es aufbewahren, um zurückzukehren. Und danach können wir einfach zurückkehren. Also kehre zurück, um zurückzukehren. Das ist im Grunde jetzt, was wir tatsächlich getan haben, ist, dass wir einen Schlüssel aufbauen. Dann prüfen wir, ob unser Wert oder was wir tun wollen, tatsächlich bereits im Memo ist. Wenn dies der Fall ist, geben wir es einfach zurück. Dass dies nicht der Fall ist, werden wir es berechnen. Und dann natürlich, zu unserem Memo hinzugefügt, dass, bevor es wieder zurück. Das war's also. Grundsätzlich ist das, was Sie tun müssen. Und das spart uns viel mehr Zeit und es wird die Komplexität sehr verringern, weil wir es nicht getan haben, wir nicht wirklich die gleiche Funktion immer wieder aufrufen. Nun, was die tatsächliche Laufzeit für dieses Problem betrifft, Lassen Sie uns darüber nachdenken. Also für all diese Basisfälle ist die tatsächliche Laufzeit O von eins. Wir kümmern uns also nicht wirklich um sie. diesen spezifischen betrifft, haben wir hier die Funktionen, die wir hier aufgerufen haben, und wir kommen, um ihn zu schreiben. Also ist es entweder dieses ein oder zwei. Jetzt nehmen wir an, wir gehen davon aus, dass wir Stan treffen werden. Also, was wir tun werden, ist zu überprüfen, wie viele Anrufe wir tätigen? Und die eigentliche Lösung? Oder die Antwort ist ziemlich einfach, weil wir dieses Memo verwenden, also nicht viel aufrufen. Also lasst uns darüber nachdenken. Aber wir rufen eigentlich an, dass jedes Mal, wenn wir nach Liste dekrementieren, ich, es tut mir leid, jedes Mal, wenn wir um ich minus eins dekrementieren. Und in diesem Fall nennen wir es die Nummer. Es sagt die Gesamtzahl mal die tatsächliche Anzahl der Elemente in dieser Liste. Warum haben wir das getan? Also lasst uns so darüber nachdenken. Die Anzahl der potenziellen Ursachen, die wir zu tun kommen, ist mit der Summe und n. weil denken Sie daran, dass wir eine Liste im Gegensatz zu Zeiten haben. Dies ist der Index 0 und den ganzen Weg bis 0123. Was wir also tun werden, ist, den Schlüssel und den Wert entsprechend zu haben. Der Schlüssel ist also eigentlich das, was wir hier getan haben, was das Gesamtplus das Auge ist. So ist es fair anzunehmen, dass wir n mal für das Auge haben, weil Annual Great, Ich würde von 0 bis drei reichen. Also haben wir vier und die Summe wird tatsächlich sein, wenn, nehmen wir an, dass wir neun haben, es wird tatsächlich neun mal vier Möglichkeiten sein, dass wir dieses Schlüssel-Wert-Paar bekommen können. Und in diesem Fall ist das Gesamtzeiten n. Und wir werden den schlimmsten Fall annehmen, wo wir es zweimal anrufen werden. Also multiplizieren wir es mit zwei. Und das ist unsere Laufzeit, die vier ist. Jetzt können wir diese Konstante immer entfernen und wir werden 0 der Gesamtzeiten bekommen. Und das ist im Grunde für dieses Problem. Jetzt in den nächsten Videos werden wir sie implementieren waren in den Sprachen, die wir haben, um Sie zu sehen. 29. Anzahl der Java-Implementierung: In diesem Video werden wir unsere Funktion mit Java implementieren. Das erste, was ich tun werde, ist, eine Funktion mit den vier Parametern zu erstellen , über die wir gesprochen haben. Also werde ich es einfach so nennen, wie wir es gesagt haben. Oder in diesem Fall können Sie es vielleicht in Memos ändern. In Ordnung, also behalte ich es vorerst. So öffentlich, statisch. Und dies sollte eine ganze Zahl zurückgeben und es wird wiederholt werden. Und die Parameter des Parlaments sind die Liste, die wir haben, die Summe, das Auge und das Memo. Und natürlich sollte unsere Liste in einer ArrayList oder weniger sein. Ich werde mit, es tut mir leid, entweder mit einer Array-Liste oder einem Array gehen. Ich werde mit einer Array-Liste gehen. Also Array-Liste. Und es wird in diesem Fall vom Typ Integer sein. Dann gibt es unsere Liste. Die Summe sollte eine Zahl, das Ende, auch eine Zahl zu einer Ganzzahl sein. Und schließlich hier haben wir die Hash-Karte in diesem Fall. Und es wird einen Schlüssel und einen Wert nehmen. Alken wird also eine Zeichenfolge sein und der tatsächliche Wert wird eine ganze Zahl sein. Also, das ist es im Grunde jetzt können wir mit unserem Code beginnen. Was wir zuerst tun werden, ist zu überprüfen, wie wir gesagt haben, wir werden den Schlüssel aufbauen und überprüfen ob diese tatsächlichen Erinnerungen und unsere Demo, wenn nicht aufgerufen. Also, wie machst du das? Wir können den Schlüssel zunächst nicht konstruieren. Also lass mich das einfach loswerden. Gibt 0 zurück. Und wir haben, was Sie tun werden, ist, die wichtigsten Stärken der Stärke k gleich der Zeichenfolge der Summe plus das Komma plus die tatsächliche Zahl I zukonstruieren die wichtigsten Stärken der Stärke k gleich der Zeichenfolge der Summe plus das Komma plus die tatsächliche Zahl I zu , die den Index hat. Nun, dieser Schlüssel ist tatsächlich in unserem Memo. Wir werden es zurückgeben, je geschrieben seinen Wert aus unserem Memo. Und wie überprüfen wir es? Wir werden das Memo verwenden, das Schlüsselmethode enthält. Und in diesem Fall, wenn es wahr ist, werden wir einfach das Memo an der spezifischen Taste zurückgeben. Und es tut mir leid, das müssen wir notieren. Holen Sie sich das spezifische Tor. Nun, das ist nicht der Fall. Was wir tun werden, ist zu überprüfen, ob die Summe gleich 0 ist. Und in diesem Fall, was wir tun werden, ist einfach 0 zurückzugeben. Also werden wir überprüfen, ob die Summe gleich 0 ist. Es tut mir leid, wir müssen eine zurückgeben, die angibt, dass wir eine Liste oder eine Teilmenge gefunden haben , die sich an die bestimmte Nummer anpassen kann. Nun, wenn die Summe kleiner als 0 ist, aber wir müssen nicht tun, ist einfach 0 zurückzugeben, was anzeigt, dass wir keinen Betrag oder weniger gefunden haben, der bis zu neun addieren kann. Es ist größer als neun. Nun gibt der Index I kleiner als 0 auch 0 zurück. Und schließlich können wir mit unseren Rekursionsfunktionen oder Rekursionsursachen beginnen. Und die erste besteht darin, zu überprüfen, ob die Summe kleiner ist als diese Liste bei einem bestimmten Index, d. h. wenn dies der Fall ist, dann können wir sie nicht einschließen. Wir werden einfach durch einen Index springen. Und wie machen wir das? Wir werden es in einer Variablen speichern. Lassen Sie mich also damit beginnen, diese Variable hier zu erstellen. Es ist also eine ganze Zahl zurückzugeben und es wird zuerst auf Nullen initialisiert. Nun, was wir tun werden, ist zuzuweisen, in diese rekursive Funktion zurückzukehren. Und es wird die folgenden Parameter nehmen. Die erste ist die Liste insgesamt, und dann ich minus 10, und dann Memo. Und schließlich, sobald wir tun, ist es zu überprüfen, oder es ist die letzte Bedingung. Also müssen wir nicht wirklich überprüfen, welche dann der Rückkehr hinzugefügt werden. Also zurück, es sollte eines von zwei Dingen sein. Es ist entweder die Liste mit der spezifischen Nummer auf der Liste ohne sie. Also mit insgesamt I minus1 Memo plus Rekursionsliste mit insgesamt minus der weniger am spezifischen Auge. Und dann machen wir dasselbe ich minus 1 und Memo. Nun, bevor wir dies zurückgeben, um von hier oder hier zurückzukehren, was wir tun werden, ist, es in unserem Memo zu speichern. Also, wie machst du das? Wir werden Memos schreiben. Und dann werden wir in dieses Memo setzen, diesen Schlüssel, und der Wert ist tatsächlich zurückzukehren. Jetzt endlich können wir einfach unsere Rückgabe-Ganzzahl zurückgeben, die die Anzahl der Teilmengen ist, aber Sie können verwenden. Also, das ist es im Grunde für diese Funktion. Nun, was wir tun werden, ist, die Kälte aufzubauen, die Hauptfunktion, wo wir anrufen werden, genannt diese und unser Ergebnis zu bekommen. Also, wie machen wir das? Ich werde einfach eine Hauptfunktion erstellen. Es tut mir leid. Also lasst uns wieder erstellen. Und in unserer Hauptfunktion, was wir tun werden, ist, eine HashMap zu erstellen. Und es wird eine Zeichenfolge und eine ganze Zahl nehmen, und dies wird unser Memo sein, um gleich neuer HashMap zu sein. Nun, was wir tun werden, ist, unsere Liste zu erstellen, die das Beispiel enthält, das wir getan haben. Also werde ich Array-Liste schreiben, und dies wird eine ganze Zahl hinzufügen. Und dann werden wir es Listen nennen, was einer neuen Array-Liste entspricht. Und ich werde ein paar Dinge hinzufügen. Also listen Sie das auf. Ich werde hier die gleichen genauen Zahlen hinzufügen, um zu überprüfen, ob wir das gleiche genaue Ergebnis erhalten. Also 1345. Also werde ich einfach 1345 hinzufügen. Dann werden wir unsere Gesamtsumme haben. Also, um eine ganze Zahl namens total zu sein, um gleich der Summe zu sein, die wir brauchen, um das im Grunde neun zu wählen. Und schließlich, was wir, endlich, wenn ich als den Index, mit dem wir anfangen werden, das ist i, wird es gleich der Liste sein, diese Größe minus eins. Also, das ist im Grunde für unsere Parameter jetzt können wir unsere rekursive Funktion aufrufen und ausdrucken. So und drucken Sie es einfach direkt aus. So wiederholen Sie auf einer bestimmten Liste, Gesamt I und Memo. Und danach werden wir unseren Code ausführen. Und mal sehen, was wir für ein Alkaloid bekommen werden. Und wir werden zwei als Endwert oder die endgültige Anzahl von Teilmengen, die wir verwenden können, um eine bestimmte Zahl, die 9 ist, zu erhalten. Das ist also im Grunde für die Memoisierung, die eigentlich Rekursion ohne Wiederholung ist. Wie wir sehen können, haben wir genau die gleiche Logik der Rekursion verwendet. Wir mussten jedoch nicht wirklich jedes Mal berechnen, wenn wir einen bestimmten Wert benötigten, wir können sie in einem Array speichern und dann natürlich später zu ihnen zurückkehren, wenn wir sie verwenden müssen. Und das wird sparen, uns viel Zeit sparen, und es wird die Komplexität stark verringern. Also das ist es im Grunde dafür genannt Walkthrough. Wir sehen uns im nächsten Video. 30. Anzahl der JavaScript-Implementierung: Alles klar, in diesem Video werden wir eine Funktion mit JavaScript implementieren. Beginnen wir also mit der Definition unserer Funktion. Also werde ich es wiederkehren nennen, wie wir gesagt haben. Es wird eine Liste nehmen und dann haben Sie die Summe, wir haben den Index und das Säugetier, das wir verwenden werden. Jetzt lass es uns öffnen. Und das erste, was ich tun werde, ist, unseren Schlüssel zu erstellen. Und das wird eine Schnur sein. Also werde ich einfach Totalverlust hinzufügen, dieses Komma plus I. Nun, was wir tun werden, ist zu überprüfen, ob dieser Schlüssel in unserem Memo ist. Also, wie würdest du das machen? Wir können einfach die Funktion verwenden. Wenn dieses Memo, das den spezifischen Schlüssel hat, ist dies der Fall, dann was wir tun werden, ist, einfach das Memo in diesem speziellen Fall zurückzugeben. Also, wie machen wir das? Wir werden Memo nehmen, die an den spezifischen Schlüssel zu bekommen. Und dann werden wir tun, ist einfach mit unserem Code fortzusetzen. Da wir also die rekursive Funktion haben, haben wir in dieser einen die Summe, die gleich 0 ist. Wenn also total gleich 0 ist, können wir es einfach nicht ignorieren und einfach einen als Rückgabewert zurückgeben. Denn das bedeutet, dass wir zu einem Punkt gekommen sind, an dem wir herausgefunden haben, dass wir eine Teilmenge haben, die insgesamt 0 zurückgibt, was unser Ziel überhaupt erreicht hat. Also in diesem Fall werden wir 0 zurückgeben. Andernfalls, wenn die Summe kleiner als 0 ist, bedeutet dies, dass innerhalb einer Form 0 zurückgegeben wird. Und dann, was wir tun werden, ist zu überprüfen, ob ich kleiner als 0 ist, dann gibt es auch 0 zurück. Jetzt können wir mit unseren rekursiven Funktionen beginnen. Also, wenn die Summe kleiner ist als diese Liste in einem bestimmten Index I. In diesem Fall, was wir tun werden, ist, einfach die Funktion wiederkehren, wie wir gesagt haben, und ignorieren, wir haben insgesamt I minus1 und memo. Und es gibt keinen Grund, warum ich minus1 ist, wie wir bereits gesagt haben, wir werden einfach springen. Denn wenn wir zum Beispiel die Liste bei i haben, die gleich 4 ist, und wir haben die Summe, die gleich zwei ist. Und in diesem Fall ist die Summe kleiner als dieser Wert hier. So können wir diesen Wert wirklich in die Teilmenge einfügen. Also werden wir es einfach ignorieren. Das ist also der Grund, warum wir jetzt tun werden, ist, einfach eine definierende Phase zurückzugeben, weniger Gesamt I minus1 Memo plus die Rekursion addieren weniger gesamt minus B. Liste bei i minus1 Lampen sind bei I. Und dann gehen wir um es zu dekrementieren ich minus1 und Säugetier. Was gibt es nicht, dass wir das hier gemacht haben ist, weil wir die letzten beiden Male zurückkehren werden. Die erste ist, dass wir die 5. Zum Beispiel, wenn Sie um fünf sind, wenn wir die vier und die zweite, wenn wir sie nicht einschließen. Das ist also, was wir tun werden. Wir werden einfach das totale Gefahrgut zurückgeben. Das bedeutet, dass wir die vier nicht aufgenommen haben, und das bedeutet, dass wir die vier hier eingeschlossen haben. Also, das ist es jetzt im Grunde, was wir tun werden, ist, dies in eine Variable zu ändern. Anstatt zu tippen, um zurückzukehren, werde ich hier eine Variable benennen, um zurückzukehren, und sie wird gleich 0 sein. Dann sollte die Rückkehr in diesem Fall gleich dieser Funktion sein. Und natürlich werden wir genau das Gleiche hier machen. Es sollte gleich sein. Und schließlich, bevor ich zu dieser Variablen zurückkehre, werde ich es in Zion in diesem Memo speichern, werde Memo verwenden, das besagte, und ich werde es auf dieses Kind setzen das die Rückgabevariable setzt und dann werde ich nur zurückgeben. Also im Grunde für diese Funktion jetzt, was wir tun werden, ist es einfach auszuprobieren. Also werde ich eine Liste von 1345 haben und wir haben insgesamt neun. Und wir haben das I, das in diesem Fall gleich drei ist. Und dann haben wir unser Memo mit Jazz und neuer Karte. Also Gedächtniskarte, und wir sind gut. Das sind also alle Variablen, also lassen Sie mich einfach einen Balken platzieren. Und wir sind gut. Dies ist auch variabel. Nun, was wir tun werden, ist, diese Funktion aufzurufen. Ich werde das variable Ergebnis haben. Beachten Sie, dass für mich diese Funktion mit diesen Parametern aufrufen, so dass die Summe und der Speicher. Und schließlich werde ich es einfach ausloggen. So Konsole protokollieren Sie die Ergebnisse, die wir haben. Nun, wenn wir hier gehen und geben Knotenzahl von Möglichkeiten, die JS, wer kann ich bekommen, wie durch die Anzahl der Möglichkeiten, die wir haben können, um diese neun oder den spezifischen Wert zu erreichen, die wir haben definiert . Dies ist es also für die Implementierung der Anzahl der Möglichkeiten, die Memoisierung und JavaScript verwenden. Wir sehen uns im nächsten Video. 31. Anzahl von Untersätzen Subsets: Alles klar, in diesem Video werden wir unsere Funktion mit Python implementieren. Das erste, was ich tun werde, ist, unsere Funktion zu erstellen und sie zu benennen. Bereiten Sie sich vor Wie gesagt, werden wir die folgenden Parameter nehmen. Die erste ist die Liste. Dann werden wir den tatsächlichen Gesamt-Deep-Index und das Memo haben , das die HashMap sein wird, die wir verwenden, oder das Wörterbuch in diesem Fall. Also das erste, was ich tun werde, ist, tatsächlich den Schlüssel zu erstellen, den wir verwenden werden. Das ist der Gesamt-Komma-Index. Also, wie machen wir das? Ich werde es einfach einen Schlüssel nennen. Und ich werde einfach STR des Gesamtes schreiben plus ein Plus Index I. So STR acti. Und dann, was wir tun werden, ist zu überprüfen, ob das im Wörterbuch ist. Wenn dies ein Memo ist, so F-Taste und Memo, dieser Fall. Dann, was wir tun werden, ist, einfach das Memo an der spezifischen ISO-Rückgabememo zurückzugeben, den spezifischen Schlüssel und wir sind damit fertig. Das ist nicht der Fall. Was wir tun werden, ist, einfach nach den anderen Basisfällen zu suchen. Also der erste Basisfall, wenn wir tatsächlich gelungen sind und zu dem Punkt gekommen sind, wo die Summe gleich 0 ist, werden wir eins zurückgeben, weil wir weg sind, wo wir eine Teilmenge haben, die zu der spezifischen Zahl addieren kann. Nun, wenn die Summe kleiner als 0 ist, dann sind wir nicht zu einem Punkt gekommen, an dem wir eine Teilmenge haben, die bis zu 0 addiert, dann werden wir 0 zurückgeben. Andernfalls können wir auch, wir müssen auch für AI überprüfen, es ist weniger als 0. Dann werden wir auch 0 zurückgeben, was anzeigt, dass wir keine Teilmenge in diesem Zweig dieses Baumes finden, den wir bauen. Jetzt können wir mit unserer rekursiven Funktion beginnen. Funktionen. Und die erste besteht darin, zu überprüfen, ob die Summe kleiner ist als der Index des Wertes, der am Ende außer wir hinzufügen, wenn dies der Fall ist, dann, was wir tun werden, ist eine rekursive Funktion ohne den spezifischen Index zurückzugeben. Also erinnern Sie sich, dass, wenn wir zum Beispiel bei vier sind und unsere Summe zwei ist, in diesem Fall ist die Punktzahl größer als 2 sagt, dass dies bedeutet, dass wir diese vier nicht in unsere Teilmenge hinzufügen können , um die Summe zu haben, die wir haben wollen. In diesem Fall, was wir tun werden, ist, einfach dieses weniger Gesamt I minus 1 mit unserem Memo zurückzugeben . Also, wie machst du das? Wir lassen mich einfach nur eine Variable direkt hier erstellen. Und diese Variable sollte nur durch 0 initialisiert werden. Und dann werden wir hinzufügen, um zurückzukehren, die gleich den rekursiven Funktionen sein wird , die wir Liste Tochter I, minus1 und Säugetiere verwenden. Dann, wenn dies nicht der Fall ist, dann wird uns das mit zwei verlassen. Da natürlich die erste darin besteht, die Liste so zu belassen, wie sie ist, dekrementieren Sie einfach den Index um eins. Und die andere ist, einfach die Liste zu nehmen und die Summe durch die Liste an der spezifischen zu dekrementieren. Es tut mir leid, ich habe vergessen, entweder t Jetzt habe ich minus1 und Säugetiere. Also, was wir hier eigentlich sagen, ist, dass wir das nur für eine Zeit verwenden und es einfach beim zweiten Mal ignorieren werden. Und das ist, was wir hier tatsächlich tun, zum Beispiel, hier werden wir diese vier zur Teilmenge hinzufügen. Und er wird es nicht hinzufügen, indem man einfach die Teilmenge zurückgibt oder sie ohne vorher zurückruft. Und wir werden einen sehen. Es ist üblich, später. Das ist also das Grundsätzliche für unsere Funktion. Nun endlich, was wir eigentlich tun müssen, ist, es einfach zu unserem Memo hinzuzufügen. Also Memo an diesem Messgerät ist gleich zurück. Und dann endlich unsere Rückkehr. Probieren wir es jetzt aus. Was ich tun werde, ist unsere Liste zu erstellen, die genau das ist, was wir hier gebaut haben, 1345. Also listen Sie bei 1345 auf, dann werden wir insgesamt neun haben. Und wir werden auch den Index haben, der eine Drei ist. Es wird beim letzten Element beginnen, das extra drei war. Dann werden wir das Memo haben, das im Grunde ein Wörterbuch ist. Jetzt können wir unsere Funktion aufrufen, ich werde sie in einem Ergebnis speichern und es Ergebnis nennen, das eine Rekursion weniger total und Säugetier sein wird, dann können Sie sie einfach ausdrucken. Also jetzt, wenn wir voran gehen und gehen über CMD, gehen Sie zum Desktop. Und dann durch dynamische Programmierung. Und dann werde ich einfach diesen Code Python Anzahl von Möglichkeiten ausführen , durch die ich eine chaotische bekommen werde. Wir haben also einen ungültigen Syntaxfehler. Und das ist eigentlich, weil wir vergessen haben, die Spalte hier hinzuzufügen und sie Kriterien zu beenden. Also, jetzt, wenn wir zurück und Rückkehr Anzahl von Möglichkeiten, Entschuldigung, so hier haben wir Anzeigen. Das war's also. Jetzt können wir wieder laufen gehen und wir haben zwei als die Anzahl der Möglichkeiten, die wir Teilmengen haben können, die zu der spezifischen Zahl neun addieren können. Das ist also das im Grunde für diese Implementierung dieses Problems mit Python, um Sie im nächsten Video zu sehen. 32. Längste häufige Subsequenz: Hallo und willkommen zurück. In diesem Video werden wir das Problem der längsten gemeinsamen Nachfolge in der S2-Stärke diskutieren . Was wir also haben werden, ist zu Stärke und wir schreiben sie einfach dort hin. Also werden wir x, y, z, w. haben und dann wird das andere x sein, das a w. Nun, bei der Antwort davon ist eigentlich die Länge der längsten gemeinsamen Nachfolge. In diesem Fall ist es gleich drei. Wie haben wir es bekommen? Wir haben x z w, x z, W. So wie wir sehen können, ist x, z und w die längste gemeinsame Nachfolge innerhalb dieser beiden Saiten. Und wir könnten ein paar Buchstaben zwischen ihnen haben, aber die Reihenfolge ist die gleiche, also haben wir Axt als Z und W. Also, wie lösen wir dieses Problem? Eigentlich, unser erster Gedanke, dass wir in die Rekursion gehen würden, da wirdie möglichen Wege oder die möglichen Kombinationen findenmüssen die möglichen Wege oder die möglichen Kombinationen finden , die wir eine jede Teilzeichenfolge haben könnten. Und dann werden wir überprüfen, dass diese Teilzeichenfolge dem anderen Ende entspricht, der zweiten Zeichenfolge. Und wenn die Spiele ihre Länge finden und dann einfach als Ergebnis zurückgeben würden. Und natürlich werden wir die maximale Länge finden , die wir innerhalb dieser beiden Saiten haben können. Wie lösen Sie dieses Problem nur mit dem Papier? Was wir tun werden, ist zu überprüfen, ob die letzten beiden Buchstaben gleich sind. Wenn dies der Fall ist, wie Sie sehen können, ist W gleich W, aber wir werden tun, ist es, sie einfach aus unseren Stärken zu entfernen und wir werden unseren Zähler um eins erhöhen. Also hier haben wir einen. Alles klar, was wir jetzt noch haben, ist eigentlich x, y und z, und die erste Saite und Ax und Ay und die andere. Wenn Sie nun die letzten beiden Zeichen vergleichen möchten, können wir sehen, dass sie nicht übereinstimmen. Was wir tun werden, ist, es mit zwei möglichen Möglichkeiten auszuprobieren. Der erste Weg ist, diese schwindelig zu entfernen und unsere Lösung mit x, y und t aus erster Hand und B x, z und a auf der anderen Seite fortzusetzen y und t aus erster Hand und B x, . Und dann machen wir das Gleiche. Aber jetzt werden wir loswerden ein, so werden wir mit x, y, z, und z verlassen werden . Nun, wenn Sie diesem Pfad folgen , wie Sie sehen können, haben wir x, y, z und a. entweder mit x und z und a, und die andere Lösung sollte x, y und das x sein. Also das erste Mal, wenn wir das y entfernen und das andere werden wir eine entfernen. Nun, denken Sie daran ist, dass wir einen bestimmten Titel finden müssen das ist am Ende dieser beiden Stränge und ein sollte gleich sein. In diesem Fall, wenn wir hier weitermachen, werden wir mit x und x an einem Ende enden. Und in diesem Fall haben wir einen gefunden, der passt. Was wir also tun werden, ist, unseren Zähler hier zu erhöhen. Und dann natürlich, wenn wir weitermachen, Hey, werden wir auch mit x und x enden . Was wir eigentlich tun werden, ist, zum Beispiel an dieser Stelle zu überprüfen. Nehmen wir an, wir sind hier. Was wir tun werden, ist, das Maximum zwischen dem linken und rechten Teilbaum zu überprüfen. Und in diesem Fall sind sie gleich, also werden wir nur eine 1 zurückgeben. Jetzt werden wir genau das Gleiche an dieser Stelle machen. Wir haben diesen Zweig jedoch noch nicht beendet. Also lassen Sie mich es einfach beenden. Wir werden hier weitermachen. Wir haben x, y, z und z. Sie sind gleich. Was wir tun werden, ist, diese schwindlig aus Heu zu entfernen und den Zähler um eins zu erhöhen. Und natürlich werden wir mit x, y und x auf der ersten Seite enden , und wir werden x und x haben, und auf der anderen Seite, tut mir leid, lassen Sie mich einfach löschen. Also werden wir einmal haben, x und x beim zweiten Mal, als XY und nichts zu haben. Und wenn wir nichts oder eine leere Zeichenfolge haben, wir einfach 0 zurück, da wir gerade an einen Ort gegangen sind, an dem keine solche Zeichenfolge oder Zeichen übrig sind. Und eine der Stärken, also werden wir nur 0 zurückgeben, was anzeigt, dass wir nichts gefunden haben, bis wir X und X haben. Sie sind gleich, also sollten wir auf eins passen. Wenn wir also an dieser Position sind, x, y und x, werden wir nur das Maximum zwischen diesen beiden Stärken nehmen und es ist tatsächlich gleich eins. Also hier haben wir einen. Und wenn wir in dieser Phase sind, X, Y und Z, wir das Maximum zwischen dem darunter liegenden zurückgeben, das ist eigentlich nur x, y und fügt hinzu, und wir werden eins haben. Also 1 plus 1 sollte gleich sein, sollte gleich zwei sein. Und in diesem Fall werden wir das Maximum zwischen diesen beiden Zweigen zurückgeben. Also wirst du einen haben und hier haben wir zwei. Wir müssen also, und natürlich werden wir mit 2 plus 1 enden, was eigentlich gleich drei ist. Das war's also. Im Grunde ist dies der Baum, den wir bauen können. Und was wir eigentlich sagen, ist, dass, wenn wir zwei Stärken haben, die zusammenpassen. Zwei Zeichen, die einander gleich sind. Aber wir werden tun, ist, sie einfach zu entfernen und unsere Arbeit fortzusetzen. Wir haben jedoch zwei Schritte, um dies zu tun. Wir entfernen entweder nur beschäftigt oder entfernt die a. Und wir werden herausfinden, welche sich bei der maximalen Teilzeichenfolge oder Untersequenz befindet , die entweder mit x, y, z und a oder X, Y,Z und X, Z und dem anderen Fall zurückgegeben werden kann y, z und a oder X, Y, . Und ich werde nur das Maximum zurückgeben. Und natürlich, wenn wir zwei Zeichenfolgen oder zwei Zeichen haben, die übereinstimmen, werden wir es um eins erhöhen. Das ist es im Grunde für diese Just Lösung, rekursive Lösung. Und was wir jetzt tun werden, ist tatsächlich einen Pseudocode zu schreiben, der uns hilft. Und die nächste Phase, in der wir es optimieren werden. Und wir werden eine Lösung mit dynamischem Programm finden. Bevor Sie das tun, lassen Sie mich einfach über die Zeitkomplexität nachdenken. Wenn wir über die möglichen Kombinationen in einer Zeichenfolge nachdenken und Statistiken verwenden, werden wir herausfinden, dass, wenn Sie eine Reihe von vier Buchstaben haben , sagen wir X, Y, Z und W. Sie könnten von hier aus nehmen. Wir können entweder x, X, Y, XYZ haben, dann haben wir y, y, z, y, w und so weiter und so weiter. Und dieser Fall, was wir haben werden, ist eigentlich eine Kombination aus ein paar Dingen. Zum Beispiel, wenn Sie eine Kombination aus nur x haben, werden wir eine Kombination aus eins und c1 haben. Und dann, wenn Sie zwei Buchstaben haben, X und Y werden und C2 haben. Und dann NC3 den ganzen Weg bis B und c. Und wir werden alle Buchstaben in der Zeichenfolge einschließen. Also, und das ist tatsächlich gleich zwei der Macht n. Und wie Sie es sehen können, Exponential. Nun, dies ist nur, um die möglichen Kombinationen in einer Zeichenfolge zu berechnen. Wir haben also zwei Stärken. Wir müssen es mit zwei multiplizieren. Und dann werden wir es mit n multiplizieren.Und das n ist, weil wir die Subsequenz berechnen müssen , wenn es in den beiden Strings üblich ist. Also werden wir herausfinden, ob das üblich ist, die beiden Stränge. Also werden wir von 0 den ganzen Weg zu n. und in diesem Fall ist es tatsächlich auf die Macht n mal n. So können wir diese beiden loswerden. Also ist die Zeitkomplexität und zwei. Und wie Sie sehen können, und das ziemlich groß und haben zwei lange Saiten, können wir wirklich damit arbeiten und haben eine minimale Zeit. Also, was Sie jetzt tun werden, ist, den Pseudocode zu schreiben und dann werden wir einen Weg finden, um die Lösung zu optimieren. Also lassen Sie mich diese einfach loswerden und ich werde diese auch löschen. Nun, was ich tun werde, ist mit Pseudocode zu beginnen. Aber lassen Sie mich einfach alle diese und kleinere nehmen, setzen Sie sie hier. So können wir jetzt mit Pseudocode beginnen. Was wir eigentlich tun werden, ist mit den Parametern zu beginnen. Also werde ich die Funktion nur als längste gemeinsame Nachfolge benennen. Und in diesem Fall wird es vier Parameter nehmen. Der erste ist Penguin, die zweite Zeichenfolge 2, und dann haben wir die Position oder die Indizes, die wir hinzufügen. Also, wenn wir sagen, wir werden das löschen, oder wir gehen zu diesem. Wir werden einen Index nehmen, der nur darauf hinweist, dass dies oder das, oder irgendein spezifisches Zeichen innerhalb dieser beiden Stränge. Also für s1 werden wir Axt haben und für uns y haben und das erste, was wir anfangen werden, ist unser Basisfall. Der Basisfall ist also, wo wir einfach rückgängig machen und unsere Funktion, und es wird tatsächlich sein, was auch immer wir eine leere Zeichenfolge haben. Also, wie finden Sie, wenn Sie eine leere Zeichenfolge haben? Wie gesagt, wenn x oder y gleich 0 ist, wie in diesem Fall, wo wir X, Y haben, und hier haben wir eine leere Zeichenfolge. Also derjenige, der die Position anzeigt, dass wir in S2 sind. Also sind wir in diesem Fall an Position 0 oder minus eins. Und wenn wir die haben, wir, wenn wir an dieser Position sind, was wir tun werden, ist einfach 0 zurückzugeben. Also fx gleich 0 oder y gleich 0. Wir werden nur 0 zurückgeben. Jetzt können wir mit unseren rekursiven Aufrufen beginnen. Wir haben also zwei Dinge, auf die wir achten sollten. Also f, das letzte Zeichen ist gleich. Also, wenn das letzte Zeichen S1 bei x minus eins und gleich S2 bei y minus 1. Das ist der Fall. Dann werden wir nur unsere Arbeit fortsetzen. Natürlich können wir unseren Zähler erhöhen, was das ist, was wir zurückgeben werden. Also sollte dies tatsächlich von Integer geschrieben werden. Also werden wir einen zurückgeben. Außerdem werden wir die Funktion aufrufen. Aber wir werden nur Öl entfernen, unsere Zähler um eins verkleinern. Also, wenn wir an dieser Position sind, w und w nur zu dekrementieren, wäre es bei z und a in diesem Fall. Also, wie machen wir das? Wir werden einfach die längste gemeinsame Nachfolge bei S1, S2 zurückgeben. Wie üblich haben wir jedoch x minus 1 und y minus 1. Nun, wenn das auch nicht der Fall ist, haben wir zwei Dinge zur Auswahl. Wir sagten, dass wir das Maximum zwischen dem linken Baum und dem rechten Baum berechnen müssen. Also, wie machen wir das? Einfach das Maximum zwischen zwei Dingen zurückgeben. Das ist die längste gemeinsame Nachfolge. So längste gemeinsame sub S1, S2 x minus 1 y. Also die erste, wir sind nur gehen, um das erste und letzte Zeichen und das erste, was zu entfernen. Und die zweite, wir werden das letzte Zeichen in der zweiten Stärke entfernen, so längste gemeinsame Nachfolge. Und in diesem Fall werden wir S1, S2 zurückgeben , und dann haben wir x und y minus eins. Also lass mich sie einfach hier schreiben. Also haben wir S1, S2, und dann haben wir x und y minus eins in diesem Fall. Das ist es im Grunde für unsere rekursive Lösung. Und wie wir sehen können, wird es zu viel Zeit dauern, da wir dasselbe immer und immer wieder berechnen werden. Zum Beispiel, hier werden wir mit x und x und x und x, x und x und x, x und x. Und natürlich werden Sie hier weitermachen. Wir werden auch mit x und x enden, also werden wir es in diesem Fall mindestens vier Mal berechnen. Und wie wir sehen können, werden wir einfach eine Menge Dinge mehrere Male berechnen. Unsere zweite Lösung sollte also auf dynamischer Programmierung basieren, und wir können diese immer und immer wieder neu berechnen. Das ist es im Grunde für dieses Problem mit Rekursion. Im nächsten Video werden wir es nur optimieren. So sehen wir uns dann. 33. Längste häufige Subsequenz Pseudo-Code: Okay, jetzt in diesem Video werden wir unsere dynamische Programmierung Implementierung des längsten gemeinsamen Folgeproblems diskutieren . Also werden wir tatsächlich Tabulationen für diese Lösung verwenden. Was wir also tun werden, ist, unsere Werte zu speichern, sind unsere Ergebnisse in einem 2D-Array und verwenden sie dann jedes Mal, wenn wir sie betrachten müssen. Lassen Sie mich also einfach damit beginnen, den Pseudocode der vergangenen Funktion zu löschen. Und wir werden tatsächlich tun, ist ein 2D-Array zu erstellen. Und ich werde in einer Sekunde erklären, warum. Aber dieses 2D-Array würde tatsächlich unsere zwei Strings enthalten. Also, wie gesagt, wir haben x, y, z und w, und dann Z und W. Also hier haben wir Stöße würde nur annehmen, dass wir eine leere Zeichenfolge haben. Dann haben wir x, y, z, w. Dann werden wir eine leere Zeichenfolge x, z, Dann werden wir eine leere Zeichenfolge x, z,a und W. Also, was wir tun werden, ist zu beginnen, indem wir annehmen, dass wir eine leere Zeichenfolge hier haben und Sie eine leere Zeichenfolge hier haben. Und wir werden nur die längste gemeinsame Nachfolge bekommen. Und in diesem Fall ist die längste gemeinsame Nachfolge eine leere Zeichenfolge, die Länge 0 ist. Nun, wenn wir hier zum zweiten Platz gehen, haben wir eine leere Saite und Taten, die wir sehen können. Die längste gemeinsame Nachfolge, die Sie haben können, ist tatsächlich auch die Länge 0. Und hier haben wir, wir werden mit y und leeren Strings am Ende der Zeichenfolge und W und leere Zeichenfolge fortfahren . Und wir werden es einfach mit Nullen füllen und einfach das gleiche hier berechnen, leere Zeichenfolge mit all diesen Buchstaben. Also werden wir mit Nullen auf beiden Seiten enden. Jetzt gehen wir weiter und kommen zu diesem Punkt, wo wir Axt und Axt haben. Und was wir eigentlich tun werden, ist, wenn wir X und X haben, aber wir werden tun, ist dieses x von hier und von hier zu entfernen, wie wir es mit diesem w getan haben. Also, wenn Sie w und w haben, und wir haben es tatsächlich getan, ist, die w und überprüfen Sie dann die x, y, z und Genauigkeit. Also, das erste Mal, dass wir das haben, zum Beispiel. Wenn dies also der Fall ist, wo wir X und X haben, dann werden wir das einfach entfernen und das überprüfen , das nicht das letzte Zeichen enthält. Also, wie machen wir das? Wir werden nur diagonal überprüfen, denn wenn wir X von hier und x von hier entfernen, werden wir mit leer und leer enden, was hier ist. Also werden wir einen zu dem Wert von hier hinzufügen, der 0 ist. Also werden wir hier mit einem enden. Jetzt werden wir weitermachen. Wir haben x jetzt und x, y in diesem Fall. Also sind wir bei diesem, wir werden x, y und x haben. Die längste gemeinsame Nachfolge ist eigentlich, nach unserer Regel, die wir vorher ausgedacht haben, ist, wenn wir zwei Zeichen haben, die nicht übereinstimmen, in diesem Fall haben wir x, y und Ax. Was wir tun werden, ist, zuerst nach X und X zu suchen, und dann haben wir, also wird er x, y und x haben. Das erste Mal, dass wir den Draht entfernen. Und das zweite Mal werden wir das Xo entfernen. Wir haben X und X und X, Y und leere Zeichenfolge. Also, wie haben wir diese Informationen bekommen? Wir holen sie von dem vorher. Wenn wir uns das vorher ansehen, werden wir herausfinden, dass wir X und X haben. Und wenn wir nach oben schauen, werden wir herausfinden, dass wir x, y und eine leere Schnur haben . Also werden wir das Maximum zwischen diesen beiden nach unserer Regel berechnen. Also haben wir 10, das Maximum ist eins, also füllen wir es mit einem aus. Wir machen genau das Gleiche für XYZ und Ax, wir werden hier einen und einen hier haben. Also, wenn Sie über dieses x, y, z und w gehen wollen und wenn Sie also x, y, z und w und x haben , was wir tatsächlich bekommen werden, weil die letzten Zeichen in diesen beiden Strings nicht übereinstimmen. Wir werden mit X, Y, Z und X fortfahren . Und der andere sollte x, y, z, w und eine leere Zeichenfolge sein. Und in diesem Fall, wie siehst du sie an? Wir werden nach links schauen und wir werden mit XYZ enden und handeln, wie wir sehen können, das ist es. Also ist es 1. Und wir haben auch x, y, z und w, und eine leere Zeichenfolge, die tatsächlich 0 ist. Also ist das Maximum zwischen ihnen tatsächlich eins. Also einfach unsere Gruppe implementieren und finden, was wir von früheren Berechnungen wollen. Jetzt werden wir mit xy und x fortfahren. In diesem Fall, was wir tun werden, ist, nach links zu schauen und knapp über sowjetische 0 oder eins, wir werden mit einer gleichen Sache hier fortfahren. Wir haben 1 und 1, 1, 1. Und natürlich haben wir hier x z und x, y, z, in diesem Fall z und die Streichhölzer. Also, was wir tun werden, ist, eins hinzuzufügen und auf die Diagonale zu schauen. In diesem Fall haben wir eine und wir werden eine hinzufügen. Also eins plus eins, wir werden nur zwei in diesem Fall statt eins speichern. Und wenn du es dir ansiehst, ist die Art und Weise, wie wir es vorher zu tun hatten , wenn du x, y und z hast und dann x, z haben, aber wir haben es tatsächlich getan, diese z und z zu entfernen, werden wir mit x enden, y, und x. Wir werden nur mit Taten und Todesfällen in der letzten Phase enden, wo wir hier eine und hier eine haben, werden wir mit zwei als endliche Antwort enden. Also, wie machen wir das? Wir schauen uns einfach die vorherigen Berechnungen an, ohne x, y und x zu berechnen. Noch einmal werden wir nur den Wert nehmen, den wir gesehen haben, ein. Also ist es 2. Und natürlich werden wir hier mit allen SO2 landen. Jetzt hier haben wir 0 oder 1, das ist 1, 1 oder 1, 2 wollen auch ein oder zwei mit 22 oder zwei enden. Ich werde einfach mit auch enden. Jetzt gehen wir den ganzen Weg bis zum Ende. Wenn wir uns das ansehen, haben wir x, z, a, w x, y, z und w. Und in diesem Fall, wie wir sehen können, w und w, dass das gleiche. So können wir nur 12 hinzufügen, die eine Diagonale, tun Sie es, das ist zwei. Also werden wir in diesem Fall mit drei als Endwert enden. Was wir also tatsächlich getan haben, ist, dass wir die rekursive Lösung verwendet haben. Wir speichern es jedoch nur unsere Aufgabe, die Ergebnisse, in diesem Fall 2D-Array, und wir verwenden sie einfach, wann immer wir wollten. Also, anstatt es zu berechnen, jedes Mal, wenn wir etwas wollen, werden wir es speichern besteht Array. Und wie wir sehen können, können wir es hier oder hier oder hier benutzen. Denken Sie also daran, dass wir zwei rekursive Aufrufe haben. In der vorherigen Lösung haben wir diejenige, wenn sie übereinstimmen, und in diesem Fall ist es diagonal und wir haben die, wenn sie nicht übereinstimmen, wir werden das Maximum zwischen diesem oder diesem nehmen. Also zuerst werden wir ein Element aus diesem Array oder dieser Zeichenfolge entfernen. Und dann werden wir ein Element aus dieser Zeichenfolge entfernen und wir werden das Maximum berechnen und es hier zurückgeben. Also im Grunde für dieses Problem jetzt, was Sie tun werden, ist die Implementierung mit Pseudo-Code. Und dann werden wir es natürlich in unseren Sprachen umsetzen. Also tun Sie das, lassen Sie mich einfach löschen und diese minimieren. Und natürlich, was ich tun werde, ist, das zu löschen. Und ich werde das alles nehmen und es hier platzieren. Jetzt können wir mit Pseudocode beginnen. Das erste, was wir tun werden, ist, eine Funktion aufzurufen. Ich werde es am längsten nennen. Gemeinsame Nachfolge wie gewohnt. Jetzt müssen wir ArrayList oder Array oder eine Liste. Also werde ich sie nur berechnen, da nur S1 eine Liste ist. Speichern Sie das und stand als Liste. Und natürlich werden wir die Indizes haben, an denen wir uns befinden. In diesem Fall werde ich es x und y nennen. Nun, das erste, was wir tun werden, ist, unsere Array 2D-Matrix zu bauen und nur die längste gemeinsame Subsequenz genannt, LTS. Und es wird 2D sein. Und natürlich, was wir tun werden, ist anzunehmen, dass wir bei Nullen und leeren Strings haben. Die Länge davon sollte also von Länge oder Größe x plus 1 sein. Also x plus eins, y plus 1. Jetzt können wir mit unseren for-Schleifen beginnen. Wir werden es füllen dieses 2D-Array. Und so haben wir den ersten, der von 0 bis x geht, oder die Länge davon. So wird es den ganzen Weg bis x plus 1 sein. Und dann haben wir ich plus 1, ich plus, plus, so dass ich von 0 zu diesem. Und dann haben wir vier j von 0 bis y plus 1. Natürlich y plus 1, eins ist nicht enthalten, oder keines ist x plus 1. Und dann haben wir j plus plus. Und jetzt können wir mit M-Lösung beginnen. Das erste, was wir tun werden, ist, wenn entweder i oder j gleich 0 ist, sie einfach mit Nullen füllen. I gleich 0 oder j ist gleich 0. Was wir tun werden, ist die LCS i, j mit 0 zu füllen. Dann werden wir überprüfen, ob x an einer bestimmten Position als gleich. In diesem Fall werden wir uns um eins zurückbewegen und dann werden wir die spezifische Position speichern. Also, wie machst du das? Denken Sie daran, dass wir S1 und S2 als Partner als Liste haben. Und in diesem Fall, was wir als S1 haben werden, wie dieses x, y, z und w S2 sollte von x, z, a und w sein. Jetzt, wie Sie hier sehen können, haben wir den Index dieser Achse ist 0. Wenn Sie sie jedoch in dieser 2D-Matrix berechnen möchten, befindet sich dies bei Index 1. Also hier haben wir 0, 1, 2, 3, 4. Also, wann immer wir damit arbeiten wollen, sollten wir einfach um eins verkleinert werden. Also, um das zu tun, was wir tun werden, ist zu überprüfen, ob, lassen Sie mich einfach etwas kleiner machen und einfach abnehmen, das auch kleiner machen. Und jetzt können wir arbeiten. Das erste, was wir tun werden, ist zu überprüfen, ob sonst. Dieses spezifische Zeichen, das wir sind, ADH ist tatsächlich gleich dem spezifischen Zeichen, das wir hatten und die zweite Zeichenfolge. Also, wenn s1 bei einem bestimmten x minus 1 gleich S2 bei einem bestimmten y minus 1. Das ist der Fall. Was wir tun werden, ist bei LCS x zu füllen, y, es tut mir leid, hier haben wir I und j also i und j. Und natürlich hier haben wir ich und j. Also, wenn sie gleich sind, wir tun, ist, die eine zu nehmen. Sie werden es tun. Also, wie machst du das? A I minus 1, j minus 1 und erhöht um eins. Und das gibt es nicht. Wir gehen davon aus, dass wir den Zustand bei einem Schwan I minus 1 einnehmen. J minus 1 liegt daran, dass unsere Listen tatsächlich mit dem Index 0 gedacht haben. Unsere 2D-Matrix berechnen wir zunächst für die leere Zeichenfolge. Also x hier ist eins und es ist bei 0 genau hier. Also, wie machen wir das? Wir nehmen einfach I minus1, was ist, wenn Sie an diesem Index I sind, gleich eins ist, und nehmen Sie einfach das, wir werden 0 minus 1 nehmen, was 1 minus 1 ist. Wir nehmen 0 und wir können dieses X von der Liste als eins bekommen. Also haben wir j minus y und dy minus eins. Wenn dies der Fall ist, dann werden wir es nur von der diagonalen Position berechnen. Wenn das nicht der Fall ist, werden wir am Ende mit dem letzten, was wir tun werden ist, das Maximum zwischen zwei Dingen zu berechnen. Die erste ist diejenige an der linken Position und die zweite ist diejenige darüber. Also, wie machen wir das? Wer wird nur nehmen und in der LCS i und j gespeichert also LCS, lassen Sie mich einfach hier schreiben. Ich werde das hier einfach hierher bringen. Und ich werde schreiben, dass SES bei I und J gleich dem Maximum zwischen zwei Dingen. Also das Maximum zwischen dem LCS bei I minus 1 und j, wie es ist, oder das Maximum, oder die zweite, die LCS bei I und j minus 1. Also das ist im Grunde für Gott, das ist unsere dynamische Programmierlösung. Wir haben gerade alle möglichen Implementierungen mit nur einem 2D-Array berechnet. Nun, wenn wir über die Zeitkomplexität nachdenken, wenn wir m als haben, haben wir x und y als die Länge von S1 und S2, und wir bauen unsere 2D-Matrix auf. Wie wir sehen können, haben wir x, y, eine zeitliche Komplexität unseres Codes. Und dann sollte unsere Lösung die letzte sein und unsere 2D-Matrix, die in diesem Fall drei ist. Also, das ist es im Grunde für dieses Problem. Und das nächste Video werden wir es mit unseren Sprachen implementieren. So sehen wir uns dann. 34. Längste gewöhnliche Subsequence: Alles klar, in diesem Video werden wir unsere Funktion mit Java implementieren. Also das erste, was ich tun werde, ist, die Funktion zu erstellen. Es sollte öffentlich, statisch, ganzzahlig sein. Und ich werde es gemeinsame Nachfolge nennen, und es wird die folgenden Parameter nehmen. Die erste ist ein Array namens S1. Dann haben wir eine andere ist, die Indizes x oder x und y zu haben. Also jetzt, was wir tun werden, ist unser 2D-Array zu erstellen und es wird von Größe sein und nennen es entlang. Und in diesem Fall sollte die Länge x plus 1 und y plus 1 sein. Jetzt können wir mit unseren for-Schleifen beginnen. Also, wie wir gesagt haben, werden wir tun, ist durch alle diese von 0 bis x und von einer 0 zu y. also für eine erstellen Sie eine for-Schleife. Und in diesem Fall, um den ganzen Weg zu gehen, ja, wer hätte die lange Inhaltsgröße oder die Länge verwenden können? Und die zweite wäre eigentlich den ganzen Weg bis y. Nun, was wir tun werden, ist zu überprüfen, ob ich gleich 0 oder j gleich 0 ist, würde einfach behaupten, dass der Islam bei I sein sollte und j gleich 0 sein sollte. In diesem Fall hätten wir es einfach ignorieren können, denn wenn wir ein 2D-Array für die Matrix oder ein Array in Java erstellen, ist der Standardwert tatsächlich 0, also können wir das einfach ignorieren, aber wir werden es als Pseudocode tun. Also behalte es einfach hier. Nun, das ist nicht der Fall. Wir werden überprüfen, ob die S1 bei I minus 1 gleich S1 Add j minus 1 ist. Also, wenn S1 bei I minus 1 gleich dem S2 bei j minus eins ist. Wenn dies der Fall ist, was wir tun werden, ist Anzeigen lang I und j, die eine diagonal zu ihm zu platzieren . Wie machst du es? I minus 1, j minus 1. Und dann fügen wir ihm eine Eins hinzu. Und natürlich, wenn dies nicht der Fall ist, haben Sie immer noch die letzte Bedingung, die darin besteht, das Maximum zwischen dem links und dem oben genannten zu überprüfen. Also werden wir mit langfristigen I und J beginnen. Das Maximum um um. Also math.max, die Lunge bei I minus ein j und langfristig bei I j minus 1. Also, das war's. Im Grunde ist dies unser tatsächlicher Code. Nun, was wir tun werden, ist, einfach den letzten Wert zurückzugeben, der an der X und W ist. Also nachdem wir von diesen zwei for-Schleifen beendet haben, die einfach die Lunge,die x und y zurückgeben . , Ich werde tun, ist eine Hauptfunktion zu erstellen, wo wir oder so unsere Variablen implementieren werden, dann werden wir die Funktion aufrufen. Also werden wir S1 haben, um im Grunde gleich einer Liste oder einem Array von x zu sein . Dann y, es tut mir leid, ich werde sie nur als Zeichen setzen, so x, y, und dann haben wir z und w Z und w. Schließen Sie es, und wir haben S2, das ist auch ein Array von X, Z und W. So x, z, und dann haben wir ein und w. Jetzt sind wir gut. Wir können mit den tatsächlichen x und y fortfahren. Dies sind also die Indizes, die bei sein sollten. Dies ist also die Länge, die in diesem Fall vier ist. Also sowohl x als auch y gleich 4. Jetzt habe ich vergessen zu tun, ist, die Funktion auszudrucken. Also werde ich das Ergebnis, die eigentliche Funktion speichern und es dann natürlich ausdrucken. Also werde ich das Ergebnis ausdrucken. Wir haben einen Tippfehler, das ist w. Nun, wenn wir voran gehen und diesen Code ausführen, was wir tun werden, um eine CI zu bekommen, ist drei, was anzeigt, dass dies die Anzahl der Zeichen oder die Länge seiner Untersequenz, die wir haben. Nun, um es zu visualisieren, was Sie tun werden, ist, einfach jedes Mal auszudrucken, wenn wir diese Schleife betreten. Dann drucke ich unsere Position aus. Und natürlich werde ich hier Platz und gedruckte Linie haben. Wenn wir jetzt voran gehen und diesen Code ausführen, erhalten Sie das gleiche exakte Ergebnis, das wir genau hier erstellt haben. Wir haben Nullen, Einsen, Zweien, und die letzte ist eigentlich drei, was darauf hinweist, dass dies unser Ergebnis hier ist. Das war's also für dieses Beispiel. Dies ist die Implementierung dieses Codes unter Verwendung von Java. 35. Längste häufige Subsequence: Okay, in diesem Video können wir unsere Funktion mit JavaScript implementieren. Also das erste, was ich tun werde, ist, die Funktion zu erstellen. Ich werde die längste gemeinsame Nachfolge ausgeben. Und es wird die folgenden Parameter nehmen. Also haben wir S1, S2, sind zwei Listen und Arrays. Und wir haben auch die Indizes und nennen sie x und y. Jetzt können wir diese Funktion öffnen. Und jetzt, was wir hier tun werden, haben wir einen Tippfehler. Das ist also Funktion. Nun, was wir tun werden, ist, unser Array zu erstellen. Also werde ich es benennen. - Vielleicht. Und in diesem Fall könnte es ein neues Array der Größe x plus 1 sein. Und natürlich werden wir in jeder Position ein neues Array haben und es tun. Ich werde es in einer Sekunde tun. Also sollte unsere erste for-Schleife bei I gleich 0 beginnen, dann bis x eingeschlossen und dann inkrementiert werden. Jetzt sollte die zweite for-Schleife sein, sollte bei j gleich 0 beginnen. J ist kleiner oder gleich y und erhöht j und natürlich jedes Mal, wenn wir zu einer Position von I kommen, werden wir ein neues Array erstellen, y plus 1. Nun, was wir tun werden, ist zu überprüfen, ob ich gleich 0 oder x ist, es tut mir leid, oder j ist gleich 0. Das ist also der Fall. Was wir tun werden, ist, einfach bei I und j im Wert von 0 zu speichern. Nun, wenn das nicht der Fall ist, werden wir überprüfen, ob an Position S1 und S1, S2 J minus eins. Wenn sie gleich sind, dann werden wir einen Tensor tun, als ob Disposition, die S1 bei I minus 1 gleich S2 bei J minus1 ist. Das ist der Fall. Was wir tun werden, ist i und j um eins plus d Wert zu erhöhen , der an dieser Position ist, I minus 1, j minus 1, was die diagonale Position des spezifischen Wertes ist. Wenn das nicht der Fall ist, werden wir das Maximum zwischen zwei Dingen nehmen. Der erste befindet sich an der Position, die sich links befindet, und der zweite, der sich oben befindet. Also, was wir tun werden, ist, an dieser spezifischen Position zu beginnen, die ich j ist. Das Maximum zwischen dem ersten, das eine langfristige bei I minus eins ist und, und es tut mir leid j. Und dann das lange I und j minus 1, dieser Fall. Nun, das ist unser Code. Schließlich, nachdem Sie diese beiden for-Schleifen beendet haben, müssen Sie einfach den letzten Wert zurückgeben , den wir erhalten haben , der der lange ist y. , kommen Sie bei x und , kommen Sie bei x undy. Beginnen Sie einfach mit der Erstellung von Listen von x, y. Dann werden wir z und w. Z. Z. Dann haben wir w. Und wir haben Liste von, lassen Sie mich einfach nennen sie Variablen. Also haben wir Variablen. Und in diesem Fall sollte der zweite von x, y a, es tut mir leid, x, z und a und W. Also x, z, a und W. Und jetzt endlich, was wir tun werden, ist, die Indizes zu haben, die bei Position 4 für jetzt. Also var x gleich 4, y, was auch gleich vier ist. Nun, was wir tun werden, ist, einfach die Funktion aufzurufen und zu sperren. Also werde ich es im Ergebnis speichern. Komm hoch und wir werden es S1, S2, x und ynennen S2, x und y und dann werde ich es endlich ausloggen, so dass Set. Nun, was wir tun werden, ist, zu unserem cmd zu gehen. Und natürlich können wir unsere Desktop- und JavaScript-dynamische Programmierung hinzufügen. Das ist so schlimm. Und dann werden wir natürlich unseren Code mit Node C dot js ausführen. Wenn wir unseren Code ausführen, werden wir drei als endgültigen Wert erhalten , den wir von dieser Funktion erhalten haben. Und das ist die längste gemeinsame Nachfolge, die wir bekommen können. Das ist x, y, und w nichts, was wir tun werden, ist, diese Funktion oder diese 2D-Matrix, die wir gerade hier erstellt haben, zu visualisieren. Anstatt also den letzten Wert zurückzugeben, werde ich das gesamte 2D-Array, 2D-Matrix, zurückgeben. Und wenn wir es wieder ausführen, werden wir genau das gleiche Ergebnis erhalten, das wir hier von Hand gebaut haben. Wie Sie sehen können, haben wir Nullen, Einsen und den ganzen Weg bis zum letzten, was eigentlich eine Drei ist, die zum Beispiel für dieses Beispiel die Implementierung dieses Problems mit JavaScript ist. 36. Längste häufige Subsequenz Subsequence: Alles klar, in diesem Video werden wir tun, ist die Funktion tatsächlich mit einem Python zu erstellen. Also werde ich nur diese Dateisequenz erstellen. Und mittlerweile werden wir mit unserer Definition oder der Funktion beginnen, die wir benutzen werden, um nur Lungenkrebs darzustellen und die folgenden Parameter zu übernehmen. Also haben wir S1, S2. Sie haben auch x und y als die Parameter oder die Indizes, die wir verwenden werden. Das erste, was ich tun werde, ist, das längste gemeinsame U-Boot zu erschaffen. Und das wird die Liste sein, die wir verwenden werden. Und tatsächlich eine Liste von Listen zu sein. Und der erste sollte für mich im Bereich von x plus 1 sein. Und dann wird die zweite Einheit natürlich im Bereich von y plus 1 liegen. Also, das war's. Nun, was wir tun werden, ist, mit unserer for-Schleife zu beginnen. Also im Bereich von 0 bis x plus eins zu sein, da x plus 1 nicht enthalten ist. Also ist dies der erste, da für die zweite von 0 bis y plus 1 tief verwurzelt wäre. Nun, was wir tun werden, ist zu überprüfen, ob i oder j gleich 0 sind. Wenn ich gleich 0 ist oder j gleich 0 ist, ist dies der Fall. Was wir tun werden, ist einfach an dieser Position zu implementieren oder hinzuzufügen, die spezifische Position bei I und j hat einen Wert von 0. Wenn dies nicht der Fall ist, werden wir prüfen, ob bei Assuan High minus 1 gleich S2 minus S1 ist. Also S1 I minus 1 gleich S2 bei j minus eins. Also, wenn dies der Fall ist, was wir tun werden, ist, einfach den Diagonalwert zu nehmen, den wir haben und ihn mit Inkrementierung eines von sich selbst speichern. Längste gemeinsame Nachfolge bei I minus 1, j minus 1, und wir werden eins hinzufügen, und das war's. Die letzte Bedingung, die wir haben werden , ist, dass, wenn diese beiden Bedingungen nicht zutreffen, wir nur das Maximum zwischen zwei Dingen speichern. Der erste, der links ist. So wird es das Maximum zwischen der längsten gemeinsamen Nachfolge, I minus1 und j, das ist die vertikale, also ist es oben. Und der zweite wird bei I sein und dann j minus 1. Das ist es im Grunde jetzt, nachdem Sie dies nach links oder zum Array gegraben haben, müssen Sie einfach die Werte an den spezifischen Indizes zurückgeben. Jetzt, um es auszuprobieren, wenn Sie tun, ist, einfach die Liste zu erstellen. Also haben wir x, y, dann haben wir z und w. Dann haben wir S2, die aus x besteht. Wir haben z, dann haben wir ein, und dann haben wir w. Das ist es im Grunde jetzt wie für die Axt gleich vier, y gleich 4. Jetzt drucken wir es aus. Wir werden s1, S2, x und y drucken, also schauen wir es uns jetzt an. Ich gehe hier rüber und ich werde mit dynamischer Programmierung zu gehen. Fünf, sorry, so dynamisch, sorry, wir haben irgendwelche Tippfehler und wir werden tun, ist einfach den Code ausführen. Also, jetzt werden wir es mit Python und Python ausführen. So längste gemeinsame Nachfolge Punkt py. Also hier haben wir einen Fehler. Es tut mir leid, hier haben wir LCF verwendet, wir haben LF und Python. Also, LF, Python. Also müssen wir auch bezahlen und was wir das tatsächlich getan haben, nennen wir die Funktion und drucken sie aus. Also lass es mich einfach aufbewahren, es tut mir leid. Und als Ergebnis werde ich es einfach platzieren und Fehlerergebnisse und dann einfach anrufen oder ausdrucken, nachdem ich mit der Berechnung des Wertes von Salz fertig bin. Nun, danach, was wir tun werden, ist einfach hier zu gehen und wieder zu ziehen. Und wie wir sehen können, haben wir drei, den endgültigen Wert, der die längste gemeinsame Nachfolge ist, die wir bekommen können. Jetzt, anstatt diese ganze Liste oder das letzte Element in der Liste zurückzugeben, werde ich diese 2D-Matrix zurückgeben. Nun, wenn Sie zurückgehen und aktualisieren, und wie Sie sehen können, haben wir unsere Funktion, unsere 2D-Matrix, und wie wir sehen können, ist es genau dasselbe, es sei denn, wir haben sie gerade von Hand gebaut. Also das ist es im Grunde für dieses Problem, der letzte Wert ist eigentlich das, woran wir interessiert sind. Dies ist also die Implementierung dieser längsten gemeinsamen Folgefunktion mit Python. So sehen wir uns im nächsten Video. 37. Längere Subsequenz: Hallo und willkommen zurück. In diesem Video werden wir das Problem der am längsten zunehmenden Subsequenz diskutieren. Die Idee dieses Problems ist also, dass wir eine Liste von Ganzzahlen erhalten und wir werden die Länge der am längsten zunehmenden Teilsequenz zurückgeben. Wenn wir zum Beispiel diese Liste hier haben, haben wir 15, 7283, dann werden wir die Nummer fünf zurückgeben, die die längste zunehmende Teilsequenz in diesem Fall angibt, das ist O157 als acht und 10. Dies ist also die längste gemeinsame Nachfolge und wir werden die Länge davon zurückgeben. Nun, das erste Mal, das ich bei der Lösung dieser Art von Problem habe, ist normalerweise Rekursion. Da wir die am längsten zunehmende Teilsequenz finden müssen, denken wir vielleicht über die Idee nach am längsten zunehmende Teilsequenz für jeden Index zu finden. Zum Beispiel, wenn wir hier sind, ist die am längsten zunehmende Teilsequenz für dieses spezifische Element tatsächlich eins. Nun, hier, was wir bekommen werden, sind zwei, weil wir 15 haben. Dann um sieben, dann sind es drei, dann zwei. Ich bin zurück zu zwei. Da wir 12 haben, können wir damit umgehen. Dann wird hier um acht vier sein. Und dann natürlich um drei und es wird 1, 2 und 3 sein, was 3 ist, und um zehn wird es fünf sein. Das ist also im Grunde die Idee über dieses Problem. Nun, was wir tun werden, ist zu überprüfen, wie wir es mit Rekursion implementieren können. Das erste, was wir tun werden, ist, die CI zu bauen, die wir haben werden. Denken Sie daran, dass, wenn wir dieses Problem lösen wollen, nehmen wir an, dass wir an der spezifischen Position sind, die bei der Indexnummer 0, 1, 2, 3 und 4 ist . Also sind wir bei Index vier. Wie können wir das für das spezifische Klima lösen? Wie können wir wissen, dass die längste gemeinsame Nachfolge für dieses Element tatsächlich vier ist. Das erste, was wir tun werden, ist, die Bedingung oder die Funktion für den Index für zu erstellen. Und was wir eigentlich tun werden, ist, das Maximum zwischen all diesen vor diesem spezifischen Index zu überprüfen und dann einen hinzuzufügen, wenn er größer als die tatsächlichen Zahlen ist. Also, wie machen wir das? Wir werden eins zum Maximum zwischen F3 und F2, F1 und 0 hinzufügen . Und natürlich sollten sie alle kleiner oder gleich diesem spezifischen Element in einem bestimmten Index sein . Das ist also ein Muss, und natürlich, das ist die Funktion, die wir jetzt tun werden, denken Sie daran, dass dies nur für, äh jetzt, wenn Sie f 0, F1, F2 und F3 berechnen wollen , werden wir genau das gleiche tun. So zum Beispiel haben wir das und dann haben wir hier müssen für F1 und F2 berechnen. Und wie Sie sehen können, bauen wir langsam einen Baum, wo wir nur für dieses spezifische Element von vier finden werden, wir werden all diese berechnen und dann immer wieder berechnen. Und natürlich werden wir genau das Gleiche für all diese Indizes hier in unserer Liste tun . Wie Sie sehen können, wird dies einen exponentiellen Ansatz erfordern und die Laufzeit wird exponentiell sein. Also lassen Sie mich Ihnen einfach den Pseudocode zeigen. Jim. Und natürlich werden wir versuchen, es mit dynamischer Programmierung zu optimieren. Das erste, was wir in diesem rekursiven Ansatz tun werden, ist, die Funktion zu bauen. Also werde ich es einfach am längsten ansteigende nennen und es wird die folgenden Parameter nehmen. Ich werde das Array oder die Lektion haben. Ich werde es die Liste nennen. Und ich werde die ganze Zahl haben und die Länge dieser Liste angeben. Was wir jetzt nicht tun wollen, ist, den Basisfall zu überprüfen. nun daran, dass wir die maximale Länge zurückgeben sollten. Vielleicht kann ich eine globale Variable außerhalb erstellen. Vielleicht nenne ich es Max length. Und in diesem Fall werde ich es in unserem Code direkt hier aktualisieren. Was wir also tun werden, ist zu überprüfen, ob Sie am Basisfall sind , der n gleich 0 oder 1 in diesem Fall ist, was wir annehmen werden, ist, dass wir mit einem beginnen werden. Wir müssen also nicht wirklich 500 berechnen. Wir beginnen mit F1, F2 und so weiter. Ein Fan gleich 1 ist also gleich einem, den wir tun werden, ist einfach einen zurückzugeben, da es das erste Element in der Liste ist und wir seine Länge zurückgeben sollten, die im Grunde gleich eins ist. Und wenn dies nicht der Fall ist, denken Sie daran, dass wir alle diese vier berechnen sollten. Spezifischer Index. Wenn wir also bei U4 sind, müssen wir F3, F2 und F1 berechnen. Also in diesem Fall brauchen wir eine for-Schleife, um das zu tun. Und für jeden von ihnen werden wir den Rückgabewert überprüfen. Und wenn es größer ist als das Maximum, das wir bereits haben, sollten wir unser Maximum aktualisieren. Also, wie machen wir das? Wir werden einfach zwei Variablen definieren. Unser Ergebnis, das wir bekommen werden. Und natürlich das Maximum, das das aktuelle Maximum ist. Also werde ich es nur Current Max nennen. Und jetzt, was wir tun werden, ist, das zu berechnen. Also, wie machen wir das? Wir werden diese Funktion für diese spezifischen Indizes aufrufen. Also für, wir werden mit dem Auge den ganzen Weg von eins bis zum Wert von n. und natürlich können wir es erhöhen, während wir durch gehen. Dann, was Sie tun werden, ist, die Ergebnisse von dieser Funktion zu erhalten. Also werden wir im Ergebnis die Funktion der Erhöhung mit unserer Liste und den Indizes speichern . Nun, es tut mir leid, der Index ist eigentlich, was wir tun werden, ist zu überprüfen, ob diese Liste auf dem spezifischen Index I minus 1 und n minus eins. Wenn dies weniger als n minus eins ist, sollten wir es aktualisieren. Also, wie machen wir das? Lass mich das einfach schnappen und es kleiner machen. Und schauen wir es uns so an. Lebensmittel sind an dieser spezifischen Position, an der wir dieses Geld berechnen müssen. Was wir im Grunde tun werden, ist, alle diese F1, F2 und F3 durchzugehen. Und wir werden überprüfen, ob die spezifische Position ist das Element in dieser Liste ist kleiner als das Element von leisten. Also zum Beispiel, wenn wir an dieser F1 sind und lassen Sie mich davon ausgehen, dass dies eine vierte ist. Das ist also der Index 4, 1234. Und was wir eigentlich tun werden, ist zu überprüfen ob diese spezifische Position kleiner ist als diese. Das ist es. Dann, was wir tun werden, ist, die maximale Länge in diesem Fall zu überprüfen, welche ist es? Weniger als die maximale Länge an dieser bestimmten Position, was in diesem Fall im Grunde 0 ist. Und wenn das also größer ist als dieses, wenn es so ist, dann können wir das um eins erhöhen und es genau hier setzen, was im Grunde zwei ist. Wir werden genau das Gleiche tun, wenn wir das hier berechnen. Die Länge hier ist also zwei. Ist es größer als oder gleich 2? Ja, das ist es. Dann nehmen wir einfach zwei plus eins und inkrementiert, wenn dies der Fall ist. Nun, wie Sie sehen können, ist fünf weniger als, tut mir leid, es ist größer als zwei, dann können wir das tun. Wir haben also zwei Schritte oder zwei Bedingungen zu erfüllen damit wir dieses aktuelle Maximum aktualisieren können. Also lass mich sie einfach aufschreiben. Das erste, was wir überprüfen werden, ob die Liste an der bestimmten Position, was ich minus eins ist, weil wir bei einem beginnen und diese Indizes beginnen mit 012, 34, und so weiter. Also, wenn diese Liste I minus 1 kleiner ist als die spezifische Liste am Ende, mit der wir es zu tun haben. Also n minus eins, wenn dies der Fall ist und unser Ergebnis plus eins. Also müssen wir uns daran erinnern, dass, wenn Sie an der bestimmten Position sind, wir nur die Ergebnisse vom Ende um eins erhöhen und dann überprüfen. Also, wenn dieses Ergebnis größer ist als das aktuelle Maximum, das wir haben, aktuelle Max, dann was wir tun werden, ist, einfach das aktuelle Maximum zu aktualisieren. Das aktuelle Max wäre also, in diesem Fall sollte ihr Ergebnis gleich dem Ergebnis plus 1 sein. Das ist also das im Grunde, wie wir unser aktuelles Maximum aktualisieren können. Nun, nach dem Abschluss von dieser ganzen for-Schleife, die davon ist. Okay, also lass es mich einfach zeichnen. Was wir tun werden, ist einfach zu überprüfen, ob das aktuelle Max, das wir gerade in diesem Fall bekommen haben, größer ist als die maximale Länge des gesamten Arrays oder der P-Gesamtliste. Wenn dies der Fall ist, müssen wir diese maximale Länge aktualisieren. Also F insgesamt, es tut mir leid, wenn der aktuelle max größer ist, dann die maxlength. Wir müssen den Schieberegler aktualisieren. Daher sollte die maximale Länge gleich dem aktuellen Maximum sein. Das ist also im Grunde, das ist unser ganzer Code und Code. Nun, nach Abschluss all dieser, was wir zurückgeben sollten, ist diese Funktion tatsächlich nicht die maxlength, ist das aktuelle max. Und der Grund, warum ist das? Weil ich einfach all diese nehmen und sie ein bisschen kleiner machen kann. Es tut mir Leid. Also lass es mich einfach von hier aus tun. Ich werde Schleife nehmen und es einfach minimieren und es hier wie zuvor platzieren. Und es gibt nicht, dass wir dieses aktuelle Max zurückgeben werden, weil unsere Funktion über dieses aktuelle Spiel ist. Also denken Sie daran, wenn wir in dieser vier Schleife sind, was wir tun werden , ist dieses aktuelle Max von jedem einzelnen dieser Elemente zu nehmen , also sollten wir das aktuelle Max zurückgeben. Wenn wir jedoch diese Funktion aufrufen müssen , wird im Grunde nicht daran interessiert, diese Art von Mathematik. Wir sind an der aktualisierten Version der maxlength interessiert, mit der wir uns beschäftigen. Also, um zu sagen, dass im Grunde für diesen Pseudocode, und wie Sie sehen können, dies auf exponentielle Weise läuft, während wir diese Lunge berechnen. Vielen Dank jedes Mal, wenn wir diese for-Schleife beendet haben und wir nennen es so oft, weil es eine rekursive ist. Also, das ist im Grunde für dieses Video. Im nächsten Video werden wir versuchen, es mit dynamischer Programmierung zu optimieren. So sehen wir uns dann. 38. Längste Subsequenz Pseudo-Code: Okay, Also in diesem Video werden wir versuchen, unsere rekursive Funktion zu optimieren und dynamische Programmierung zu verwenden. Also die Sache ist, wenn wir Rekursion verwenden, rufen wir diese Funktion immer und immer wieder auf. Zum Beispiel, wenn wir an dieser spezifischen Position von jemals für das, was wir im Grunde tun, ist F1, F2 und F3 zu codieren. Und in diesem Fall ein F2, wir werden F1 und F3 anrufen wir F1 und F2 wieder anrufen. Anstatt all das zu tun, ist das, was wir tun werden, einfach eine for-Schleife zu erstellen , die alle diese zusammen durchläuft. So F1 und F2 und F3 und überprüft das Maximum zwischen ihnen. Und danach werden wir es zurückgeben oder es einfach in diese F4 legen. Und natürlich werden wir es um eins erhöhen. Anstatt diesen Pseudocode zu verwenden, wo ich tun werde , ist es einfach los zu werden und neu zu beginnen. Also, was wir anfangen werden, ist tatsächlich die Funktion zu bauen , wo wir die Liste und den Index haben werden. Und so werde ich es nur am längsten steigenden SQL-Server nennen. Es wird eine Liste und die ganze Zahl nehmen. Und jetzt werden wir eine Liste erstellen, in der wir am längsten zunehmende Teilsequenz bis zum Punkt dieser Indizes speichern werden. Zum Beispiel, wenn Sie sich an dieser bestimmten Position befinden, die Index eins ist, aber wir werden in der anderen Liste speichern, die wir erstellen werden , ist die am längsten zunehmende Untersequenz zu diesem Fall , der eigentlich zwei . In Ordnung, lass mich das hier machen. Dies ist unsere zweite Liste, also werde ich sie L I, S nennen , was anzeigt, dass dies die am längsten zunehmende Teilsequenz ist. Und es wird von Größe sein. Und in diesem Fall, wie üblich, jetzt zu tun, ist, unsere Indizes I und unseren Maximalwert zu initialisieren. Also haben wir I, J und Max. Und alle diese sollten auf 0 initialisiert werden, also Maximum auf 0 zu sein. Nun, was wir tun werden, ist, mit unserer for-Schleife, Salem, der LINCS mit einem zu beginnen . Da wir in jedem Index zum Beispiel haben, wenn wir bei Index zwei sind, ist die minimale Zahl hier eins. Die Länge der minimalen möglichen Nachfolge ist also tatsächlich eins, und sie enthält nur diese Zahl selbst. Wenn Sie also zum Beispiel an dieser bestimmten Position fünf sind, ist die Mindestlänge, die wir haben könnten, tatsächlich eins, was bei diesen fünf genau hier ist. Also, um das zu tun, werde ich mir den Blick von den ganzen Weg bis n leisten und einfach speichern und LINCS an der spezifischen Position I, den Wert von eins. Dann, was wir tatsächlich tun werden, ist, zu einem Asset for Schleifen zu erstellen, durch alle diese Elemente oder alle diese Elemente in dieser Liste zu übergeben. Und dann bei jedem Element. Nehmen wir an, wir sind an dieser spezifischen Position, das ist die spezifische Position 3. Aber wir werden tun, ist, durch 012 zu gehen, das Maximum zwischen diesen zu bekommen. Und solange der Wert innerhalb dieser Positionen kleiner als der Wert bei zwei und das Maximum hier größer ist als dieser, können wir ihn aktualisieren. Also, was wir tun werden, ist, lassen Sie mich es einfach hier schreiben, aber davor, lassen Sie mich das minimieren und dann weitermachen. Also, was wir sagen werden, ist, dass wir eine for-Schleife von I bis n haben werden und dann innerhalb dieser for-Schleife werden wir von 0 bis I beginnen Natürlich sollte ich bei 0 beginnen. Dann, was wir tun werden, ist zu überprüfen, wie wir gesagt haben, wenn die Liste an dieser bestimmten Position, die ich größer ist als die Liste an , es tut mir leid, hier haben wir j von 0 bis ISO, j gleich 0 der Weg bis i wenn die Liste an dieser bestimmten Position, die ich größer ist als die Liste an, es tut mir leid, hier haben wir j von 0 bis ISO,j gleich 0 der Weg bis i habe ich gleich 0 den ganzen Weg bis n und ist weniger bei I ist größer als die Liste. Also, wenn wir zum Beispiel hier sind und wir eine gleich 3 haben, die annehmen, was wir tun werden, ist, durch all diese Elemente von 0 bis zu schauen. Und was wir tun werden, ist zu überprüfen, ob diese Gegenstände kleiner sind als der Artikel, den wir haben. Dann, wenn das der Fall ist, was wir tun werden. Also werden wir es mit der am längsten zunehmenden Subsequenz beenden. Nehmen wir an, wir sind an dieser spezifischen Position, wo wir eine haben. Wir nehmen einen und fügen ihm einen hinzu. Das wird also zwei machen. Und denken Sie daran, dass wir alle diese zu einem initialisiert haben. Also, wenn Sie die spezifische Position sind, die bei Index drei ist, und wir werden eine AD als die am längsten zunehmende Teilsequenz haben. Moment nehmen wir 1 plus 1, das gleich zwei ist. Wir werden prüfen, ob zwei größer als eins sind. Wenn dies der Fall ist, müssen wir dies aktualisieren. Um das zu tun, werden wir an einer bestimmten Position überprüfen, die j plus 1 größer ist als die LINCS an der Position von I. Wenn dies der Fall ist, dann müssen wir unser LAS bei atoi aktualisieren. Also werde ich bei IST, ich sollte gleich S bei j eins sein. Also, das ist es im Grunde, jetzt werden wir eine Liste von diesen hier haben. Also werden wir 1, 2, 3, 2, 4, 3 und 5. Und natürlich, um das Maximum zu erhalten, werden wir eine weitere for-Schleife erstellen, die uns hilft, das Maximum aus dieser Elias-Liste zu bekommen. Also, um das zu tun, lass mich das hier machen. Und was wir jetzt tun werden, ist eine andere for-Schleife zu erstellen, die ich gleich 0 bis zum Ende durchläuft. Und wir werden eine maximale unverzerrte und die maximale Variable genau hier finden. Also, wenn Elias bei I größer als Maximum ist, werden wir diesen Wert von Elias bei I speichern und maximieren. Also das ist es im Grunde jetzt, was wir zurückgeben werden, ist einfach das Maximum zurückzugeben, das wir gerade berechnet haben, was ist eigentlich die Länge der am längsten zunehmenden Untersequenz, die wir schreiben. Also geben wir einfach max zurück, und jetzt sind wir gut. Das ist also unsere Funktion. Nun, wenn wir es nennen wollen, können wir es einfach mit dem Array oder dem weniger, das wir haben, und es ist Index oder die Größe davon. Also, das ist es im Grunde jetzt, über die Zeitkomplexität nachzudenken. Hier verwenden wir zwei verschachtelte for-Schleifen, beginnend von 0 bis n. und wir haben auch von I gleich j gleich 0 bis i, was im schlimmsten Fall ist, werden wir n haben, Also wir haben m Quadrat genau hier. Und was wir tatsächlich im Hilfsraum gemacht haben , ist, dass wir sie in einem Array oder einer Liste verkauft haben, und es wird einen Raum von n. Also die Zeitkomplexität ist O n Quadrat und die Raumkomplexität ist O von n. und es wird einen Raum von n. Also die Zeitkomplexität ist O n Quadrat und die Raumkomplexität ist O von n. im Grunde für dieses Problem. Im nächsten Video werden wir es mit unseren Sprachen implementieren. 39. Längere Subsequence Java-Implementierung: Oh, hey, also in diesem Video werden wir unsere Funktion mit Java implementieren. Also das erste, was ich tun werde, ist, die Funktion zu erstellen, die wir verwenden können. Also ist es öffentlich statisch, und ich werde es am längsten nennen, zunehmender. Und es wird das Grau nehmen. Und jetzt, was wir tun werden, ist die am längsten zunehmende Subsequenz zu erstellen, die auch ein Array der Größe n sein wird, wie wir sagten. Dann werden wir unsere Indizes initialisieren. Und natürlich werden wir das Maximum initialisieren, das wir verwenden werden. Danach. Das erste, was wir tun werden, wie wir gesagt haben, ist, in der Liste die am längsten zunehmende Subsequenz mit Einsen zu füllen. Also werden wir mit I gleich 0 beginnen. Ich ist kleiner oder gleich n, und wir werden es inkrementieren. Dann werden wir die amlängsten zunehmende Teilsequenz an der spezifischen Position I, den Wert von eins,ausfüllen längsten zunehmende Teilsequenz an der spezifischen Position I, den Wert von eins, . Danach werden wir mit unserer for-Schleife fortfahren. Also haben wir zwei verschachtelte für Schleifen, die ich weniger als n und ich plus plus. Dann werden wir mit j gleich 0, j kleiner als i fortfahren und j implementieren. Wie wir in unserem Pseudocode gesagt haben, werden wir überprüfen, ob diese Werte Liste oder das Array bei I größer ist als das Array bei j. Und wir werden überprüfen, ob die am längsten zunehmende Subsequenz bei j plus eins größer ist als die am längsten zunehmende Subsequenz an mir. Das ist der Fall. Wir müssen die am längsten zunehmende Teilsequenz an einer bestimmten Position aktualisieren. Wenn also Array bei I größer ist als das Array bei j, und wie gesagt, die am längsten zunehmende Subsequenz bei j plus eins ist größer als die am längsten zunehmende Subsequenz bei mir ist, ist dies der Fall, dann müssen wir es. Also am längsten zunehmende Subsequenz, sollte ich gleich der bei j plus eins sein. Also im Grunde, so können wir unser Array konstruieren. Nun, nach dem Druck von diesen beiden verschachtelten for-Schleifen, müssen wir das Maximum finden und es und den maximalen Wert speichern. Also werden wir durch I gleich 0 kleiner als n schauen und dann I erhöhen. Dann werden wir überprüfen, ob das Maximum kleiner ist als die längste zunehmende Teilsequenz an der spezifischen Position, die dies der Fall ist, dann sollten wir aktualisieren das Maximum, um den Wert zu sein, den wir hier haben. Nun danach, aber wir werden tun, ist, einfach das Maximum zurückzugeben, das wir haben. Probieren wir es jetzt aus. Was ich tun werde, ist eine Hauptfunktion zu erstellen , wo ich das Array erstellen werde, das wir wollen. Jetzt. Also die Belüftung ist, lassen Sie mich das gleiche exakte Beispiel verwenden. Wir haben 15 728310, also 157283. Und dann haben wir die Länge n, die im Grunde die Länge ist, die Länge dieses Arrays, 1, 2 , 3, 4, 5, 6, 7. Also n gleich sieben. Jetzt und ich werde tun, ist das Ergebnis in einer Ganzzahl namens Ergebnis zu speichern. Und ich werde diese Funktion nennen, die die am längsten zunehmende Sequenz ist. Und natürlich werde ich das Ergebnis ausdrucken, wie hier, Alpha, gehen Sie vor und führen Sie diesen Code aus. Ich werde fünf als die am längsten zunehmende Subsequenz bekommen. Und wenn wir hier zurück gehen, können Sie feststellen, dass unser weniger aus fünf Elementen besteht , die darauf hinweisen, dass die Länge dieser Liste tatsächlich fünf ist. Also, das ist es im Grunde jetzt 400 gehen weiter hinein und visualisieren dies. Ich liste die am längsten wachsende Teilsequenz auf, die aus 1232435 besteht. Was ich einfach tun werde, ist eine Liste oder ein Array anstelle dieses zurückzugeben. Und ich werde hier einfach die am längsten zunehmende Subsequenz zurückkehren. Dann werde ich es in einem Ergebnis wie diesem speichern. Und ich werde eine for-Schleife erstellen. Und natürlich werde ich es als dieses etwas Raum ausdrucken. Und wenn wir fortfahren und diesen Code erneut ausführen, werden wir 1232435 bekommen. Jetzt. Wir müssen einfach da sein. Also haben wir 1232435 und wie wir sehen können, haben wir 1232435. Die Ergebnisse entsprechen also unseren Erwartungen. Und das ist die Dokumentation der am längsten zunehmenden Subsequenz mit Java. 40. Längere Subsequence: Wie k. so in diesem Video werden wir unsere Funktion mit JavaScript implementieren. Also das erste, was ich tun werde, ist, unsere Funktion zu erstellen und ich werde sie nennen. Ich werde eine Liste und die ganze Zahl bekommen und die Größe dieser Liste angeben. Nun, was wir tun werden, ist eine weitere Liste zu erstellen , die die am längsten zunehmende Subsequenz ist. Ich werde es als Verbündeter nennen. Und ein Array von und das ist die Größe. Und ich wollte es mit einem 1s füllen. Also, das ist es im Grunde. Nun lassen Sie uns die Indizes I und j initialisieren und dann werden wir ein Maximum initialisieren, das wir verwenden werden, das gleich 0 sein wird. Dann werden wir von I zu 0 beginnen. Es tut mir leid, von mir gleich eins bis ich gleich und, und gerade implementiert. Dann werden wir J nehmen, was gleich 0 ist. Also j von 0 bis I, und natürlich werden wir es inkrementieren. Jetzt werden wir tun, ist das Gleiche wie der Pseudocode. Wir werden überprüfen, ob die Liste bei i größer ist als der kleiner als j. Also, wenn Liste bei i größer als a, kleiner als j, und wir müssen überprüfen, ob der Elias bei j plus eins größer ist als DALYS bei i. Wenn dies der Fall ist, wir müssen diese Allianz bei I aktualisieren, um Ls bei j plus 1 gleich zu sein. Danach können wir das Maximum zurückgeben. Nun, was wir tun werden, ist, nach dem Maximum in der Liste zu suchen. Also werden wir von 0 den ganzen Weg bis und beginnen, und aktualisiert. Dann werden wir überprüfen, ob Max kleiner ist als die Elias an der spezifischen Position, in der wir es aktualisieren werden. Also sollte Max Elias bei I. und natürlich sollten wir danach einfach das Maximum zurückgeben. Das war's also. Das ist es. Dies ist die Funktion, die wir jetzt verwenden werden, ich werde tun, ist unsere Liste zu erstellen, also um sie auszuführen, also lasst uns einfach gleich der gleichen genauen Liste, die wir verwenden. Wir haben 15, 7283 und 10. So 157283 und 10. Dann haben wir n, die gleich 7 ist, im Grunde. Danach werde ich das Ergebnis in einer Variablen namens Ergebnis speichern. Und zwei werden die längsten sein, steigen als weniger als 10. Danach werde ich es ausloggen. Also werde ich die Ergebnisse danach ausloggen. Was ich tun werde, ist, zu meinem Verzeichnis zu gehen, das die dynamische JavaScript-Programmierung ist. Und dann werde ich diesen Code mit Node Java-Skript ausführen. Tut mir Leid, Node. Und der Name der Datei am längsten zunehmenden Subsequenz dot js. Und so haben wir hier einen Fehler. Also mal sehen, innerhalb des Moduls nicht gefunden. Also glaube ich, ich habe es falsch geschrieben. Die am längsten ansteigende Teilsequenz. So ist es zunehmende Subsequenzknoten lernen zunehmende Subsequenz, die keine forensische hat , und wir werden fünf als die längste zunehmende Subsequenz, die wir haben. Und wenn Sie tatsächlich diese Liste der am längsten wachsenden Teilsequenz visualisieren möchten, die 1, 2, 3, 2, 4, 3 und 5. Wir können hier einfach den Elias anstelle des Maximums zurückgeben. Und jetzt, wenn ich vorangehe und zurückgehe, lese es noch einmal, werde ich 1232435 als das Ergebnis bekommen, das wir erwartet haben, und als Ergebnis, dass wir tatsächlich bis zum Ende hier generiert. Also, das ist es im Grunde für dieses Problem ist, dass für die längste zunehmende Subsequenz mit JavaScript. 41. Längere Subsequence Subsequence: Okay, das ist also Python Implementierung des am längsten wachsenden Subsequenzproblems. Also das erste, was ich tun werde, ist, die Funktion zu definieren. Ich werde den längsten Anstieg nennen. Und es wird das Array oder die Liste nehmen, die wir eine einfach benannte Liste haben werden. Dann werden wir den Index n oder die Größe dieser Liste haben. Was wir eigentlich tun werden, ist zu speichern und eine neue Liste. Ich werde uns Verbündeten aussenden. Wir werden einmal lagern, und sie werden es nicht sein. Und einmal. Danach können wir mit dem Bereich oder den beiden for-Schleifen beginnen. Also für ich im Bereich von 1 n, Wir gehen von j im Bereich von 0 bis i zu gehen und wir werden überprüfen, wie wir bereits gesagt haben, innerhalb von Pseudocode, können wir überprüfen, ob die Liste bei i größer ist als aufgeführt j Also lassen Sie mich es schreiben ganz schnell runter. Also weniger bei mir ist größer als die Liste L, j. Und wir haben auch, sorry, und wir werden die LINCS haben. J plus 1 ist größer als der LAS I Hut. J plus 1 ist tatsächlich größer als die Elias bei i f. Dies ist der Fall. Dann, was wir tun werden, ist, die ALS bei L2 zu aktualisieren. Ich füge j plus 1 hinzu. Danach können wir das Maximum definieren, das wir verwenden werden. Das Maximum sollte also auf den ersten 0 liegen. Dann werden wir durch die gesamte Elias-Liste suchen, die die am längsten zunehmende Teilsequenz für jeden hat. Und das ist, und in diesem Fall für ich im Bereich von 0 den ganzen Weg. Und so werde ich einfach schreiben, und wenn das Maximum gleich ist, letzteres größer als die tatsächliche maximale Variable, die wir hier haben, dann müssen wir diese hier aktualisieren. Also, wie machen wir das? Wir können einfach schreiben, das Maximum ist kleiner als die LSAT. Ich werde das Maximum aktualisieren, um an einer bestimmten Position i zu sein. Danach werden wir einfach als das Maximum zurückkehren, das wir jetzt erstellt haben. Nun, um es zu überprüfen, was ich tun werde, ist eine Liste zu erstellen, die genau das ist, was wir, hey, also haben wir 15728310. Also werden wir in dieser Liste 15, 7283 und 10 haben. Dann werden wir n haben, was gleich 7 ist. Danach werde ich ein Ergebnis speichern, die am längsten zunehmende Subsequenz mit weniger und n. Und natürlich werde ich das Ergebnis ausdrucken. Jetzt sieh es dir an. Was ich tun werde, ist, einfach zum CMD-Desktop und zum Python dynamischen Programmierverzeichnis zu gehen . Und ich werde diesen Code ausführen. Also am längsten zunehmende Subsequenz Punkt py. Also hier haben wir einen Fehler, weil wir ein variables Ergebnis erstellt haben und wir es nicht in Python verwenden können. Also jetzt, wenn wir zurückgehen und aktualisieren, wie Sie hier sehen können, werden wir fünf als die am längsten zunehmende Subsequenz innerhalb dieser Untersequenz von Ganzzahlen erhalten . Nun, wenn wir die ganze Liste sehen wollen, das ist, was, die 1, 2, 3, 2, 4, 3 und 5. Wir können einfach das Maximum zurückgeben, nur den Verbündeten wie, wie es ist. Wenn Sie nun zurückgehen und es erneut ausführen, werden wir diese Liste 1, 2, 3, 2, 4, 3 und 5. Dies sind also die am längsten zunehmende Teilsequenz für jeden einzelnen Index in unserer Eingabeliste. Also hatte ich nicht 0 bei den längsten Zutaten. Schräger Muskel ist eins, Index , eins, es ist 23. Und hier haben wir zwei, weil wir, an der spezifischen Position, die wir sind, müssen wir, die am längsten zunehmende Teilsequenz ist 12 und ihre Länge ist eigentlich 2. Das ist es im Grunde jetzt, was wir am Ende tatsächlich getan haben , ist, das Maximum von diesen zu berechnen, das ist fünf, und es als unser Ergebnis zurückzugeben. Also, das ist es im Grunde für dieses Problem. Dies ist die Implementierung der am längsten zunehmenden Subsequenz mit Python. 42. PROJEKT: Okay, Also im letzten Problem haben wir die Länge der am längsten zunehmenden Subsequenz mit einer Zeitkomplexität von O n Quadrat gelöst , wie Sie hier sehen können. Also, was wir tatsächlich getan haben, ist, die Länge der längsten Nachfolge in einer Liste von ganzen Zahlen wie dieser zu finden , und es ist die längste ist 15, 7, 8, 10, und seine Länge ist tatsächlich 5. Nun, was Sie tun sollten, ist, die Lösungsstunde zu verbessern, um einen verbesserten Weg in Bezug auf die zeitliche Komplexität zu finden. Unsere Zeitkomplexität ist also O n quadriert. Ihre Aufgabe ist es, es in o und Login zu verbessern. Was Sie tun müssen, ist über eine Methode nachzudenken und mit Ihrer bevorzugten Programmiersprache implementiert und die Lösung in Bezug auf die Zeitkomplexität zu verbessern. nun daran, wenn Sie mit einem solchen Problem umgehen, können Sie die Platzkomplexität opfern, um eine bessere Zeitkomplexität zu haben. Zum Beispiel, wenn wir kein Array verwenden oder wenn wir eine Liste verwenden, können wir mehr verwenden. Sie können 2D-Matrix, eine HashMap oder irgendetwas dieser Art verwenden, um Ihre Zeitkomplexität zu verbessern. Also konzentrieren wir uns nur auf die Zeitkomplexität und ignorieren den Raum für den Moment. Das war's also. Das ist deine Aufgabe. Ich hoffe, es gefällt dir. Score, und vergessen Sie nicht, Ihr Projekt im Projektbereich zu löschen. Und viel Glück und genießen. 43. Schlussbemerkung: Also herzlichen Glückwunsch, Sie haben gerade diesen Kurs beendet. Dies ist nur eine kurze Zusammenfassung darüber, was wir darin behandelt haben. Also das erste, was wir getan haben, ist Fibonacci-Sequenz zu verwenden, um Auswendiglernen und Tabulationen zu definieren und die Unterschiede zwischen ihnen zu lernen. Dann lösen wir einige der berühmtesten dynamischen Programmieralgorithmen. Und zuerst zeichnen wir die Bäume, ihre IRAs oder 2D-Matrix neben dem Pseudocode, den wir verwenden werden. Danach haben wir sie mit unseren Sprachen implementiert. Also, jetzt, nur kurze Tipps. Wann immer Sie diese Art von dynamischen Programmierproblemen verkauft haben, müssen Sie es durch einen 100 Durst lösen, der versucht wurde, die Lösung zu finden, die funktioniert, vielleicht durch Rekursion. Und natürlich können Sie danach mit der Optimierung beginnen und eine bessere Lösung finden, indem Sie entweder Memoisierung und Tabulation verwenden. Damit das gesagt wird, ist dies das Ende unseres Kurses. Ich hoffe, es hat dir gefallen. Schließlich, wenn Sie Fragen oder Anregungen oder Verbesserungen haben, dann kann ich den Diskurs halten. Oder wenn Sie möchten, dass ich zusätzliche Probleme beziehe, fragen Sie es bitte im Bereich Fragen und Antworten. Und es wäre toll, eine Rezension zu hinterlassen, damit ich diesen Kurs verbessern kann. Also danke, dass du hier bist und viel Glück auf deiner nächsten Reise.