Programmation dynamique : Java, Javascript et Python

1. Introduction: Bonjour à tous et bienvenue à ce nouveau cours sur la programmation dynamique. m'appelle 100 unités et je serai votre instructeur tout au long de ce cours. Donc, tout d'abord, permettez-moi de commencer par vous montrer le schéma avec le schéma de ce cours. Nous allons commencer par définir la programmation dynamique. Et nous allons en apprendre davantage sur deux des techniques les plus populaires qui sont généralement utilisées dans ce sujet. Le premier est la mémorisation, et le second est la tabulation. Et nous allons en apprendre davantage sur eux en utilisant la séquence Fibonacci. Nous allons résoudre ce problème en utilisant trois méthodes. Le premier utilise la récursivité générative que nous connaissons tous. Et nous allons passer à la mémorisation et à la tabulation. Et nous allons voir les différences entre eux. Et nous allons apprendre quand et où utiliser chacun d'eux. Après cela, ce que nous allons faire est de résoudre certains des exercices les plus célèbres en utilisant la programmation dynamique. Donc la première chose que nous allons faire est d'essayer de construire un arbre ou peut-être une sorte de tableau ou une matrice 2D de ce problème. Après cela, nous allons essayer d'écrire un pseudocode qui nous aidera à implémenter ce problème. Et enfin, nous allons réellement implémenter en utilisant trois langages, Java, JavaScript et Python. Donc, en passant par les sections, vous remarquerez peut-être que nous allons résoudre un problème principal dans chaque section. Et le problème contient l'explication du problème à côté du code ou de l'exemple de travail à travers. Ensuite, nous allons avoir un pseudocode qui explique notre logique et nos formules. Et après cela, nous allons l'implémenter en utilisant les trois langues mentionnées précédemment. Nous avons également une fonctionnalité supplémentaire qui est ce site Web. J' ai créé ce site Web afin que vous puissiez exécuter votre code et testé. Donc ici, nous avons quelques problèmes que nous allons résoudre. Et vous pouvez aller de l'avant et choisir l'un des problèmes. Essayez de le résoudre ici avant de revenir à l'explication vidéo et la mise en œuvre que nous avons et le discours. Donc, cela dit fondamentalement, c'est le schéma ou le schéma de notre cours. J' espère que vous apprécierez et vous verrez dans la section suivante. 2. Exigences: OK, donc avant de commencer, il y a une liste d'exigences que vous devez télécharger en fonction de la langue que vous allez utiliser. Donc, par exemple, si vous utilisez Java, mais que vous devez télécharger est Eclipse ou une sorte d'IDE où vous pouvez exécuter Java. Alors bien sûr, vous devrez télécharger Java. Vous allez vous diriger vers Java SDK et ils ont juste un peu appuyer et d'accord et un tel téléchargement gratuit. Et vous obtiendrez votre nouvelle version. Si vous utilisez Python, par exemple, vous devez télécharger Python. Et bien sûr, je vais télécharger Visual Studio Code où nous allons exécuter notre code avec Python et JavaScript. Enfin, pour JavaScript, nous allons utiliser Node.JS pour l'exécuter sur notre serveur. Donc, ce sont les exigences dont vous avez besoin. Je vais ajouter les liens dans la section description. Et j'espère que vous avez apprécié ce cours. Alors, on se voit dans la section suivante. 3. Séquence Fibonacci: Bon, alors bonjour et bienvenue. Et ces deux vidéos, nous allons répondre à la question de savoir ce qu'est la programmation dynamique ? Alors commençons par quelque chose de simple. C' est la séquence de Fibonacci. Et la séquence de Fibonacci est en fait une séquence où chaque nombre est la somme de ses deux nombres précédents. Donc, nos cas de base sont en fait les deux premiers chiffres, c'est-à-dire 01. Ce sont donc les deux premiers nombres de la séquence de Fibonacci. Et le reste d'entre eux sont en fait la somme des chiffres précédents. Par exemple, si un je reçois ce nombre, il est 0 plus un est un. Ensuite, nous avons 1 plus 1, 2, 1, 2, 3, 2 plus 35, suite et ainsi de suite. Donc c'est la séquence de Fibonacci. Maintenant, chaque fois que nous voulons le résoudre, notre première pensée va dans la récursion. Puisque chaque fois que nous voulons calculer le nombre à une position spécifique, nous devons revenir aux nombres précédents. Laisse-moi juste écrire les indices ici. C' est donc l'indice 0, 1, 2 , 3, 4, 5, 6 et 7. Maintenant, laissez-moi juste dessiner un arbre où nous allons représenter ces chiffres. Donc supposons que je veux calculer le Fibonacci de cinq. Donc, pour calculer le Fibonacci de cinq, je dois calculer le Fibonacci de quatre, puis le Fibonacci de trois, puis les additionner ensemble. Maintenant, afin d'obtenir ce Fibonacci de quatre, ce que je devrais faire est de calculer le Fibonacci de trois, puis le Fibonacci de deux. Et la même chose s'applique ici. Donc, je veux obtenir f de 2 et f de 1. Et ici, nous allons nous rencontrer pour obtenir f de 1 et f de 0. Et rappelez-vous que f de 1 et f de z sont les cas de base. Et chaque fois que nous arrivons à ce point, nous devrions simplement retourner ces deux valeurs que nous avons ici. Donc ici, nous avons f de 1 aussi et f de 0. Et la même chose s'applique ici. Donc je vais juste écrire ces points. Donc c'est tout maintenant, si nous pensons à la complexité temporelle de cet algorithme, cela prendra une forme exponentielle, puisque comme nous pouvons le voir, nous calculons les mêmes nombres encore et encore. Donc ici nous avons f de 2, 2, et ici nous avons f de 1, 1 et 1. Et vous les calculez encore et encore comme nous pouvons le voir. Donc, notre solution peut fonctionner, ou elle fonctionne réellement pour de petits nombres, mais cela prendra beaucoup de temps, peut prendre des secondes, minutes, voire des heures pour calculer une grande séquence Fibonacci. Alors à quel code absolu pourrait ressembler ? Alors laissez-moi juste écrire le Fibonacci et il devrait être égal à ce code. Donc la première chose qu'on va faire est d'écrire nos cas de base. Si n est égal à 0. Donc, si n est à l'index 0, nous devrions juste retourner cette valeur qui est 0. Donc, je vais simplement retourner 0 dans ce cas. Maintenant, si n est égal à 1, ce que nous devrions retourner comme en fait cette valeur à un index spécifique un, qui est en fait un. Donc, je vais simplement en retourner un. Maintenant, nous pouvons commencer par notre cas de base ou je suis désolé, avec notre récursion. Ce que nous devons retourner en fait, ce sont les deux chiffres précédents. Donc, si nous sommes à Banaji de n, qui est égal à cinq, nous devrions faire semblant de Fibonacci de quatre plus Fibonacci de trois. Alors comment on a fait ça ? Nous avons simplement appelé la fonction Fibonacci de n-minus-1. Et puis nous le somme avec le Fibonacci de n moins 2. Alors c'est tout. Fondamentalement, c'est pour notre pseudocode. Maintenant, ce que je vais faire est de prendre l'esprit de Dieu et réellement implémenté en utilisant Java. Gardez à l'esprit que nous allons seulement utiliser Java dans le but de visualiser la complexité temporelle de ce problème et le reste de vos problèmes sera présenté dans tous les langages, Java, JavaScript et Python. Donc, pour faire ça, laisse-moi aller à Eclipse. Et ce que je vais faire est d'écrire ce code ici. Donc f n est égal à 0. Je vais faire est de retourner simplement 0. Maintenant, si n est égal à un, je vais en retourner un. Et si ce ne sont pas les cas, ce que je vais faire est simplement de revenir. Donc, je vais retourner Fibonacci de n moins 1 plus Fibonacci de n moins deux. Maintenant, après ça, je pars, je suis désolé, j'ai oublié ici. Maintenant pour tester cela, ce que je vais faire est de créer une fonction principale et appeler le Fibonacci d'un nombre spécifique imprimé, imprimer le Fibonacci de 7 dans ce cas. Comme vous pouvez le voir, si je vais de l'avant et exécute ce code ici. Mais je vais en fait devenir P numéro 13. Et si vous revenez ici, nous pouvons voir que ce Fibonacci de ce spécifique et X7 est en fait 13. Donc, notre code fonctionne correctement. Cependant, si je retourne maintenant et essayons le Fibonacci 50. Et si nous exécutons ce code mardi, un certain temps à exécuter puisque nous avons des appels récursifs où nous allons exécuter le même code ou exécuter la même fonction encore et encore. Et cela prendra peut-être des secondes ou peut-être des minutes dans ce cas. Nous devons donc avoir un meilleur moyen obtenir ces séquences de Fibonacci ou les résultats dans ce cas. Et voici dans la programmation dynamique. Donc nous avons deux techniques que nous allons présenter. Le premier est appelé mémoisation, et le second est appelé tabulation. Et nous allons les présenter dans les prochaines vidéos. Alors, à vous voir. 4. Memoization: Bon, donc nous avons trouvé la solution où nous utilisons récursivité pour résoudre ce problème de Fibonacci. Cependant, nous rencontrons un problème en raison de sa complexité temporelle. Parce que nous exécutons la même fonction ou appelons la même fonction encore et encore. Alors, comment on fait face à ça ? Voici la programmation dynamique. Donc, la première technique que nous allons utiliser est appelée mémoization, qui est essentiellement juste pour stocker les valeurs que nous allons utiliser encore et encore. Donc, pour ce faire, au lieu de simplement appeler f de 2 ici une fois et ici une autre fois. Mais nous allons en fait à deux pour résoudre ce f de deux la première fois que nous le voyons. Donc notre code va fonctionner de cette façon. On va appeler f de 5, 10. Dans ce cas, il l'appellera f de 4, 4, 3. Cependant, avant d'appeler cela, il ira de cette façon. Donc le flux de notre code est en fait f de 5, 4, 3, et ensuite on va aller jusqu'à 21, et on est bons et ensuite on va revenir jusqu'ici. Et comme vous pouvez le voir juste là. Donc c'est le flux de notre code. Maintenant, ce que nous avons fait pour faire est de stocker toutes ces valeurs à chaque fois ou la première fois que nous allons les voir. Et bien sûr, chaque fois que nous voulons les utiliser à nouveau, nous allons simplement les prendre de notre mémoire. Donc, pour ce faire, ce que je vais réellement ajouter dans ce cas est une liste ici. Alors laissez-moi juste supprimer ceci. Et je vais changer les paramètres ici, de N en N et une mémoire. Et dans ce cas, ce que nous allons faire, c'est de prendre cette mémoire et de l'utiliser plus tard. Donc avant de faire tout ça, nous allons vérifier si le fibonacci de cette séquence, et il est effectivement stocké dans notre mémoire. Alors comment on fait ça ? Permettez-moi de changer la couleur pour que nous puissions visualiser les changements. Donc, si la mémoire à cette position spécifique et n'est pas égale à 0. Maintenant rappelez-vous que chaque fois que nous créons cette mémoire, nous allons juste mettre des zéros et la position d'Annette et de la FDA, qui est à n, n'est pas égale à 0. Ce que nous allons faire en fait, c'est simplement le retourner tel qu'il est. Donc, nous allons retourner la mémoire à cette position spécifique. Et maintenant, si ce n'est pas le cas, nous allons continuer avec notre code comme avant. Cependant, avant de retourner celui-ci ici, ce que nous allons faire est de le stocker dans notre mémoire. Parce que rappelez-vous que Fibonacci n est retourné par cette hanche droite. Donc, pour ce faire, je vais simplement le stocker en mémoire à n, puis retourné. Laisse-moi le faire en prenant tout simplement tout ça et peut-être les pousser à entendre. Et ce que je vais faire maintenant, c'est de prendre ça et de le placer ici. Maintenant, continuons. Donc, au lieu de retourner celui-là, et je vais faire, c'est de les mettre dans notre mémoire et de retourner la mémoire réelle. Laisse-moi juste essayer ici. Nous avons la mémoire à n sera égal à celui-ci. Et bien sûr, après cela, nous allons simplement retourner la mémoire à cette position spécifique. Et c'est tout maintenant, au lieu d'appeler toutes ces fonctions encore et encore, qui va juste vérifier s'ils sont à cette mémoire ? Si c'est le cas, nous allons simplement les retourner. Si ce n'est pas le cas, nous allons les calculer et les stocker dans la mémoire pour la deuxième fois, nous allons les utiliser. Bien sûr, cela fonctionnera correctement. Maintenant, allons de l'avant et utilisons ce pseudocode et notre Java. Donc, au lieu d'avoir n, je vais prendre un souvenir. Et bien sûr, quand nous appelons les nazis ici, nous devrions aussi retourner la mémoire. Cependant, avant de le retourner, ce que nous devrions faire est simplement d'ajouter une queue. Donc la mémoire à n devrait être égale à ds, et bien sûr nous devrions tenir sur la mémoire. Et après ça, Maintenant, appelons-ça des critères. Donc, comme vous pouvez le voir, ce grand nombre a pris un certain temps à obtenir et il est négatif parce que nous utilisions des entiers. Alors peut-être qu'on va utiliser 24 maintenant. Cependant, nous devons l'incrémenter. Donc, nous allons avoir une nouvelle fin de taille 21 à utiliser à l'intérieur du pseudocode. Maintenant, si nous revenons en arrière et exécutons ce code, comme vous pouvez le voir, nous avons obtenu notre résultat qui est 67, 65, ce qui est, nous n'avons pas pris beaucoup de temps comme avant. Laisse-moi vérifier le numéro 30. Et comme nous pouvons le voir, pour non découvert, nous allons obtenir ce grand nombre et ce nombre qui n'aurait pas pu simplement calculer en utilisant la fonction récursive originale parce que nous appelons les mêmes fonctions exactes encore et encore. Donc maintenant, ce que nous allons faire est d'essayer un très grand nombre comme 20000. Dans ce cas, si nous allons de l'avant et l'exécuter, nous pouvons voir que nous avons une erreur. Et cette erreur est en fait StackOverflow. Donc, notre code s'exécutera rapidement. Cependant, chaque fois que nous appelons ces fonctions encore et encore. Donc, si nous sommes à une position précise où nous avons 10 mille, nous allons appeler dix mille neuf cent mille neuf cent quatre-vingt-dix neuf mille neuf cent quatre-vingt-dix huit jusqu'au dernier qui est à 0. Donc, toutes ces fonctions de rappel ou de rappel SysML vont être ou le ou juste stockés dans une pile. Et notre personnel pourrait ne pas prendre tous ces éléments ou les assembler tous ensemble. Donc, ce que nous allons faire est d'utiliser une autre technique qui s'appelle la tabulation. Et c'est aussi une technique de programmation dynamique, et nous allons la voir dans la prochaine vidéo. 5. Tabulation: Ok, donc dans la dernière vidéo, on utilise la mémoisation pour résoudre ce problème de Fibonacci. Cependant, nous rencontrons un problème où nous avons eu une erreur de débordement de pile parce que nous utilisions trop d'instructions de retour , de rappels, et nous stockons tous dans notre pile et cela ne pouvait pas les adapter. Donc maintenant, ce que nous allons faire est d'utiliser la tabulation pour résoudre ce problème de Fibonacci. Maintenant, si nous savons que nous devons obtenir ce f de cinq, et pour obtenir ce f de 5, nous devons obtenir f de quatre, f de 2 et f d'un. Il est donc logique de résoudre tous ces problèmes à l'avance et simplement les stocker dans une sorte de liste de tableaux ou quelque chose comme ça. Et puis il suffit de retourner f de 5. Donc, ce que nous allons faire est de commencer du bas jusqu'au dernier élément. Et cela s'appelle la tabulation, qui est fondamentalement une programmation dynamique ascendante. Et en fait appelé ça parce que nous allons le construire à partir du bas, un par 12, prêchant notre but. Donc, ce que nous allons réellement faire est de commencer à partir de 0, remplir notre fonction, ou à travers notre repos, puis retourner le dernier dont nous avons besoin. Alors laissez-moi juste supprimer tout ce pseudocode et l'écrire à nouveau avec la tabulation. Donc, je vais vraiment faire est de créer une fonction et ce sera une fonction itérative, donc itérée. Et dans ce cas, ce que nous allons faire, c'est d'avoir un numéro et que nous allons revenir. Et dans ce cas, ce que je vais faire est de créer peut-être une liste ou un tableau. Je vais simplement appeler ça une liste. Et il sera de taille et plus un. Et ce que nous allons faire en fait, c'est de remplir cette liste avec ces valeurs ici. Donc, la liste à l'index spécifique 0 doit être égale à 0. Et puis la liste à un index spécifique 1 est égale à un. Et puis nous pouvons commencer par une boucle for commençant à I égal à deux jusqu'à n. Et chaque fois dans cette liste, nous allons stocker cet index spécifique I, la valeur de la liste à i minus1, et le plus à I moins deux. Donc, il faudra un grand O de n. Donc c'est la complexité de l'exécution parce que nous parcourons tous les éléments de 0 à n. Et chaque fois que nous atteignons le dernier élément qui est à un index spécifique, et nous pouvons le retourner. Donc, après avoir terminé de tous ces éléments, nous retournons simplement la liste à la position. Et dans ce cas, donc c'est tout maintenant, au lieu de rappeler chaque fois que nous devons appeler ceci, par exemple, f à 99, 99, nous pouvons simplement le stocker dans notre liste et enfin, obtenir quand nous le voulions. Donc, dans ce cas, laissez-moi juste lire le type de cette fonction ici en utilisant la tabulation. Donc, au lieu d'obtenir tous ces éléments, ce que je vais faire est simplement de créer une fonction et ce sera. Et au lieu de stocker ce paramètre, je vais simplement l'écrire ici. Donc je vais avoir la dame ici de taille n plus un. Et dans ce cas, ce que je vais faire est de stocker à Mammoth 0 la valeur de 0, la mère d'un sera un. Et maintenant, nous pouvons commencer avec la boucle for, à partir de I égal à deux tout le chemin. Et ainsi inclus. Et bien sûr, nous allons l'incrémenter après ça. Ce que je vais faire est de commencer à cette position spécifique à i, la valeur de m à I moins 1, et d'y ajouter la valeur de n moins deux dans ce cas. Comme nous pouvons le voir, si nous allons de l'avant et retournons la valeur de et à la fin, ce que nous allons obtenir en fait comme la valeur correcte de ce 20000 ici. Donc, si je lance ce code, je vais obtenir 93637285. Et c'est la séquence de Fibonacci correcte à un indice spécifique de 20000. Nous nous débarrassons donc des problèmes StackOverflow que nous avions l'habitude d' utiliser la mémoisation et nous avons déjà utilisé la tabulation dans cette solution. Donc, cela dit essentiellement pour la mémorisation et la tabulation, ce que nous allons faire ensuite est en fait de résoudre certains des problèmes de programmation dynamique les plus célèbres en utilisant la mémoisation et la tabulation. Donc, ce que nous allons faire est de voir le problème, de le lire, et de travailler à travers un exemple d'un essayé de le résoudre à l'aide d'une main. Et après cela, nous allons créer ou simplement générer un pseudo code. Et cela nous aidera à l'implémenter dans nos langages, Java, JavaScript et Python. Donc, le schéma de nos coûts sera le suivant. Nous allons avoir le problème que le pseudocode, puis l'implémentation. Donc c'est tout, fondamentalement ce que cette vidéo vous voit dans la prochaine. 6. Nombre de factures minimes pour retourner un montant: Très bien, donc dans cette vidéo, nous allons passer par l'un des exemples les plus populaires qui est généralement résolu avec la programmation dynamique. Et le problème va comme ça. Alors imaginez que vous avez un magasin et qu'un client arrive et commandé avec 60$ de nourriture. Maintenant, il vous donne une facture de 100$ et dans ce cas, vous allez retourner les restes, c'est les 40$. Donc, par exemple, supposons que nous ayons 100$ et qu'il achète avec 60$ et qu'il devrait le retourner. Maintenant, pour l'amour de ce problème, supposons que nous avons quatre types de cloches. Supposons donc que nous ayons la facture de 1$. Je les écris ici. Donc, nous avons l'odeur et c'est le $1, nous avons les cinq dollars. Nous avons aussi 10, et nous avons aussi le 25. Alors c'est tout. Nous avons donc ces quatre types de cloches. Maintenant, si nous voulons résoudre ce problème en utilisant un algorithme gourmand, essayons-le ici. Pour cet exemple, nous avons un retour de 40$. Et dans ce cas, l'algorithme gourmand va comme ceci. La première chose que nous allons faire est de chercher la plus grosse facture possible avec laquelle nous pouvons payer. Donc, dans ce cas, nous devrions retourner 40$. Laisse-moi l'écrire ici. Donc, c'est les 40$ que nous devrions retourner. Maintenant, nous allons vérifier aux côtés de ces quatre types, quelle est la plus grande quantité que nous pouvons extraire de ces 40 ? Dans ce cas, nous avons le 25, donc 40$ moins 25. Donc, nous utilisons cette 11 fois. Maintenant, on va en avoir 15. Et dans ce cas, nous avons aussi un 10 qui est plus petit que 15, donc 15, nous pouvons les extraire. Donc, nous utilisons ce 10 aussi une fois. Et cela nous laissera avec cinq, puis s'échappe. Enfin, nous avons cinq moins cinq, ce qui est égal à 0. Pour résoudre, nous avons également utilisé ce 5 une fois. Donc nous avons fini avec 25 plus 10 plus 5. Et ce cas, cet algorithme gourmand fonctionne en fait et il nous donne la solution la plus optimale, qui consiste à utiliser des factures de 25, 10 et 5$. Imaginez que nous ayons aussi un billet de 20 dollars au lieu d'avoir ces quatre types. Alors laissez-moi juste supprimer tout cela et essayons à nouveau. Donc, si j'ai juste ici un autre billet de 20 dollars, et essayons l'algorithme gourmand une fois de plus. Dans ce cas, maintenant nous avons déjà des dollars par défaut que nous devrions retourner. Et dans ce cas, l'algorithme gourmand fonctionnera exactement comme avant. Donc nous allons chercher la plus grande ou la plus grande ceinture que nous pouvons extraire de ces 40$ devrait être inférieure à ces 40$. Cependant, nous en avons 25. Donc on est bons. On va rester avec 15. Et dans ce cas, si nous voulons travailler avec 20$, nous ne pouvons pas parce que maintenant nous en avons 15. Nous devons chercher tout ce qui est égal ou inférieur à 15. Et cette affaire. Et donc on va rester avec la même chose qu'avant. Et ce n'est clairement pas la solution optimale. Donc, la solution optimale est de simplement utiliser les billets de 20 dollars fois deux. Donc nous allons utiliser ces billets de 20 dollars deux fois et nous allons obtenir les 40$ dont nous avons besoin pour retourner au client. Et dans ce cas, comme vous pouvez le voir, l'algorithme gourmand ne fonctionnera pas. Ce ne sera en fait pas la solution optimale. Nous allons donc utiliser la programmation dynamique à la place. Alors laissez-moi éclaircir tout cela et nous allons passer par un autre exemple en utilisant la méthode de programmation dynamique. Droit ? C'est donc un autre exemple. Donc nous avons 7$ que nous devrions retourner et nous avons les ceintures 1, 3 et 4. Dans ce cas. Ces cloches constituent celles que nous dessinons auparavant. Alors ne vous inquiétez pas à ce sujet, s'ajuste avec eux et s'enrôler. Et dans ce cas, ce que nous allons faire est de construire un tableau ou une liste. Et on va en parler dans une seconde. Mais tout d'abord, laissez-moi juste construire et ce tableau sera surdimensionné, ce sept plus un. Donc, dans ce cas, je vais juste dessiner sept. Très bien ici, donc 3, 4, 5, 6, 7. Et comme nous l'avons dit, certains plus un, ce qui est un cas S, les indices seront 0, 1, 2, 3, 4, 5, 6 et 7. Donc, comme nous l'avons dit, nous avons huit éléments dans cette liste. Et ce que nous allons faire, c'est que nous allons examiner cette liste de cloches une par une et vérifier la mise en œuvre possible de l'ajout possible dans cette hanche droite. Donc, en d'autres termes, ce que nous allons faire, c'est vérifier, par exemple, si nous n'avons qu'une facture de 1$, que va-t-il se passer pour eux ici ? Donc, dans ce cas, essayons-le avec la facture de 1$. Par exemple, si nous avons ce $1, mais combien de factures devons-nous constituer le 0 ? Et dans ce cas, nous n'avons pas besoin de construction, donc nous écrivons juste 0. Donc, ce n'est qu'un cas de base. Maintenant, supposons qu'on doit retourner 1$. Combien de billets de 1$ avons-nous besoin pour retourner 1$ ? On en a juste besoin. Maintenant, passons à la seconde. Donc, par exemple, si nous l' avons fait, nous devons retourner 2$. Combien de billets de 1$ le faire pour retourner ces $2 aurait juste besoin de billets de 1$. Donc, dans ce cas, ce que nous disons que nous avons besoin de 1$ pour retourner le montant qui est de 2$. Donc, pour faciliter les choses, ce sont là le montant et ce sont tout simplement le nombre minimum de factures que nous devrions retourner dans ce cas. Ce que nous disons ici, c'est que nous n'avons que ce bill de 1$, et c'est le nombre minimum de billets de 1$ que nous devrions rembourser si nous voulons avoir ces montants. Et bien, sans passer par tout ça, c'est la même chose. C'est assez simple. Nous avons donc besoin de billets de $3 pour retourner un montant de trois. On a besoin de 4567. Alors c'est tout. Fondamentalement c'est ce dont nous avons besoin. Laissez-moi simplement supprimer ceci et continuons avec. Donc, dans ce cas, nous venons de passer le $1 ici. Donc ce qu'il faut faire maintenant, c'est vérifier les 3$. Supposons que nous n' ayons pas seulement le seul diabète. Nous avons le $1 ainsi que le $3. Mais dans ce cas, ce que nous allons faire est de vérifier dès le début. Alors à 0, combien de bons de dollars devons-nous représenter le montant 0 ? On n'en a pas besoin. Maintenant, trois, combien de billets de $3 avons-nous besoin pour représenter un billet que nous pouvons pour en empêcher un avec $3. Nous passons donc à deux. Dans ce cas, nous allons vérifier aussi et nous sommes venus en présenter deux avec des factures de 3$. Donc nous allons passer à ces trois ici. Et dans ce cas, nous nous demandons combien de billets de $3 avons-nous besoin pour représenter ce montant de $3 ? Et la réponse est assez simple. On n'en a pas besoin, on en a juste besoin. Ce que nous disons ici, c'est qu'il nous faut un billet de trois dollars pour représenter ce montant. Et passons à la quatrième. Alors, combien de bits avons-nous besoin pour représenter ces quatre ? Et en fait, nous avons juste besoin de factures, c'est la facture de $3 plus la facture de $1 pour présenter cela. Donc nous n'avons pas besoin de ceintures, nous avons juste besoin de le faire et cette affaire, c'est trois plus un. Alors, qu'est-ce qu'on fait ? Nous annulons cela et remplacons ici aussi. Et en ce qui concerne les cinq dollars, combien de bits avons-nous besoin pour présenter le montant de 5 ? Et en fait, nous avons besoin de trois bits. Il s'agit de la facture de $3 Plus un plus de $1, alors c'est trois ans ici. Maintenant, comme pour le sexe, et combien de bits avons-nous besoin pour présenter le sexe ? Nous avons besoin, juste pour nous rappeler que trois, nous en avons autant que nous le voulons. Donc, au lieu de le représenter avec six, nous pouvons le présenter, il représentait deux trois. Dans ce cas, nous avons juste besoin de passer à la septième. Et dans ce cas, ce que nous allons faire est d'utiliser 3,3$ naissances, je suis désolé. Et c'est des billets de 2 à 3$ et 1 billet de 1$. Et dans ce cas, nous allons finir avec quelque chose comme ça. Nous avons 01212323. Passons à la dernière. C' est pour représenter le quatrième. Donc maintenant, nous avons aussi la ceinture de 4$. Dans ce cas, nous avons les numéros 1, 3 et 4 dollars à la fois et nous pouvons tous les utiliser dans ce cas. Maintenant, ce que nous allons faire est de sauter toutes ces jusqu'aux quatre parce que nous ne pouvons représenter aucune des plus petites quantités, 0, 1, 2 et 3. Et on va aller jusqu'au quatrième. Et dans ce cas, nous allons nous demander comme avant, combien de billets de 4$ avons-nous besoin pour représenter le montant en dollars par défaut ? Et la réponse est une. Alors combien ? Pour les billets d'un dollar ou les cloches, nous devons présenter les cinq et la réponse est tout à fait simple. Autrement dit, nous avons besoin d'un billet de $4 plus un billet de $1. Et dans ce cas, il y en a deux. Et la même chose vaut pour ça. Donc, nous en avons deux. Et bien sûr qu'on va vérifier. Donc maintenant, nous avons aussi quatre. Donc quatre plus un plus un est égal à 6$. Donc, dans ce cas, nous avons utilisé trois ceintures, et ce n'est pas optimal. Nous avons déjà une solution qui fonctionne mieux avec deux courroies. Ce sont les deux billets de $3. Si on en a trois ou deux, on va choisir de rester avec ces deux-là. Et enfin, si nous voulons nous demander le dernier, c'est les 7$. Dans ce cas, nous allons avoir besoin de 4 $3. Donc, peut le représenter avec trois au lieu d'un ensemble de trois. Alors c'est tout. Fondamentalement, c'est comme ça que nous avons obtenu avec une réponse finie. Autrement dit, nous pouvons représenter ce montant en utilisant seulement deux cloches. Donc c'est tout pour l'idée du travail jusqu'à maintenant. Petit pseudocode pour voir exactement ce qui se passe et comment nous pouvons y penser de cette façon. Alors qu'avons-nous dit quand nous étions à trois ou quatre ans ? Nous avons dit que nous pouvons sauter toutes ces choses, 43 car elles sont plus petites que trois. Et dénotons cela en fait par les cloches juste ici. Ce sont donc les croyances que nous avons. Ce sont le nombre minimum et c'est le montant. Maintenant, dans ce cas, si la cloche, sorte que les cloches sont 1, 3, et 4, donc la cloche représente soit 12 ou trois. Et dans ce cas, si ce bill est inférieur ou égal au montant que nous recherchons. Ce que nous allons faire, c'est mettre à jour le nombre minimum. Et si nous revenons à notre exemple, nous pouvons voir que le nombre minimum devrait être l'une des deux choses. C' est soit celui-ci ici, soit nous devons le mettre à jour comme ici. Par exemple, 012, nous n'avions pas besoin de les mettre à jour. Ils ont donc envoyé les mêmes ou les mises à jour, c'est-à-dire 1, 2, 2 et 2, comme nous pouvons le voir ci-dessus. Et dans ce cas, comment avons-nous obtenu ces chiffres mis à jour ? Donc, si nous examinons les quatre projets de loi et ces quatre projets de loi, ce que nous avons fait, c'est que nous avons pris ces quatre de chacun des montants que nous avons pris. Alors réfléchissons-y une seconde. Donc, par exemple, dans ce cas, quand nous avions ces cinq ici, donc nous avons $5 à retourner. Et ce que nous avons fait, c'est que nous soustrayons 4$ d'ici. Donc, nous avons 5 moins 4, donc nous avons encore 1$. Et dans ce cas, ce que nous allons faire, c'est regarder le montant de 1$ juste ici dans le tableau. C' est le montant de 1$. Et dans ce cas, ce que nous avons fait, c'est juste que nous avons pris ce nombre minimum ici et ajouté au nombre de billets, combien de billets de 4$ avons-nous utilisés ? Ici ? On a utilisé une seule facture. C' est la somme de $4 et nous devons quand même retourner le montant restant de $1. Dans ce cas, l'ensemble de données ici. Nous avons celui juste ici. C' est donc le montant que nous devrions retourner. Donc, 1, 4 billets de dollars plus 1 billet de 1$. Et ce cas, la réponse est deux, comme nous pouvons le voir, qui est en utilisant cette formule. Donc, ce que nous allons faire après, c'est que nous allons écrire un pseudocode pour cela en fait. Et puis nous allons l'implémenter en Java. 7. Pseudo-Code: Bon, alors maintenant que nous savons vraiment comment fonctionne cet algorithme, et nous avons passé par un exemple réel. Nous connaissons déjà l'idée derrière. Maintenant, essayons de trouver un pseudocode qui nous aidera et notre code à écrire un peu. Donc si on veut passer par le pseudocode, comme on l'a dit, la facture lourde est inférieure au montant. Dans ce cas, ce que nous allons faire, c'est que nous allons mettre à jour ce nombre minimum ici. Donc, ce que nous allons faire est de passer à travers toute cette liste pour chacune de ces ceintures. Donc nous allons en avoir deux pour boucles imbriquées l'une dans l'autre. Le premier sera, sera la boucle des factures, et le second sera le nombre minimum que nous allons mettre à jour chaque fois que nous passons par numéro. Et dans ce cas, ce que nous allons faire est de mettre à jour le nombre minimum chaque fois que la facture est inférieure ou égale au montant. Dans ce cas, par exemple, nous avons eu pour l'examen 4, 3 facture. Nous avons déjà ce 012 et il y en a plus petit que trois, donc nous n'avons pas besoin de les mettre à jour. Nous commençons par la quantité qui est plus grande ou égale, cette ceinture juste ici. Donc, comme nous l'avons dit, nous commençons à partir d'ici jusqu' à la fin de chacune des ceintures ici. Donc ce qu'on va faire, c'est vérifier le minimum entre deux choses. Comme nous l'avons dit, le minimum entre ce nombre ici et le nombre réel que nous pouvons mettre à jour. Ce que nous devons faire, c'est changer le nombre minimum. Le nombre minimum à ce montant spécifique devrait être mis à jour. Dans ce cas, il sera égal à 2, une des choses qui est le minimum entre eux. Il sera donc égal aux hommes entre la première chose et l'autre. Et comme nous l'avons dit, la première chose est le montant réel que nous avons déjà. Donc, ce sera le nombre minimum du montant. Donc c'est la même chose qu'avant, ou nous avons besoin d'en avoir un plus petit. Donc, ce que nous faisons en fait, c'est simplement vérifier si notre nouvelle solution est meilleure que l'autre. Donc, comme nous l'avons dit ici, nous avons déjà ces solutions 01234567, et elles sont représentées avec cette facture de 1$. Cependant, pour le montant de trois, par exemple, nous pouvons le représenter avec le montant de 3, 0, le projet de loi de trois dollars. Dans ce cas, nous enlevons ces trois cloches et nous venons d'ajouter une courroie est de 3$. Et dans ce cas, il est beaucoup mieux et plus efficace d'utiliser un billet de 13 dollars au lieu de 3 billets de 1$. Donc, ce que nous avons fait ici, c'est que nous avons pris ce montant trois et juste, juste, attaqué le projet de loi S3 d'ici. Donc nous sommes partis avec 0. Et ce cas, nous sommes allés jusqu'à la quantité de 0 et nous regardons ce nombre minimum et dans ce cas 0. Et donc ce qu'on a fait, c'est qu'on n'a utilisé qu'une seule pilule ici. Et puis nous vérifions pour ce montant 0. Et on a utilisé une cloche 0 ici. Et cela nous laissera avec un antigène cloche. C' est pourquoi nous en avons trois ici. Et la même chose vaut pour ces six ici. Ce que nous avons fait, c'est que nous avons utilisé 2 factures de 3$. Donc nous ce x ici, moins deux fois trois, ce qui est égal à 0. Donc, ce trois est utilisé deux fois. Donc, utilisez des tuples. Et nous sommes retournés jusqu' au nombre minimum ou au montant de 0 et nous avons vérifié le nombre minimum, c'est-à-dire 0. Donc nous, nous utilisons 02 moins 0 pour plus 0, je suis désolé, est égal à deux. Donc on a fini par le frapper. Donc c'est le travail réel à travers. Donc, si vous voulez y penser d'une autre façon, pour ces six ceintures ici, ce qu'on a fait,c' pour ces six ceintures ici, ce qu'on a fait, est qu'on a dit que c' soit des billets de 6$ ou quelque chose d'autre en utilisant ces trois, Dahlberg juste ici. Et dans ce cas, ce que nous avons fait, c'est que nous venons de prendre cette facture de 3$. Donc c'est six moins trois. Et cette affaire, on a fini avec trois, non ? Donc, nous n'avons utilisé qu'une seule facture d'ici. Et puis nous avons vérifié au montant de trois, ce qui est juste ici. Combien, quel est le nombre minimum dans ce cas que nous avons besoin pour finir avec un retour tous les montants que nous avons dans ce cas pour trois, nous pouvons clairement voir que c'est un. Et c'est ainsi que nous avons obtenu une cloche plus 1, ce qui équivaut à deux factures. Donc c'est ça. C' est une idée générale. Si nous avons la multiplication dans ce cas, nous pouvons l'utiliser directement. Cependant, c'est la façon réelle. Laissez-moi les supprimer et nous sommes bons. On peut continuer. Donc, nous voilà M. Eh bien, je suis désolé. Donc, nous avons Bill. Donc, si le bill est inférieur à la monture, comme nous l'avons dit plus tôt, nous devons mettre à jour le nombre minimum, qui sera égal soit au même, soit au même, nous l' avons ajouté, comme nous l'avons dit. Donc, c'est une facture plus le nombre minimum au montant moins la facture. C' est logique. Laisse-moi l'écrire et je l'expliquerai. Donc minimum entre le montant réel que nous avons moins la ceinture que nous avons pad que nous avons. Donc c'est tout en gros. Maintenant, si nous voulons passer par cet exemple en utilisant cette formule, Allons-y et faisons-le. Et bien sûr, je ne vais pas passer par tout l'exemple. Je vais juste prendre des situations spécifiques. Donc, par exemple, supposons que nous en soyons à cinq ici. Et nous avons juste les billets de 3$ que nous pouvons représenter ces 51$ et ce cas ce que nous allons faire. Nous en sommes donc à ce stade. Et nous allons réfléchir à travers le processus. Nous avons ces billets de $3. Et dans ce cas, ce qu'on va faire, c'est qu'on va en ajouter un. Donc c'est soit le minimum entre deux choses, non ? Donc c'est celui-là juste ici, qui est cinq. Tu ne le vois pas maintenant parce qu'on l'enlève juste avant, mais c'est juste là. Et ça, c'est cinq. Donc c'est cinq ou autre chose. Et l'utilisation de cette formule est un plus le montant minimum, minimum entre la quantité, l'esprit, l'esprit. Et dans ce cas, ce que nous allons faire, c'est donc cinq ou un, plus. Nous allons aller jusqu'au nombre minimum de montants. Dans ce cas, le montant est de cinq. Le constructeur Cupidon est trois. Donc, le nombre minimum ajouter 5 moins 3, ce qui est le nombre minimum à deux. Dans ce cas, nous allons regarder ça. Et comme nous pouvons le voir, nous avons le nombre minimum dans ce cas est de deux. Donc 1 plus 2, ce qui est 3. Donc, le minimum entre 53 est en fait trois. Et c'est ce que nous avons ici, c'est le numéro trois. Nous pouvons donc représenter les billets de $5 avec un billet de trois dollars et des billets de $1. Alors c'est tout. C' est ainsi que nous pouvons utiliser cette formule. Et si on l'a essayé pour la dernière fois, on peut l'essayer ici. Alors avant ça, on en avait trois ici. Et dans ce cas, ce que nous faisons en fait, c'est que nous allons en ajouter un pour un billet d'un dollar. Alors laissez-moi juste supprimer ceci et continuons. Donc le minimum entre deux choses, le montant réel que nous avons ou le nombre minimum réel que nous avons déjà, ou nous devons le mettre à jour en ajoutant un billet pour un dollar. Donc il en a un. Plus. Nous allons au nombre minimum au montant qui est 7 moins wL, qui est 4. Donc 7 moins 4 est 3. Donc on va aller jusqu'à ces trois ici. Nous allons examiner le nombre minimum. Dans ce cas, c'est un. Nous allons en ajouter un ici, donc c'est le minimum entre 32. Donc la réponse est deux. C'est ça. Fondamentalement, c'est comment nous pouvons utiliser ce pseudocode pour nous aider à écrire notre code en ce moment, c'est la partie la plus difficile. Nous venons juste avec cette méthode réelle ou un algorithme réel ou une idée que nous pouvons utiliser pour résoudre le problème spécifique. Et en utilisant cette méthode, nous avons pu trouver la solution la plus optimale. Contrairement à l'algorithme gourmand que nous avions au début. Dans ce cas, comme nous l'avons dit, nous pouvons représenter ces $7 construits avec un pour des billets d'un dollar et 13 crédules. Et ce cas, la réponse est deux. Et cela étant dit, c'est la fin du pseudo code ici. Et la prochaine vidéo, nous allons implémenter notre fonction en utilisant Java. Alors, à vous voir. 8. Mise en place minimale: Bon, maintenant que nous savons comment cet algorithme fonctionne exactement, et nous avons écrit le pseudocode qui va nous aider dans notre passage à travers le code. ce moment. On peut commencer par le codage. Et en fait, c'est l'un des plus importants, mais vous devriez toujours commencer par ça, quelque chose comme ça. Ainsi, vous pouvez écrire votre code ou écrire vos pensées sur un morceau de papier et peut-être dessiner certaines choses. Dans ce cas, nous dessinons cette liste et nous mettons à jour chaque fois que nous passons à travers une cloche. Donc vous aviez besoin de travailler avec un stylo et papier et pas seulement de visualiser toutes les choses dans votre tête. Surtout dans la programmation dynamique. Parce que la visualisation de quelque chose ou vous avez des travaux généralement feuille des problèmes plus simples. Cependant, dans certains problèmes profonds ou complexes, vous devez toujours utiliser un stylo et du papier. Et cette affaire, allons à notre Eclipse. Et dans ce cas, ce que nous allons faire est de commencer par créer la fonction. Donc, je vais simplement, nous avons juste besoin de Min retourne le nombre minimum de changement, qui est un nombre entier et un nombre minimum de fonction vide, dans ce cas, ce que nous allons prendre, le montant qui retournera et il est désigné par N. Et combien ou le type de ceintures que nous avons. Dans ce cas, nous allons les nommer cloches. Alors ouvrons et nous allons commencer par implémenter cela. Donc, la première chose que nous allons faire est de créer cette liste dont nous avons parlé plus tôt, et c'est le nombre minimum. Donc, pour le créer, je vais simplement créer une liste de nombres minimum. Et il est en fait contredit la, c'est la même chose que la méthode, non ? Quatre, si intime différemment. Et dans ce cas, ce sera la taille, le nombre ou le montant de plus un, comme nous l'avons dit. Et ce que nous allons faire est d'abord de le remplir avec la valeur maximale que nous pouvons. Donc, nous allons utiliser des tableaux qui ont senti. Et ce que nous allons faire est de remplir ces cloches avec un entier, cette valeur max. C' est ainsi que nous pouvons stocker le maximum de valeur entière ici. Et il semble que nous avons besoin d'importer des tableaux. Donc, nous essayons juste l'espace de contraste, appuyez sur Entrée, et il va juste prendre juste ici. Maintenant, cette zone, bien que nous n'ayons pas encore retourné l'entier, mais nous pouvons le gérer plus tard. Mais pour l'instant, ce que nous allons faire est de nous rappeler que nous voulons toujours commencer avec une quantité de 0. Donc, le nombre minimum devrait être 0. Dans ce cas, ce que nous allons faire est de stocker et le, je suis désolé, ce n'est pas double est le nombre minimum juste ici. Et nous allons commencer au minimum à 0, nous allons stocker 0. C' est donc la première étape. Maintenant, nous allons passer à travers toutes les données réelles. Donc ce que nous allons faire est de passer par le bus et à l'intérieur de chacun, eh bien, nous allons passer par le montant dans ce cas. Donc int je égal à 0 tout le chemin aux cloches, cette longueur et ensuite mis à jour. Maintenant, le second sera j égal à 0. Ensuite, J est inférieur au nombre minimum. Je suis désolé. Donc ici, j'ai ajouté S par erreur. Et maintenant, on est bons. Donc, nous allons aller jusqu'au nombre minimum de cette longueur, puis mis à jour. Ce qu'on va faire, c'est vérifier si la cloche est inférieure à la quantité. Alors, comment faites-vous ça ? Nous vérifions simplement si les cloches chez moi sont inférieures à quelque chose, qui est le montant. Et dans ce cas, le montant est en fait l'indice. Comme nous pouvons le voir, le montant est l'indice de ce tableau de nombres minimum ou moins. Donc c'est, si c'est inférieur ou égal à ce montant, nous allons faire quelque chose de mal. On va, on ne va rien faire. Dans ce cas. Ce que nous allons faire, c'est prendre la différence entre ce montant et la cloche. Donc, nous pouvons dire que ce j est le montant et les factures à ISB réelle Bell. Donc, la différence sera j moins ceinture satire. Et nous voulons aussi calculer la cloche dans ce cas. Donc je vais indiquer par peut-être que ce pourrait être le nombre minimum dans ce cas, encore une fois, je viens de mentionner par B. Et ce que nous allons faire est d'ajouter celui-ci plus le montant ou le nombre minimum. Cette différence. Donc, ce que nous avons fait ici, c'est que nous avons calculé la formule. La formule dit que c'est le nombre minimum. Et le minimum. Il s'agit de la nouvelle mise à jour. Ce sera un plus ça ici. Et comment nous avons calculé ceci, c'est que nous avons pris le nombre minimum et le montant moins cloche et ça le frappe. Donc 1 plus 1 plus le nombre minimum. Voilà comment, c'est le nombre minimum au montant moins la facture. Et nous calculons la différence juste dans la ligne précédente. Dans ce cas, nous avons eu celui qui pourrait être mis à jour. Donc, dans ce cas, ce que nous allons faire est de revenir. viens de dire que les ceintures à moi seront les maths, mais les hommes. Donc, c'est l'une des deux choses. C' est le je suis désolé, le nombre minimum chez moi et J. Je suis désolé. Et ce sera l'une des deux choses. Ce sera soit le même qu'avant et, soit le BI que nous venons de créer plus tôt. Et ce cas, nous pouvons mettre à jour ce nombre minimum facilement. Donc, ce que nous avons fait en fait, c'est que nous avons pris la différence entre le montant et la facture, nous avons calculé que le nombre minimum, nous avons juste calculé cette formule et nous avons obtenu ceci ici. Ensuite, nous avons dit que le nombre minimum à ce montant devrait être égal au nombre minimum à ce autour ou un plus le nombre minimum de montant 2012. Et cette affaire, on l'a juste là, on l'a mise à jour. Donc c'est le même ou celui qui est TBI. Maintenant, ce que nous allons faire est de vérifier si le nombre minimum à la fin ou à oui. Donc, à la quantité n'est pas égale à la valeur Emax. Et tu vas te dire pourquoi dans une seconde. Nous allons retourner le nombre minimum à et sinon retourner moins un. Donc, ce que nous avons fait ici, c'est que nous avons vérifié, nous pouvons effectivement faire ou retourner ce montant. Dans ce cas, si nous pouvons obtenir cette dernière valeur ne devrait pas être la valeur maximale. Ce devrait être un nombre naturel. Et si c'est le cas, nous retournons juste ce numéro. Et si ce n'est pas le cas, nous allons retourner minuscule 1, même chose que nous ne pouvons pas calculer ou nous ne pouvons pas avoir ce retour avec cette stratégie de facture. Et un exemple de cela est d'imaginer que nous devons retourner des billets de 5$ ou un montant de 5$ et que nous n'avons que 78 doubles. Dans ce cas, nous ne pouvons pas retourner cinq parce que nous n'avons que 78. C' est pourquoi ce sera toujours la valeur maximale et nous ne pouvons pas retourner le montant, donc nous retournons juste moins un. C' est donc la mise en œuvre. Je pense que c'est assez simple après toute l' explication que nous avons faite ici et que nous avons traversé. Et c'est tout pour cette vidéo. se voit dans la prochaine. 9. Modèle minimum: Ok, Donc, dans cette vidéo, nous allons implémenter notre fonction ou le pseudocode que nous avons créé plus tôt en utilisant JavaScript. Donc, sans plus tarder, allons juste y aller. La première chose que je vais faire est de créer le nom de la fonction au changement minimum. Et dans ce cas, il faudra et factures en tant que paramètres. Allons l'ouvrir. Et dans ce cas, ce que nous allons faire est de créer un tableau en JavaScript. On peut le faire. Donnons-le un nom. Donnons-le un nom. En fait, le montant. Et ce que nous ne voulons pas faire, c'est prendre ce montant. Et bien sûr, nous allons passer par tout ça dans un peu. Mais pour l'instant, ce que nous allons faire est de le créer comme un tableau d'un plus 1. Et nous allons le remplir d'infini. Donc c'est tout, fondamentalement ceci, comment nous pouvons créer un tableau en JavaScript. Maintenant, ce que nous allons faire est de mettre à jour ce montant dans le premier devrait être égal à 0. Donc, si nous revenons à celui-ci, nous pouvons voir que ce montant devrait être égal à 0. En fait, nommons le nombre minimum, puisque nous l'avons fait ici, nombre minimum. Donc on va juste, j'entends le nombre minimum. La même chose s'applique ici. Maintenant, ce que nous allons faire est de créer notre boucle for. Donc la première chose que nous allons créer est la boucle for pour les cloches. Donc ce que nous allons faire, c'est créer, construire des cloches, des cloches, et ensuite l'ouvrir. Maintenant, le second sera pour le nombre minimum réel. Et nous allons indiquer ces indices par montant, comme nous l'avons dit ici. Donc on va le créer ici pour le labo. Montant égal à 0, alors le montant doit être inférieur au nombre, nombre minimum cette longueur. Et bien sûr, nous allons augmenter le montant. Maintenant, ouvrons et maintenant nous pouvons commencer avec notre code réel. Nous allons simplement écrire le pseudocode que nous avons écrit plus tôt. On dit donc que si le montant est supérieur ou égal au bill, nous devons faire quelque chose. Dans ce cas, ce que nous allons faire est de mettre à jour le nombre minimum, qui sera égal, devrait être au montant pour être égal au minimum entre deux choses. Donc, nous allons utiliser les hommes de méthode. Et ce minimum sera le nombre de nombre minimum de montant et le nombre minimum de montant moins la facture. Maintenant, ce que nous allons faire, bien sûr ici, nous devons en ajouter un. Donc, c'est le nombre minimum de montant moins p plus 1. Et dans ce cas, nous avons fini avec cette fonction. C' est ainsi que nous pouvons l'implémenter en utilisant JavaScript avec ce pseudocode que nous avons créé plus tôt, avec juste l'utilisation de la matière destinée à prendre le minimum entre ces deux choses. Et bien sûr, nous allons le remplir d'infini. Et n'oubliez pas de remplir le premier avec 0, car c'est comme le cas de base juste ici. Maintenant, ce que nous allons faire, c'est simplement les rendre ici. Gardez donc à l'esprit que si cette fonction fonctionne correctement, elle devrait mettre à jour la dernière. Cependant, parfois nous pouvons avoir l'infini à la fin. Et dans ce cas, si vous avez l'infini, cela signifie que nous n'avons pas résolu le problème, il n'y a pas de solution appropriée. Permettez-moi donc de vous donner un exemple pour une chose telle que supposons que nous ayons les cinq dollars à représenter et que nous en avons 678 également. Dans ce cas, il n'y a pas de solution appropriée et ce dernier infini ne sera pas mis à jour puisque 5$ ne peuvent pas être représentés avec 67 ou 8$ factures. Donc ce que nous allons faire est de vérifier si ce dernier est égal à l'infini, nous allons retourner minus1. Sinon, nous allons retourner le nombre minimum réel que nous avons obtenu. Donc maintenant, si nous retournons réellement ceci, laissez-moi juste le retourner juste ici pour que le nombre minimum de retour à, et ce que nous avons fait pour obtenir un simplement le dernier dans la liste. Donc c'est la liste que nous allons obtenir 0, 1, 2, 1, 1, 2, 2, 2. Et on va avoir le nombre minimum. Maintenant, pour être plus clair, je vais d'abord retourner toute la liste et ensuite nous allons en discuter. Donc, la variable n sera égale aux données réelles ici, qui est sept. Et le dernier serait 1, 3, 4, ainsi et égal à sept. Et la liste sera égale à la liste 134. Et dans ce cas, ce que nous allons faire est d'appeler cette fonction de changement minimum avec un et factures. Et bien sûr, nous allons nous connecter. Donc console.log et chance cette fonction. Maintenant, si on retourne ici. Et passons à JavaScript, la programmation dynamique. Et ce que nous allons faire est d'utiliser simplement les hommes de noeud, changer ce JS et nous allons obtenir 0, 1, 2, 1, 1, 2, 2, 2, 2, ce qui est exactement la même chose que nous avons générée manuellement. Faire maintenant est de retourner le dernier en utilisant le nombre minimum à. Et maintenant, si nous revenons en arrière et grandioses, nous allons en obtenir deux comme le nombre minimum de changements que nous avons besoin pour présenter un nombre spécifique. Cependant, si par exemple, nous n'avons pas cela. Supposons qu'on en ait cinq. Dans ce cas. Supposons que nous ayons 678 comme ceintures. Ce que nous allons obtenir est en fait l'infini et ce n'est pas une bonne réponse. Nous devons revenir moins un. Dans ce cas, nous avons simplement besoin de vérifier si le nombre minimum à n est égal à l'infini. Maintenant, c'est le cas. Nous allons le mettre à jour en moins 1. Il y a donc plusieurs façons. Ainsi, par exemple, une façon de faire comme si ce nombre minimum est égal à l'infini, mais nous ne le faisons pas est simplement de retourner ou de mettre à jour. Donc, si elle est égale à l'infini, nous allons, je suis désolé, nous devons ajouter les crochets afin que le nombre minimum à n soit égal à l'infini. Nous allons le mettre à jour en moins 1. Maintenant, si on retourne en arrière et que l' on touche rafraichissement, on aura moins 17 f infini. Une autre façon de le faire est de simplement vérifier à côté de la déclaration de retour. Donc, pour ce faire, nous vérifions simplement si ce nombre minimum est égal à l'infini. Si c'est le cas, nous devons faire quelque chose. Et pour ce faire, nous écrivons simplement ce point d'interrogation et ensuite nous avons deux options. Cette déclaration est donc satisfaite. La première option sera, donc ça ressemble à ceci. Donc, si cette équation est satisfaite, si elle retourne true, nous allons obtenir cette option. Sinon, on va avoir le deuxième. Donc, si c'est vrai, mais nous allons faire est de retourner minuscule 1. Sinon, nous allons retourner le nombre minimum à Penn. Et vérifions à nouveau. Si on recommence à courir, on aura moins de 1 comme avant. Maintenant, par exemple, si nous avons ceci ici comme bronzage, et revenons en arrière, réexécutez-le. Et bien sûr, il ne devrait pas l'être, devrait être multiple de six, par exemple. Maintenant, si nous revenons en arrière, nous allons en obtenir deux comme le nombre minimum de changements que nous pouvons avoir en utilisant ces 12 et ces factures comme montant. Donc, c'est tout essentiellement pour cette implémentation. C' est ainsi que nous pouvons l'implémenter en JavaScript. Cela dit, c'est la fin de cette vidéo. se voit dans la prochaine. 10. Mise en place du nombre minimum Python: Ok, Donc dans cette vidéo, nous allons faire est de créer la fonction Python pour notre pseudocode que nous avons trouvé plus tôt. Donc, laissez-moi juste ajouter quelques choses juste ici parce que le supprimé. Donc, ce que nous allons faire est de déterminer la fonction minimale de celui-ci ici. Laisse-moi juste faire plus gros. Nous avons donc $7 et les changements ou les plus profonds que nous avons sont 1, 3 et 4. Donc, pour ce faire, Commençons par définir nos paramètres tout de suite en Python. Donc n égal à sept. Et nous avons cette liste qui est 134. Et ceux-ci représenteront les dels de savon des gens égaux à 1, 3, 4. Maintenant, nous pouvons commencer par notre fonction. Donc, ce que nous allons faire est au début, nous devons créer cette liste de nombres minimum et elle devrait être initialisée à l'infini. Et après cela, ce que nous allons faire est de l'ajouter ou le modifier chaque fois que nous traversons chacun de ces éléments. Donc, ce que nous allons faire au début est de créer la liste réelle en ajoutant simplement ou en nommant le nombre minimum. Et ce sera égal à un moins que dans ce cas, ce que nous allons faire est de le remplir avec lui. Et comment nous pouvons faire cela, nous pouvons simplement passer à travers une boucle for dans la plage de n plus un, puis le remplir, remplir le nombre minimum que nous allons y ajouter. Float, indiquant qu'il s'agit d'une infinité. Alors maintenant un libre aller de l'avant et l'imprimer. On va voir ça. Donc, si je vais de l'avant et imprimer celui-ci, nous allons obtenir ces infini comme éléments dans cette liste. Maintenant, pour commencer, revenons ici et voyons notre fonction, notre, notre pseudocode. Rappelez-vous maintenant que nous avons besoin de celui-ci, qui est le premier qui sera égal à 0. Donc, avant de faire quoi que ce soit, faisons-le juste égal à 0. Donc nombre minimum à 0 pour être égal à 0. Maintenant, nous pouvons passer par notre code, alors laissez-moi le relancer ici. Et comme vous pouvez le voir, le premier est 0 et tout le reste est infini. Donc, ce que nous allons faire maintenant est de passer à travers 24 boucles imbriquées nettes. Et tout en faisant cela, nous allons passer à travers toutes ces choses et ensuite mettre à jour toutes ces choses. Donc, laissez-moi juste créer pour Bell et ceintures, nous allons commencer avec ça et ensuite nous allons passer au nombre minimum. Donc, pour ce faire, nous pouvons simplement créer une seconde pour la boucle en utilisant une plage de la longueur de ce nombre. C' est donc pour le montant et la plage de la longueur de cette liste réelle que nous avons créée. C' est le nombre minimum. Et ce que nous allons faire au début, c'est vérifier si le montant est supérieur ou égal à la facture. Dans ce cas, si c'est le cas, nous devons le mettre à jour. Et c'est l'une des deux choses selon nos formules. Il s'agit du minimum entre le montant minimum réel et ou un plus le nombre minimum à la quantité moins le déversement. Alors laissez-moi juste implémenté ici. Comment on fait ça ? Donc, il est le nombre minimum au montant devrait être égal à deux choses. Le minimum entre le nombre minimum et nombre minimum 1 plus le nombre minimum au montant moins le, c'est tout. Fondamentalement, c'est ainsi que nous pouvons l'implémenter. Maintenant, si nous revenons en arrière et nous allons appuyer sur rafraichir et exécuter ce code à nouveau. Comme vous pouvez le voir, nous avons 0, 1, 2, 1, 1, 2, 2, 2. Et si on le regarde ici, on a 0, 1, 2, 1, 1, 2, 2, 2. Donc c'est exactement le même résultat. Maintenant, gardez à l'esprit que ce n'est pas ce dont nous avons réellement besoin. La solution réelle de ce problème est d'obtenir le dernier ici. Donc, nous allons retourner le dernier d'ici. Maintenant, une chose à laquelle nous devons prêter attention est que peut-être certains, il n'y a pas une telle combinaison qui nous permet d'obtenir le nombre spécifique. Supposons donc que nous ayons les 5$ et tout le dénominateur, tous les meilleurs que nous ayons, nos 678. Donc, dans ce cas, nous pouvons en représenter cinq en utilisant n'importe lequel de ces projets de loi. Donc la réponse restera à l'infini. Maintenant, dans ce cas, si la réponse est l'infini, nous ne retournons pas l'infini, nous retournons juste moins un, indiquant qu'il n'y a pas de solution pour un tel problème. Dans ce cas, nous devons faire attention et nous assurer que nous obtenons ce cas de bord. Alors comment on fait ça ? Nous pouvons simplement créer une déclaration if si le nombre de pièces de monnaie. Donc, si le nombre minimum est le montant, ou peut-être si le nombre minimum au dernier, qui est n, est égal à l'infini. Ce qu'on va faire, c'est me laisser juste essayer de couler essayé ici. Et si cela est égal à ce nombre, ce que nous allons faire est de retourner minus1, minus1. Sinon, nous allons imprimer le nombre exact, le nombre minimum à. Et donc c'est tout. Fondamentalement, c'est comme ça que nous pouvons le faire. Maintenant, si nous revenons en arrière, appuyez sur refresh, et exécutez ce code à nouveau, pensez que nous avons un retrait ne correspond pas à l'autre. Très bien, alors réparons ça très vite. On va faire ça, c'est faire comme ça. Et maintenant je pense qu'on est bons si on y retourne, on recommence. Et la réponse serait deux. Maintenant, dans ce cas, si nous avons l'exemple dont nous avons parlé plus tôt, nous avons 6, 7 et 8. Si nous revenons et nous rafraîchissons, nous aurons moins un, qui indique qu'il n'y a aucun moyen d'obtenir ce montant en utilisant ces trois types de factures parce qu'elles sont plus grandes que cinq. Donc c'est tout fondamentalement pour ce problème, c'est comment nous pouvons être rencontrés avec Python. Cela dit, c'est la fin de cette vidéo. se voit dans la prochaine. 11. Nombre de moyens de renvoyer un montant: Très bien, donc dans cet exemple, il va y avoir un autre problème, à le nombre de façons dont nous devons apporter un changement pour un montant précis. Supposons donc que nous ayons un montant de $5 qui est juste ici. Et ce que nous allons faire, c'est calculer le nombre de façons de représenter ces cinq dollars si nous avons ces factures ici. Donc, si vous avez 1.2.34 facture, et dans ce cas, ce que nous allons faire est d'utiliser la programmation dynamique pour avoir la solution la plus optimale ou le nombre exact de façons que nous pouvons calculer en utilisant ces factures pour avoir ce montant de 5$. Donc, pour ce faire, commençons par créer la liste dont nous allons avoir besoin. Et comme nous l'avons déjà dit, ces cinq dollars, nous allons créer une liste qui peut faire jusqu'à 5$. Donc, pour ce faire, nous allons avoir la taille de cette liste cinq plus un, ce qui est six. Et ce cas, laissez-moi juste créer cette liste ici. Nous avons donc 123456 éléments dans cette liste. Donc, les indices sont les suivants, 012, jour 4 et 5. Ces indices représentent donc le montant. Laisse-moi l'écrire ici. Je suis désolé. Nous avons donc le montant. Et ce que nous allons avoir ici, c'est le nombre de façons. Donc je vais juste le désigner comme un certain nombre de façons. Donc, ce que nous allons faire, c'est de parcourir toute la base que nous avons un par un et vérifier le nombre de façons dont nous pouvons représenter ces cinq dollars en utilisant ces Belk ici. Donc, tout d'abord, ce que nous allons faire est d'initialiser tous ceux-ci à 0. Donc 00000. Cependant, le premier serait le cas de base. Et il est sûr de dire que celui-ci devrait être initialisé comme un seul. Puisque si nous y réfléchissons, si nous n'avons pas oh, nous avons un billet de $1 ou $2 ou trois ou $4 et nous devons présenter le montant de zéros. n'y a qu'une seule façon de représenter ce montant en n'ayant pas ou en n'utilisant pas ces montants. Donc, il est sûr de dire que nous pouvons utiliser le nombre de façons comme un pour le montant 0. Droit ? Maintenant, si on regarde ça, commençons par celle-là. Laisse-moi changer la couleur. Donc, maintenant, nous travaillons sur ce projet de loi de 1$. Alors, combien de façons pouvons-nous représenter le montant d'un en utilisant une facture de 1$ ? Et c'est assez simple. Nous pouvons le représenter d'une manière. Donc au lieu d'avoir 0 ici, on va en avoir un. Passons maintenant au montant de 2$. Combien de façons pouvons-nous représenter ces 2$ en utilisant cette facture de 1$ ? Et bien sûr, c'est pareil. Nous n'avons qu'une façon d'utiliser des billets de 2$. La même chose ici. Donc on va avoir 111. Ce que nous disons, c'est que nous pouvons représenter ce montant de 34 ou 5$ en utilisant un billet de 1$ d'une seule façon. Et c'est à utiliser, par exemple, ici si nous avons un montant de 3$, alors comment pouvons-nous, comment pouvons-nous obtenir ce montant de 3$ ? Nous pouvons utiliser 3 $1 mieux à partir d'ici. Et c'est la même chose pour 4 $5. Passons maintenant à la seconde. Autrement dit, nous avons ces $2, mais maintenant ce que nous allons faire, c'est simplement sauter montant 01 puisque nous pouvons présenter ces montants en utilisant un billet de $2, parce que deux sont supérieurs à 01. Donc nous allons aller jusqu'à ce montant de 2$. Maintenant, réfléchissons-y. Qu' est-ce qu'on a ? On a ces 2 dollars, non ? Et cela, nous avons aussi ces billets de $2. Donc, nous pouvons représenter ces montants de 2$ en utilisant 1 facture de 2$ d'ici. Et bien sûr, nous ne voulons pas oublier que nous pouvons représenter d'une façon à l'aide de ces billets d'un dollar. Donc, ce que nous allons faire est de supprimer ceci et d'en ajouter deux ici parce que nous pouvons le représenter maintenant de deux façons. Et nous allons trouver la formule dans un peu, mais nous allons y arriver maintenant. Donc, par exemple, nous avons maintenant ce montant de 3$. Donc ce que nous allons faire, c'est de représenter aussi de deux façons, non ? Alors laissez-moi écrire ici aussi, et réfléchissons à comment pouvons-nous représenter ce montant trois. Donc, si on a 3$, on peut utiliser deux, euh, 3$ factures. Donc 3 fois 1 ou 2, ou 1 à 1 dollar et 1 billet de 1 dollar, n'est-ce pas ? Donc 12. Les factures et 1 billet de 1$. Et nous allons obtenir le montant qui est trois comme avant. Maintenant, si nous revenons à ici et voyons combien de façons pouvons-nous représenter ce montant. Donc, si nous avons $4 et que nous allons avoir besoin soit pour des billets de $1, soit pour des billets de deux dollars, soit 1 billet de $2 plus 2 billets de $1. Donc, si cela a du sens, c'est bon si ce n'est pas le cas, réfléchissons à ce que nous avons ici pour des billets de 1$. Et ici, nous avons, ou nous devons, des billets d'un dollar, ou nous avons des billets de 1 $2 et un billet de 1$. Donc tous ces éléments seront les mêmes que vous pouvez voir ici. Si je le dessine. Nous allons avoir ici aussi, et ici, la même chose et nous avons des factures de 1$. Donc c'est tout en gros. Maintenant, pensons à la formule. Comment peut-on obtenir ça ? Nous avons trois façons ici. Nous avons donc trois possibilités pour représenter ce numéro quatre. Et au lieu d'en avoir un ici, nous allons l'enlever et en ajouter trois. Donc, si nous y réfléchissons, nous pouvons voir que si nous avons ce billet de $2.2, ce que nous avons fait en fait, c'est d'en ajouter un au nombre de façons dont nous avions adopté. Donc, pour être clair, laissez-moi juste écrire la formule ici. Donc, ce que nous disons est que nous devons mettre à jour ce numéro, qui est un certain nombre de façons à un index spécifique. Supposons que c'est l'annonce I. Ce sera égal à un plus le nombre de façons. Et laissez-moi supprimer tout cela. Et c'est le nombre de façons à ce montant spécifique, qui est quatre moins ce que nous obtenons d'ici. Et nous allons nommer ceci, cette liste comme des factures et désigner chacun d'entre eux comme le projet de loi. Donc c'est la quantité moins ceinture. Donc, dans ce cas, si nous allons regarder cet exemple, nous sommes à la montagne avant et la construction numéro deux. Donc, ce que nous avons fait, c'est que nous avons ajouté celui-ci d'ici. Donc ici, ce n'est pas un, c'est le nombre de façons. Donc c'est plus 0 égal. Et laissez-moi juste supprimer ceci. Donc, c'est en fait égal à ce nombre de façons à I, égal au nombre de façons à i. Donc ce que nous avons déjà, le nombre réel de façons plus le nombre de façons. Entendons ce nombre de façons au montant moins les factures. Donc c'est la formule que nous allons utiliser maintenant si vous l'utilisez ici, Pensez-y. On en a déjà un ici. Donc, le nombre de façons à, j'écris ici, il sera égal à un plus nombre de façons à 4 moins 2, ce qui est égal à 2. Donc, si nous revenons à l'index pour voir que nous en avons déjà deux ici. Donc nous allons avoir 1 plus 2, ce qui est égal à 3. Et c'est ce que nous avons obtenu en utilisant la pensée ou en utilisant l'exemple que nous avons fait auparavant. Nous avons donc découvert que nous avions trois façons de représenter ces quatre. Nous avons 1 billet de 2$. Passons à la dernière, qui est cinq. Et en utilisant cette formule, nous pouvons calculer que si nous avons le montant de 5$ et que nous avons ceci, ces tuples, nous pouvons avoir un seul moyen plus le nombre de façons à cinq moins deux, qui est le nombre de façons à cet indice ici, trois. Donc c'est deux, donc 1 plus 2 sera 3. Maintenant, si on fait exactement la même chose pour les 34 qu'on peut avoir. Laisse-moi juste changer la couleur. Laisse-moi juste rendre l'encre bleue plus facile. Donc, ce que nous allons faire, c'est juste les recadrer d'ici et les coller ici. Supprimons ceci et continuons. Ce qu'on dit, c'est que maintenant on est à trois ans. Donc, comme nous l'avons dit, nous pouvons sauter 012 parce qu'ils sont plus petits que trois. On va aller jusqu'à trois. Et maintenant ce que nous allons faire est de dire que nous pouvons représenter cet Amar trois en utilisant deux façons plus le nombre de façons à trois moins trois. Donc cette quantité moins ces trois ici, qui est la ceinture. Et si nous passons au nombre de façons, trois mois aujourd'hui sont à 0, donc nous en avons un. Donc au lieu d'en avoir trois ici, nous allons avoir 2 plus 1, ce qui est 3. Maintenant, nous allons faire exactement la même chose pour celle-là. Donc c'est 3 plus le nombre de façons à la quantité moins mil, qui est quatre moins trois, ce qui est en fait un. Donc nous allons changer ça en 3 plus 1, ce qui est 4. Maintenant, nous allons finir avec ce fichier, qui est que nous avons 3 plus le nombre de façons à quantité qui est 5 moins le nombre de mots, nombre de cloches, ou la ceinture réelle, ce qui est génial. Donc 5 moins 3 nous donnera 2. Et nous allons regarder pour avoir ici le nombre de façons, ce qui est deux. Donc nous allons mettre à jour ça en trois plus deux à cinq. J' espère que cela a du sens. Nous allons continuer avec ce dernier, qui est quatre. Maintenant, nous avons le montant de quatre factures pour le dîner juste calculé pour ces deux-là parce qu'il n'est pas logique d'avoir ces quatre en 0123 car ils sont plus petits. Donc ce qu'on va faire, c'est prendre ce 4. Nous avons ces quatre, c'est-à-dire le nombre de façons à I plus le nombre de façons au montant moins 12. Alors 4. C' est le montant moins avant Bill. Donc nous allons avoir le nombre de façons à 0. Donc, nous pouvons voir que c'est quatre plus un est cinq. Alors on va prendre ces cinq là. Plus le nombre de façons à la quantité moins bien, qui est aussi à un, parce que le nombre de façons de 5 moins 4 qui est égal à un. Donc, nombre de façons à un, va vérifier qu'il est égal à un. Donc nous allons mettre à jour ça à cinq plus un. On va finir avec six. Alors c'est tout. Fondamentalement, c'est comment nous pouvons obtenir le nombre de façons en utilisant la méthode de programmation dynamique en utilisant cette quantité spécifique. Maintenant, ce que nous allons faire est que ce serait regarder, si c'est exactement ce est le nombre correct de façons. Donc, si vous avez ce montant de 5$ et que nous avons ces quatre types de projet de loi, ce que nous allons faire est de représenter ce fichier en utilisant ces fichiers manuellement. Alors réfléchissons à ça. Nous pouvons avoir quatre ou cinq billets de 1$, ou nous pouvons avoir 2122 doubles plus 1 billet de 1$. Ou nous pouvons aussi avoir deux ou 1$ billets de 2$ et 3$ de billets. Ou on peut aussi en avoir 32. Donc 1 billet de 3$ et 23 billets de dollars et 12 dollars côté affaires. Ou nous pouvons aussi avoir et 1, donc 1, 4 billets de dollars et 1 billet de $1. Donc ces cinq ou nous pouvons aussi avoir les 311, donc les billets de 13 dollars et les billets de 1$. Et si on les compte, 123456. Donc nous finirons avec six façons de représenter ce montant de 5$ en utilisant ces quatre types de personnes. J' espère que cela a du sens. Dans la vidéo suivante, nous allons simplement écrire le pseudocode de ceci et ensuite nous allons l'implémenter dans nos langues. Alors, à vous voir. 12. Nombre de façons Pseudo-Code: Très bien, donc dans cette vidéo, nous allons faire est de résumer nos pensées et d'écrire un pseudocode que nous allons utiliser lorsque nous implémentons cette magnitude, cet algorithme maintenant code. Alors laissez-moi juste supprimer tout ça. Et bien sûr, tout cela aussi. Maintenant, nous pouvons continuer. Maintenant, pensons-y une seconde. Donc ce qu'on a fait, c'est qu'à chaque fois on va utiliser un travail avec une ceinture. Laisse-moi juste écrire les pilules ici vite. Donc, chaque fois que nous allons travailler avec une facture à partir d'ici, nous allons ajouter ou mettre à jour ce nombre de façons. Donc ce qu'on va dire, c'est que si le montant est inférieur à cette cloche, on ne fera rien. On va simplement l'ignorer. Donc, le pseudocode devrait aller comme ça. Donc la première chose qu'on va faire est de vérifier si la quantité est supérieure à la ceinture. Mais c'est le cas. On va continuer. Donc, le montant est supérieur ou égal au bill que nous avons. On va faire quelque chose. Dans ce cas, ce que nous allons faire est de mettre à jour le nombre de façons à cette ceinture, non ? Donc ce que nous allons faire, je suis désolé, à ce montant réel. Donc, ce que nous allons faire est de mettre à jour le nombre de façons. Et ce cas, ce sera au montant réel. On va le mettre à jour. Ce sera égal à deux choses additionnées pour être égal au nombre réel de façons dont nous disposons actuellement. Donc, il sera égal au nombre de façons au montant. Nous pouvons ajouter quelque chose de nouveau, qui est le nombre de façons à la quantité moins un. Donc, il sera égal au nombre de façons à la quantité moins la cloche que nous avons. Maintenant, si vous voulez vous assurer que cet algorithme fonctionne réellement, Faisons cela, par exemple, à quatre heures et vous permet d'utiliser le dernier ici, qui est aussi la cloche pour. Donc, ce que nous allons faire, c'est supposons que nous avons ici pour. Nous en sommes donc maintenant au stade où nous avons le nombre de moyens, qui est de quatre, et nous allons le mettre à jour. Nous allons donc vérifier si le montant est supérieur ou égal à la facture. Et ce cas, le montant est quatre, ce qui est égal à quatre. Donc, cela fonctionne vraiment. Ce que nous allons faire maintenant, c'est de mettre à jour le nombre de façons au montant spécifique. Donc, le nombre de façons à quatre serait égal au nombre de façons à quatre, ce qui est quatre plus le nombre de façons à la quantité moins le déversement. Donc, le nombre de façons au montant de mon sort, qui est 4 moins 4, être égal à 0. Nous allons aller au nombre de façons. Prenez celui-ci ajouté à la 4 nous donnera 5. Donc maintenant, nous pouvons, nous savons que notre formule réelle ici que nous avons générée est réellement vraie et fonctionne exactement bien. Alors c'est tout. Fondamentalement, c'est profond pour la cour. Et en fait, c'est assez simple. Une fois que vous connaissez la méthode, vous pouvez trouver ce pseudocode. J' encourage donc vivement chaque fois que vous résolvez le problème de programmation dynamique à écrire, à l'écrire comme ceci, et à essayer de trouver une solution. Et essayez de trouver la méthode réelle ou la formule réelle qui est la tuberculose utilisée dans ce problème. Donc, comme la première partie du problème, nous ne savions pas que la formule irait juste avec le flux. Donc, par exemple, ici, nous venons de dire qu'au montant 0, nous ne pouvons pas représenter autrement qu' une seule et unique façon qui est de ne pas utiliser d'argent. Maintenant, au montant numéro un, nous pouvons le représenter si nous avons ce $1, mais nous pouvons le représenter par un. Et voici exactement la même chose pour les autres. Et puis ce n'est qu'à ce numéro trois que nous connaissions la formule. Je suis désolé. Ce n'est qu'à la somme du numéro quatre que nous connaissions cette formule. Et nous avons calculé en utilisant cet exemple ici. Donc, commencez toujours par un exemple et essayez de trouver une formule plus tard. Alors c'est tout. Fondamentalement, c'est pour le pseudocode. Lors de la prochaine vidéo, nous allons l'implémenter et notre code réel. Pour te voir, alors. 13. Nombre de méthodes de mise en œuvre Java: Très bien, donc dans cette vidéo, nous allons mettre en œuvre notre fonction, fonction que nous avons créée plus tôt. Et j'ai déjà instancié cette méthode publique statique int nombre de façons. Et on a deux paramètres. Le premier est le montant réel indiqué par N, et le second est les cloches réelles. Donc, c'est un tableau de ceux ici. Donc, ce que nous allons faire est que nous allons créer un nouveau tableau comme avant, comme nous l'avons dit précédemment, qui est d'implémenter ou d'ajouter le nombre de façons à chaque quantité. Alors laissez-moi juste instancié comme moyens il sera égal à 0 et plus un, comme nous l'avons dit. Maintenant, ce que nous allons faire est de désigner ou d'ajouter à la première, comme nous l'avons dit ici est le premier devrait être égal à un. Donc gaspiller à 0 pour être égal à un. Et l'autre sera égal à 0, qui sont le nombre par défaut ou la façon par défaut d'être instanciée dans un tableau. Donc, comme nous l'avons dit, nous en avons déjà un ici. Ce qu'on va faire, c'est passer à travers tout ça ici, c'est de passer un peu à travers tout ce que j'ai construit. Et puis bien sûr, nous allons mettre à jour le nombre de façons ici. Alors revenons en arrière. Maintenant, si nous y réfléchissons, ce que nous allons faire est de payer la boucle for, commençant par 0 jusqu'aux factures de cette longueur et mises à jour. Et le second, nous allons avoir aussi 0. Jusqu' à, je suis désolé, on peut dire que c'est un. Et les deux seront jusqu'aux chemins. Cette longueur de point de taille, je suis désolé, moi et j plus, plus. Ce que nous allons faire au début, c'est vérifier si ce montant est supérieur ou égal à la facture. Et comme nous l'avons dit, ce montant est en fait dans la seconde pour la boucle désignée comme j. Nous pouvons réellement changer ce j en quantité de cela va nous rendre, le rendre plus facile. Laisse-moi juste changer ça très vite. Et puis nous avons le montant aussi. Ce que nous allons faire, c'est vérifier si ce montant est supérieur ou égal à la facture réelle. Et qu'est-ce qu'on a dit ? Nous avons dit que celui-ci serait considéré comme des projets de loi. Et la bande passante réelle de la facture sera au mieux à moi, qui est 0, 1, 2, 3, et 4, ainsi de suite, ainsi de suite. Et ce cas, ce que nous allons faire est de vérifier si le montant est supérieur ou égal à ce qui sera égal aux factures à. Je sais que c'est le cas. Nous devons mettre à jour le nombre de façons. Donc, les façons que je, ou les façons dont ce montant un site sera mis à jour de deux façons au montant plus façons, comme nous l'avons dit, nous allons utiliser la formule, montant moins cela ici. Alors, comment avons-nous eu ce projet de loi ? Ce seront les cloches à I. Donc, dans ce cas, ce que nous avons dit que nous pouvons calculer cela en utilisant des cloches à i. Donc, je vais simplement l'écrire ici à moi et nous avons mis à jour avec succès. Maintenant, ce que nous allons faire est de simplement retourner le nombre de façons à la dernière que nous avons. Donc si on retourne ici, on a juste besoin de celui-là de la sienne. Donc, c'est le nombre de six. Rappelez-vous que le but de ce problème est que si nous avons un montant de $5, combien de façons pouvons-nous représenter ces cinq dollars ? Et nous avons fait tout cela pour trouver la solution finale, c' est-à-dire un six. Alors, comment peut-on prendre ça ? Nous pouvons simplement demander le nombre de moyens à notre montant initial, qui est de cinq. Et ce sera égal à six façons. Donc c'est tout maintenant, c'est ce que nous devrions retourner ici. Donc, après avoir terminé de ces deux pour les boucles imbriquées pour les boucles, nous allons représenter les façons à. Alors c'est tout. Fondamentalement, c'est pour ce problème. Maintenant, si nous allons le tester, nous pouvons simplement utiliser une fonction principale. Donc, je vais simplement créer un critère de fonction principal. Et ce que nous allons faire est d'appeler le nombre de vagues avec n et factures. Et avant cela, nous allons initialiser ça ici. Donc n sera égal à l'échantillon réel, qui est cinq. Et les factures de fin seront égales à ce réel, qui est 12341. Bien. Maintenant, si on veut l'imprimer, laissez-moi juste je suis désolé. Système solaire, point, imprimez juste ici. Et faisons-le. Et comme on peut le voir ici sur ce problème, je vais en avoir six, ce qui est le dernier. Maintenant, si nous voulons retourner tout cela pour l'instant, voir que le dernier ici. Donc, ce que nous allons faire est de retourner une liste. Et si on recommence, on va avoir, je suis désolé, on ne peut pas faire ça. Bien sûr, nous avons juste besoin de créer une boucle for juste ici. Donc, pour moi égal à 0, je suis inférieur à la fin et je passe. Donc je pense que nous avons, nous pouvons imprimer ce que nous avons. Donc, laissez-moi juste créer cet endroit juste ici pour être égal à plusieurs façons. Donc je pense qu'on est bons. Nous pouvons supprimer ceci d'ici. Et bien sûr, nous pouvons imprimer des façons à chacun d'entre eux. Donc, avec ADD, je l'imprime simplement. Et on va l'imprimer. Donc, à un certain espace pourrait continuer. Maintenant, si nous le faisons, nous allons avoir 11 à 35. Si nous allons ici, nous pouvons voir que nous avons 1, 1 à 5. Bien sûr, nous avons oublié le dernier, oublié que c'est et plus un. Maintenant, si on recommence, va en avoir un, 1, 2, 3, 5, 6. Et c'est exactement le même moindre, le tableau exact que nous venons avec cet exemple ici manuellement. Donc c'est tout essentiellement pour la mise en œuvre. C' est ainsi que nous pouvons le mettre en œuvre. Et bien sûr, tu n'as pas besoin de tout ça. Ceci est à des fins de visualisation. Nous avons juste besoin du dernier index ou du dernier élément dans le nombre de façons moins. C' est pour représenter le montant cinq en utilisant le nombre de façons d'utiliser celui-ci ici. Donc c'est tout essentiellement pour cet exemple, voir dans la vidéo suivante. 14. Nombre de façons utilisations en JavaScript: Très bien, donc dans cette vidéo, qui peut implémenter notre fonction en utilisant un JavaScript. Donc, comme nous l'avons dit plus tôt, nous allons l'implémenter en utilisant ce nombre de façons comme un tableau. Et on peut avoir deux choses. Le montant réel, qui est de 5$, et le nombre de lits, ou les types de cloches et un tableau ou une liste. Donc, ce que nous allons faire est simplement de commencer par créer la fonction. Donc, la fonction sera un certain nombre de façons et ce que nous ne faisons pas et qui est le montant. Et puis nous avons également noté par des animaux de compagnie juste ici. Et nous pouvons commencer par créer le tableau et le nommer deux façons d'être égal à un nouveau tableau. Et comme nous l'avons dit, nous avons besoin de n plus un comme une taille. Et on va le remplir avec des zéros. Maintenant, comme nous l'avons dit tout à l'heure. Mais nous devons faire est de sentir ce montant à 0 par nombre de façons, ce qui est un. Donc, pour ce faire, nous allons simplement écrire des moyens à 0 pour être égal à un. Et maintenant, nous pouvons commencer par créer nos deux boucles imbriquées pour. Pour en revenir à cet exemple, nous pouvons voir que nous allons commencer par une boucle for, qui sera pour les cloches. Et puis nous allons mettre à jour le nombre de façons chaque fois que nous examinons un nouveau projet de loi. Donc le premier sera pour la naissance. Car nous avons un montant variable ou le premier sera moins le même en fait, et il sera égal à 0 au début. Et puis ce que nous allons faire, c'est de le mettre à jour. Bien sûr, ce sera jusqu'à et plus un. Et puis on va construire. Donc c'est tout en gros. Et maintenant ce qu'on va faire, je suis désolé, pas avant le n plus un. C' est coupable et la liste. Et dans ce cas, ce que nous allons écrire est la longueur des points de Bills. Donc c'est tout pour la première boucle pour. L' autre serait imbriqué, sera montant variable, qui sera égal à 1. Et ce cas, nous allons regarder jusqu'au montant qui sera égal à moins de et plus un. Maintenant, ce que nous allons faire est de mettre à jour ce montant à chaque fois que nous le traversons. Maintenant, nous pouvons commencer avec la fonction réelle. Donc ce qu'on va dire, c'est que nous allons regarder, regarder ce précis ici. Donc, si le montant est supérieur ou égal au lit, et comme vous l'avez dit, Bill n'est pas un indice comme nous l'avons initialisé plus tôt, c'est en fait le meilleur à cet indice réel. Donc, par exemple, ici à 0, nous allons en obtenir un, celui-ci, nous allons en obtenir 2 et ainsi de suite et ainsi de suite. Donc à mettre en œuvre, mais nous devons faire est de vérifier si le montant est égal ou égal. Cela cloche à cet indice qui sera construit. Maintenant, pour le rendre plus facile, ce que je vais faire est simplement de supprimer tout cela et d'utiliser une autre méthode pour la boucle qui sera construite de factures. Ce que je vais dire, c'est qu'on va laisser Bill. Et maintenant, nous pouvons utiliser cloche et au lieu de cela à cet index. C' est donc une autre fonction. Donc ce que nous disons simplement ici, c'est que la ceinture de naissance est en fait ne pas remplacer les factures, 0 de factures à un et ainsi de suite et ainsi de suite. Donc on n'a plus vraiment besoin de ça. On peut juste l'utiliser comme. Maintenant, ce que nous allons faire est de mettre à jour le nombre de façons au montant spécifique en ajoutant simplement ce nombre de façons au montant spécifique à une nouvelle chose. C' est le nombre de façons au montant moins la facture réelle. C' est donc la formule que nous élaborons ici. Et nous avons déjà dit que ce projet de loi était construit à moi , donc nous sommes bons. C' est la formule qui va se poursuivre. Et maintenant, nous avons juste besoin de retourner le nombre de façons au dernier index. Donc, c'est six. Nous avons juste besoin de retourner le nombre de façons au montant qui est de cinq. Dans ce cas, nous l'avons désigné comme n. Donc nous allons simplement retourner des moyens. Et maintenant, on est bons. Je pense qu'on peut travailler avec ça. C' est notre formule. Maintenant, si nous voulons l'utiliser ou tester, nous pouvons le faire ici. Donc, nous allons indiquer, laissez n égal à cinq et conduire à une zone de 12345. Maintenant, ce que nous allons faire est d'imprimer le nombre de façons que nous pouvons créer avec ce montant et est rempli. Donc maintenant, si nous avons réellement testé, accord, donc ici nous avons consulté branche amygdalaire. Et dans ce cas, ce que je vais me diriger vers CMD et ce que je vais utiliser pour exécuter le JavaScript. Je vais utiliser le serveur NodeJS. Si vous ne l'avez pas encore installé. Vous pouvez aller de l'avant et l'installer dès maintenant. Peut simplement se diriger vers la note. Et comme nous l'avons dit, peut le télécharger à partir d'ici. Alors allez-y et téléchargez-le. Ensuite, ce que vous faites est de vous diriger vers votre dynamique ou vers votre répertoire. Dans ce cas, je vais le nommer programmation dynamique JavaScript. Et dans cette programmation dynamique, je vais avoir ce nombre de façons que j'ai créé plus tôt. Et vous pouvez simplement l'exécuter de la sienne. Donc, je vais utiliser ces nœuds et écrire simplement nombre de façons, montant dot js. Et je vais en avoir six comme nombre de façons. Souviens-toi qu'on voulait juste avoir ce dernier. Maintenant, si nous voulons visualiser ce nombre de façons, moins. Donc, en d'autres termes, nous voulons visualiser cette liste telle que 1, 2, 3, 1, 1, 2, 3, 5, 6. Gardez à l'esprit que nous devrions retourner autre chose. Donc, ici, nous revenons des moyens de rivaliser avec des moyens écrits. Maintenant, si on recommence, on aura moins de, c'est 112357. Maintenant, gardez à l'esprit que nous n'avons besoin que de la dernière qui est de représenter ce montant de $5 avec ces quatre types de ceinture. Nous avons donc six façons de le faire. Donc c'est ça fondamentalement c'est tout pour ce problème. se voit dans la vidéo suivante. 15. Nombre de façons utilisations Python: Très bien, donc dans cette vidéo, nous allons continuer ou fonction incrémentielle en utilisant Python. Donc, comme nous l' avons dit plus tôt, nous avons le nombre de façons qui est une liste que nous allons stocker. Le nombre de façons pour chaque montant spécifique jusqu'au montant final ou le montant que nous voulons. Alors faites cela, commençons par créer une liste en Python. Allons donc à notre Visual Studio. Et dans ce cas, je vais faire est de créer une liste. Je vais le nommer. Et ce sera simplement liste, comme ceci ou je peux juste le faire entre crochets. Et dans ce cas, ce que je vais faire est de remplir cette liste jusqu'à la fin, juste ici. Donc, tout d'abord, définissons nos deux paramètres. Donc, le premier est et il sera égal à cinq. Et le second sera construit qui est aussi une liste. Et il sera égal à 1, 2, 3 et 4. Et dans ce cas, ce que je vais faire est de créer cette liste L ou LastName. Il pèse en fait puisque nous allons l'utiliser comme déchets. Et bien sûr, je vais le remplir avec des zéros. Donc, pour moi dans la gamme de peut-être n plus un, allons-nous faire est d'ajouter à ce 0. déchets qui ajoutent. Et je vais ajouter 0 ici. Et bien sûr, si nous l' imprimons, nous allons faire remplir notre liste avec des zéros. Donc, si nous allons ici et à droite, par le nombre de façons nous allons obtenir 000, 000, 000, et ça va rendre la liste vide. Donc, nous avons 012345 éléments ou cinq indices, qui sont six depuis que nous avons commencé avec 0. Maintenant, ce que nous allons faire est de troisième, le premier était un avec un. Donc ce que je vais faire, c'est simplement dire qu'à 0, je vais le remplir avec un. Je vais le faire à nouveau. On va en avoir un ici. Maintenant, nous pouvons commencer par notre fonction. Nous avons tout prêt pour nous. Nous pouvons résoudre nos boucles for. Puisque nous avons cette fonction, ce que nous allons faire est de parcourir tous les éléments ou la totalité de la fin des numéros ici dans les cloches, puis faire la même chose pour le nombre de façons et mis à jour. Donc, je vais supprimer la marque et je vais continuer à créer une build à partir des factures. Alors maintenant que nous pouvons continuer, nous pouvons créer le montant dès maintenant pour ces moyens spécifiques. Donc ce que nous allons faire, c'est que nous allons commencer d'un jusqu'au n plus 1. Et comment nous pouvons faire ça, nous pouvons utiliser la portée d'un jusqu'à la fin plus un. Et bien sûr, on va ouvrir ce regard. Et nous allons vérifier, comme nous l'avons dit précédemment, si le montant est supérieur à la facture, nous allons mettre à jour le nombre de façons. Alors, comment faites-vous ça ? Nous vérifions simplement si la quantité est supérieure ou égale aux cloches ou si la tension est créée. Si c'est le cas, nous allons devoir mettre à jour le nombre de façons. Donc, un certain nombre de façons au montant sera égal, comme nous l'avons dit, utilisant la formule que nous avons générée dans le pseudocode, nombre de façons égal au nombre de façons plus nombre de façons à la quantité moins minus1. Donc, dans ce cas, nombre de façons Au montant égal deux façons à quantité plus moyens à la quantité moins la ceinture. Maintenant, gardez à l'esprit que ce projet de loi est en fait que nous utilisons construit et construit. Et cela nous donnera des cloches à 0, cloches à moi et ainsi de suite et ainsi de suite. Donc, c'est peut-être juste une solution de raccourci pour la boucle for-au lieu de l'avoir dans la portée et l'accès et les cloches à i pour des indices spécifiques, nous pouvons utiliser la facture et les cloches. Alors c'est tout. Fondamentalement, c'est comment nous pouvons le mettre à jour. Maintenant, ce que nous allons faire, c'est simplement imprimer ici. Donc si nous imprimons des façons, et maintenant revenons ici. Et comme vous pouvez le voir, nous avons obtenu le même résultat exact que nous attendions un, 1, 2, 3, 5 et 6. Donc voici celui-ci, 1, 2, 3, 5 et 6. Nous savons donc que notre programme fonctionne. Maintenant, ce que nous voulons faire ou quel était notre objectif, générer le nombre de façons que nous pouvons spécifier ou nous pouvons créer $5 en échange $5 en supposant que nous n'avons que ces quatre types de factures. Alors comment on fait ça ? Nous retournons simplement le dernier parce que le dernier élément de la liste indique qu'il est pour le montant de 5. Alors c'est tout. Fondamentalement, nous venons de retourner les chemins à. Et maintenant, si nous revenons en arrière et que nous l'exécutons à nouveau, nous allons en obtenir six indiquant que nous avons six façons de mettre en œuvre ou à MD oui, mettre en œuvre cette fonction ou d'avoir 5$ de ces quatre types de factures. Donc, c'est tout essentiellement pour l'implémentation Python. Cela dit, c'est la fin de cette vidéo. se voit dans la prochaine. 16. Problème de Knapsack: Très bien, donc dans cette vidéo, ce que nous allons faire est de passer en revue l'un des problèmes les plus célèbres de la programmation dynamique. Et c'est connu comme le problème du sac à dos. Et ce problème a en fait deux versions de celui-ci. Le premier est la version fractionnelle et l'autre est la discrète. Ce que nous allons faire, c'est passer par un exemple. Et nous allons discuter de ces deux versions et nous allons en apprendre davantage sur l'une d'entre elles. Et il est en fait résolu en utilisant la programmation dynamique. Donc, pour y aller, Commençons par l'exemple. L' idée de ce problème est que vous avez certains articles ou produits, et chacun de ces articles a un poids et une valeur. Supposons donc que nous avons quatre éléments. Le premier, donc je les écris simplement ici. Donc le premier sera un poids cinq. Le second sera de poids pour le troisième sera attendu trois, et le dernier sera de poids aussi. Donc nous y voilà. Nous avons quatre produits ayant toutes ces façons. Maintenant, nous devons ajouter la quantité ou la valeur de ces produits. Donc, le premier sera une valeur 28. Donc, 28$, le second sera une valeur 20. Le troisième sera à 18 ans, et le dernier sera à 11 ans. Donc 18 et 11. Maintenant, le vrai problème est que vous allez recevoir ces articles avec un poids spécifique que vous pouvez tenir. Donc, par exemple, supposons que vous avez un sac. Et dans ce sac, vous ne pouvez supporter que 10 en poids. Donc, vous devez obtenir tous ces produits et ajouter jusqu'à 10. Donc supposons que vous avez ici sac. Et dans ce sac, vous ne pouvez en tenir que dix. Donc maintenant, la version fractionnelle de ce problème peut réellement être résolue en utilisant des algorithmes avides. Et dans ce cas, voyons ça ici. Donc, ce que nous allons faire, c'est que nous pouvons prendre une fraction de ces articles en poids. Donc, au lieu de prendre l'article entier, donc nous avons ici le poids car nous pouvons réellement prendre des fractions de cela. Donc, par exemple, si nous voulons avoir ceci à partir d'ici, donc nous en avons 10, ce que nous allons faire est de diviser ces montants sur les valeurs et de prendre le maximum de ceux-ci. Par exemple, si vous avez 28 sur 5, nous allons obtenir quelque chose comme 5.6. Laisse-moi l'écrire ici. Le second sera cinq. Le troisième sera 18 sur trois, ce qui sera six. Et le dernier sera en fait 5.5. Maintenant, nous pouvons toujours le résoudre en utilisant le montant maximum. Donc, pour remplir ce poids de 10, ce que nous allons faire, c'est de prendre tous ces trois d'ici. Donc nous allons prendre ces trois car ils ont la valeur la plus élevée en ce qui concerne la quantité sur le poids. Et cette affaire, nous allons prendre tout ça, donc somme jusqu'à 18$. Maintenant, nous allons continuer en prenant celui-ci qui est cinq. Donc, si nous retournons ici et ajoutons ces cinq, qui seront d'environ 28$. Et parce qu'il a la valeur la plus élevée. Rappelez-vous maintenant que le but de ce problème est de le résoudre ou d'avoir un poids de dix avec un montant maximum d'argent. Maintenant, dans ce cas, nous avons 18 plus 28. Et enfin, ce que nous allons faire, c'est prendre ce 5.5. Donc si vous vous souvenez d'ici, nous avons 532. Maintenant, si on prend 11, on va finir avec quelque chose comme 11 ou 18 plus 28 plus 11. Donc, le poids est de trois plus cinq plus deux, et il est égal à 10. Maintenant, supposons qu'on n'a pas un poids de dix. Donc, au lieu d'avoir un poids de 10, nous allons avoir un poids de neuf dans cette affaire. Et si nous voulons résoudre ce problème avec un poids de neuf, nous allons finir avec la même chose qu'avant. Cependant, je ne veux pas avoir ici deux fait deux plus trois plus cinq est neuf. Dans ce cas. Quand nous arriverons à cette position, ce que nous allons faire, c'est prendre une fraction de ces deux. Au lieu de prendre Net dans son ensemble, nous pouvons en prendre une fraction. Donc on va prendre une fraction de deux. Donc, nous ne prendrons pas tout l'outil qui va prendre une fraction, ce qui est que vous pouvez en prendre une. Et ce cas, la valeur sera 5.5. Donc c'est 11 sur 2, ce qui est 525. Maintenant, la quantité entière ou le poids total est de 3 plus 5 plus 1, ce qui est. En fait égal à neuf. Et dans ce cas, nous pouvons utiliser un algorithme gourmand qui recherche quelque chose ou la valeur, la plus grande valeur que nous avons. Donc, par exemple, ici, nous en avons six, Good Prenez tous ces. Alors on va vérifier si on a encore un endroit. Bien sûr, nous allons avoir une place puisque nous n'avons ajouté que le poids de trois. Donc neuf moins trois, il nous reste six. On va prendre tout ça. Alors il ne nous reste qu'un seul. Nous allons aller chercher entre 55.55.5 est plus grand et nous allons le prendre comme le plus grand. Et bien sûr, nous pouvons en prendre une fraction, pas la totalité. C' est donc l'idée d'un sac à dos fractionné. Et c'est en fait, cela ne fonctionne pas si nous en avons un discret. Imaginez qu'on ait un sac à dos discret. Et dans ce cas, nous pouvons travailler avec elle parce qu'une fois que nous atteignons cette étape ici, et nous en avons 35, alors nous en avons encore une. Et cette affaire, on ne peut pas diviser celle-ci ici. Donc, la solution optimale en fait brume d'utiliser quatre plus cinq et attendre. Et bien sûr, nous allons finir avec 48 au lieu de 18 plus 28. Dans ce cas. Comme nous pouvons le voir, la version discrète de ce problème devra être utilisée pour avoir une programmation dynamique comme solution pour cela. Et cela dit essentiellement pour le sac à dos fractionnel, vous pouvez toujours utiliser l'algorithme gourmand avec, mais nous ne traitons pas le trait maintenant nous voulons simplement travailler avec la version discrète où nous avons la programmation dynamique. Laissez-moi juste supprimer tout cela d'ici. Maintenant, pour la version discrète, nous avons aussi deux versions ici. Nous avons la quantité illimitée et la quantité limitée. Donc, ici quand il est connu comme sans répétition. Maintenant, parlons-en une seconde. Pour la quantité illimitée, ils signifient que nous avons une quantité illimitée de cet article, cet article, cet article et cet article. Cependant, jusqu'à quantité limitée, qui est sans répétition, nous n'avons qu'un seul de cet article, E1, produit de cet article, l' un de ceux-ci et l'un de ceux-ci. Donc on ne peut pas vraiment utiliser ça plus d'une fois. Maintenant, ce que nous allons faire, c'est que nous allons avoir un exemple et passer par la quantité illimitée à côté de la quantité limitée ou sans répétition. Alors réfléchissons-y une seconde. Si nous avons cet exemple ici, laissez-moi vous apprendre. Et laissez-moi vraiment prendre toutes ces choses et les rendre plus petits et venir ici. Et je vais faire exactement la même chose pour ça aussi. Et je les ai mis ici. Maintenant, nous pouvons continuer notre travail. Maintenant, imaginons que nous avons illimité ou sans la pétition, celui qui était assis avec la, sans la répétition. Donc sans répétition ce que nous allons faire. Donc ici, nous avons Sans, nous allons prendre ces trois, qui est le plus élevé. Encore une fois, prenez ces trois. Maintenant rappelez-vous que nous avons besoin d'un poids de dix. Donc nous avons ce trois plus celui-là, plus celui-ci un des cinq. Maintenant, si nous voulons ajouter tous ces, donc ici nous avons 18.11.28. Dans ce cas, nous allons finir avec 57$ comme valeur finale. Et ce sera le plus élevé pour le sans la répétition LFO. Et il suffit de calculer ce 13 plus deux plus cinq, ce qui est égal à 10. Donc nous sommes bons maintenant avec une quantité illimitée, mais nous pouvons faire est, alors laissez-moi juste changer la couleur ici. Donc, ici, nous avons l'illimité. Jetons ça un coup d'oeil. Alors imaginez que nous avons plus de 13, donc nous avons 3 plus. Peut également utiliser trois autres, ce qui va ajouter jusqu'à six. Et nous pouvons aussi utiliser deux deux dans ce cas. Donc maintenant, si nous le calculons, alors nous avons trois plus trois, donc trois, c'est 18$. Ici aussi 18, nous avons 11 et 11. Donc, comme vous pouvez le voir, cela se transformera en 58$, ce qui sera meilleur que l'ancien si nous avons une quantité illimitée. Et en supposant que nous ayons le même nombre ou les mêmes poids et les mêmes montants. Donc, dans ce cas, comme vous pouvez le voir, il est préférable d'utiliser la quantité illimitée ou la répétition de largeur juste ici. Ce sont donc les deux versions que nous avons dans la version discrète du problème de knapsack. Et on va se concentrer sur eux. Et nous pouvons également les résoudre en utilisant la programmation dynamique et les deux prochaines vidéos. Alors, à vous voir. 17. Retour avec répétitions: Très bien, donc dans cette vidéo, nous allons nous concentrer sur la discrète avec une quantité illimitée de version du problème de sac à dos. Donc, pour ce faire, laissez-moi juste supprimer tout cela d'ici. Et il est aussi un indicateur. Laisse-moi prendre tout ça, les rendre plus petits et les ranger ici. Et je fais exactement la même chose. Ce genre me laisse juste les prendre et les placer ici. Donc maintenant, nous pouvons commencer avec notre problème de sac à dos avec la répétition avec une quantité illimitée ou des articles. Donc, dans ce cas, si nous voulons regarder, regarder, de cette façon, nous allons finir avec quelque chose qui est égal. Nous avons donc 58$ au total. Alors gardez ce numéro à l'esprit pour les données. Maintenant, ce que nous allons faire est que nous allons utiliser un tableau ou une liste pour essayer de résoudre ce problème et trouver une solution appropriée en utilisant la programmation dynamique. Donc, ce que nous allons faire, c'est que nous allons prendre le montant ou le poids maximum que nous avons, qui est 10, et créer une liste, dix plus un comme taille. Laisse-moi juste créer, et voici notre liste. Et ce que nous allons faire, c'est que nous allons mettre à jour toutes ces choses, à chaque fois que nous les traversons. Maintenant, réfléchissons-y. Ce que nous voulons faire, c'est que nous pouvons, nous devons avoir le maximum d'argent en utilisant ces, supposant que nous avons 10 comme poids. Donc nous allons utiliser tout ça. Nous avons une quantité limitée et nous allons utiliser montant illimité et nous devons trouver le montant maximum d'argent. Commençons par 01. Aussi haut que nous pouvons le voir, nous n'avons rien et nous n'utilisons pas fractionnaire, donc nous pouvons diviser ceci. Donc ce que nous allons faire, c'est simplement écrire 00 ici. Laisse-moi changer la couleur. Maintenant, nous en avons deux et comme nous pouvons le voir, nous pouvons nous en servir, et le coût sera de $11. Maintenant rappelez-vous que nous devons maximiser discuté pour l'instant, nous ne pouvons pas utiliser autre chose que ce 11 pour les deux. Maintenant, si nous allons jusqu'à 2, 3, et regardons les trois. Nous avons 18$, ce qui est plus grand que 11, donc nous pouvons travailler avec 18 ici. Excusez-moi, laissez-moi l'écrire mieux. Nous en avons donc trois, ce qui sera un total de 18. Maintenant, si nous allons à l'avant, comme nous pouvons le voir pour la, pour une, nous avons ici la valeur de 20. Maintenant, dans ce cas, vingt plus grands que 11 et 18. Donc on va écrire 20 ici. Maintenant, si nous passons aux cinq, nous avons en fait plus d'une option. Dans ce cas, regardons. Nous pouvons en avoir deux et y ajouter un trois, qui sera 11 plus 18, ce qui sera en fait 29. Ou, je suis désolé, ou si nous en avons trois et nous y ajoutons, deux obtiendront également le résultat de 29. Donc ce que nous allons faire, c'est simplement écrire ici 29. Donc gardez à l'esprit ce que nous avons fait est en fait d'utiliser soit 2 plus 3 ou 3 plus 2. Et on va en avoir 29. Maintenant que le sexe, la valeur totale ou la valeur maximale que nous pouvons obtenir est 3600. Expliquez-le dans une minute. Mile, réfléchis comme ça. Vous pouvez également avoir toutes ces informations ici. Alors pensons à ce cinq et à ce cinq. Gardez à l'esprit que ce fichier est la solution optimale pour la quantité maximale, qui est de 29. Pensez-y comme si nous avions un cinq et nous allons en ajouter un pour en faire un poids de six. Et ce cas, il n'y a rien que nous puissions ajouter pour faire de cette façon plus de 29. Et dans ce cas, nous allons regarder quatre. Alors regardons quatre. Si nous en avons 20 ici, que pouvons-nous ajouter d'ici pour le rendre plus grand que 29 ? Dans ce cas, si nous le regardons, nous pouvons ajouter deux d'ici, qui a la valeur de 11. Donc 20 plus 11, il sera égal à 31 nazis. Maintenant, pensons à ce voyage. Donc nous en avons trois. Que peut-on ajouter à trois ? Avoir des relations sexuelles comme un montant était ou comme un poids. Dans ce cas, ce que nous pouvons ajouter trois autres, qui totalisera également 18$. Donc 18 plus 18 être 36, ce qui est plus grand que 31. Donc nous allons supprimer ceci et vous allez utiliser 36. Maintenant, nous allons aussi revenir à cela aussi. Nous allons donc nous poser la même question. Que pouvons-nous ajouter à, à, pour en faire six ? Et heureusement, nous avons ces quatre ici, qui est la valeur de 20. Donc, si nous voulons l'utiliser, nous pouvons ajouter la valeur de deux, qui est 11 plus 20, pour nous donner aussi 31, ce qui n'est pas la valeur optimale, ont déjà une valeur optimale qui est 36. C' est ainsi que nous pouvons calculer cela. Passons à la septième, et comme on peut le voir, on en a 36, mais on ne peut rien y ajouter. Donc si on veut l'utiliser ici, on peut. Laisse-moi essayer ça pour l'instant, 36. Si nous revenons à ce dossier, si nous en avons 29 et nous y ajoutons deux, donc cinq plus deux pour nous en donner sept. Donc 2029 plus 11, il nous donnera en fait 40, ce qui est plus grand que 36. Donc on va l'utiliser. Et bien sûr, nous pouvons aller jusqu'au 4, 3 et 2, mais c'est la solution optimale et vous pouvez l'essayer par vous-même. Passons maintenant à l'aide. Cette aide, la solution optimale sera 47 et il sera en fait 36 plus celui-ci des deux qui est 11, donc 36 plus 11 est 47. Ensuite, nous allons avoir la solution optimale pour le poids de neuf, soit 454. Et enfin 58 pour le dernier, qui utilise réellement ce bord d'ici, la solution optimale de huit plus en y ajoutant ces deux d'ici, qui a une valeur de 11, donc 47 plus 11, qui nous donnera 58. Et comme vous pouvez le voir, nous avons obtenu le même résultat exact qu'avant. Alors c'est tout. C' est ainsi que nous pouvons obtenir la quantité maximale en utilisant la méthode de programmation dynamique. Je sais que si vous allez résoudre le problème du sac à dos, et si elle a un petit problème, peut le résoudre juste par la tête. Tu n'as pas vraiment besoin de celui-là. Mais que se passe-t-il si vous avez peut-être 10 ou 15 produits ou articles ici ? Vous ne pouvez pas vraiment y penser et trouver la bonne solution. C' est donc la bonne façon. C' est ainsi que nous pouvons le calculer en utilisant la solution optimale que nous pouvons obtenir. Donc c'est tout pour cette vidéo. Et le prochain, nous allons écrire un pseudocode. Et nous allons trouver une formule que nous avons utilisée ici. Cela étant dit, c'est la fin de cette vidéo. se voit dans la prochaine. 18. Prise avec Pseudo-Code: Bon, maintenant que nous avons une idée sur le problème du sac à dos avec la répétition, Prenons ou venons avec une formule réelle ou une solution à ce problème sous une forme de pseudocode. Maintenant, dans ce cas, ce que nous allons faire, c'est d'abord définir nos paramètres. Donc, ce que nous allons obtenir en fait, c'est trois ou quatre paramètres. Je vais en parler. Donc le premier sera en fait le poids dont nous allons avoir besoin. Donc, ce que nous allons faire est de taper ici w. donc c'est le premier paramètre. Le second sera les valeurs réelles telles que 54, je suis désolé, comme 282809, 11. Donc ce sera un tableau. Donc, dans ce cas, je vais juste les désigner par Val. Donc c'est une liste ou un tableau. Maintenant, ce troisième sera le poids réel. Donc, je vais juste essayer de largeur. Et bien sûr, ce sera un autre tableau de liste. Et bien sûr, le dernier serait la taille de la longueur de ce fichier et les poids. Donc je vais juste indiquer par N. Ok, alors qu'est-ce que ça signifie ? Donc Val et les vagues devraient être les mêmes. Par exemple, val à 0. Nous avons, dans cet exemple spécifique, nous aurons la valeur 28 et attend à 0. Nous aurons la valeur de cinq. C' est ainsi que nous pouvons y accéder puisqu'ils ont le même index. Donc 28, 524, 18, 3, 11 et 2. Donc, c'est un, fondamentalement c'est ce que nous allons obtenir maintenant, pensons-y d'une manière dynamique de programmation. Donc la première chose que nous allons faire est de créer ce tableau, non ? Et le semi est en fait de taille w plus un, comme nous l'avons dit. Donc, j'ai simplement désigné comme un signe qui est la capacité maximale que nous pouvons obtenir. Donc, notre tableau sera MA, et bien sûr sa taille devrait être. Donc c'est le tableau ou la liste et de taille Tune soit ce poids plus 1. Donc w plus un. Rappelez-vous maintenant que lorsque nous avions le timbre comme poids, nous avons créé ce tableau de longueur dix plus un. Donc c'est la longueur 11, tout le chemin de l'index 1, index 0, je suis désolé, jusqu'à la fin de l'index 10. Maintenant, c'est notre tableau appelé MA. Maintenant, nous pouvons commencer à formuler ou à passer par deux boucles imbriquées pour et mettre à jour ces valeurs ici. Laisse-moi juste énumérer certains d'entre eux. Supprimez ceci. Je vais prendre tout ça et les rendre plus petits. Je pense qu'on n'en a pas vraiment besoin pour l'instant. Je vais simplement les ajouter ici. Maintenant, la seconde sera celle-ci. Donc c'est la première chose qu'on va faire et notre code. Rappelez-vous maintenant que ce que nous visons à faire est de créer une liste ou un tableau contenant les valeurs optimales pour chaque poids spécifique. Par exemple, la valeur optimale ici pour ce poids de 0 est 0. Le taux optimal d'un est 0. Le poids optimal de 2 est de 11, et ainsi de suite et ainsi de suite. Donc, bien sûr, quand nous en arriverons à ce point, et ce sont les six. Et nous avons utilisé l'écran d'ici, nous utilisons 18 plus un autre 3, qui est 36. Nous savions que c'est le moyen optimal que nous pouvons obtenir pour cette valeur de trois. Et bien sûr, c'est très important parce que les valeurs dépendent les unes des autres. Donc, par exemple, si ce n'est pas le moyen optimal pour cette valeur de trois, et nous l'avons utilisé dans le sexe que, par conséquent, ce six n'est pas le moyen optimal aussi. Donc, cela dit, c'est l'idée derrière elle. Nous visons juste à faire le moyen optimal pour chaque poids jusqu'à la fin. Et bien sûr, nous finirons avec un moyen optimal aussi. Donc, ce que nous allons faire maintenant, c'est de commencer avec nos boucles for. Le premier, on passera de 0 jusqu'à la fin de ce poids. Donc ce sera de 0 à W. Maintenant, bien sûr, c'est le capital W. Et alors ce que nous allons faire est d'aller et un autre pour boucle. Et cette formule sera une valeur j. Maintenant ce j va aller de 0 jusqu'à la fin. Alors je vais en parler dans une seconde. Maintenant, si vous y pensez, ce que nous faisons, c'est que nous sommes en train de boucler. Tout ça, un par un. Et à chaque fois, par exemple, si vous êtes deux, ce que nous allons faire, c'est d'examiner toutes ces choses ici. Donc nous allons regarder à travers les 5, 4, 3, et 2. Donc ces poids devraient, nous devrions y accéder. Et nous pouvons également accéder à ces valeurs en utilisant le valide dont nous avons parlé plus tôt. Alors c'est tout. Fondamentalement, nous avons notre Val et les déchets et nous pouvons y accéder à l'intérieur de ces deux boucles. Et ce que nous allons faire est de vérifier si ce poids à un indice spécifique de j, non ? Donc membre, rappelez-vous que nous sommes en train de boucler, en boucle à travers cela avec j. Donc de cette façon, à un index spécifique est inférieur ou égal aux poids réels que nous traversons, alors nous pouvons faire quelque chose. Sinon nous, ça n'a pas vraiment d'importance et n'a pas de sens de changer. Donc, par exemple, passons par l'un des exemples. Supposons que nous soyons à un seul ici. Ce que nous allons faire, c'est de parcourir tout ça. Maintenant, ce que nous allons dire, c'est que si ces cinq sont inférieurs ou égaux à un, alors nous allons faire quelque chose. Maintenant. Rappelons que cinq n'est pas supérieur et pas inférieur à un. Donc, ce que nous allons faire est simplement de l'ignorer, puisque nous pouvons représenter la dissuade S1 en utilisant ces cinq. Ce que tu vas faire, c'est passer à travers tout ça jusqu'à présent, 432. Et nous allons voir qu'ils ne sont pas moins d'un. Donc, bien sûr, nous allons l'ignorer, donc le 0 reste tel qu'ils sont. Ce que nous allons faire, c'est passer par un autre exemple. Maintenant, nous sommes à moi égal à deux dans ce cas, c'est moi. Alors demandez-vous si ces deux sont moins de cinq, je suis désolé, si ces deux sont plus grands que cinq, ça ne fera rien. Ce deux est supérieur à quatre ou trois. Non. Alors est ce deux est supérieur ou égal à 2. Oui. Donc on peut utiliser ça pour ici. Donc, nous ajoutons la valeur que nous avons ici, qui était 0 en fait ajouté à cette valeur à partir d'ici. Alors c'est tout. Fondamentalement, c'est comme ça que nous pouvons le faire. Maintenant, essayons-le avec le dernier exemple. Donc, par exemple, supposons que nous soyons à quatre ans. Demandons-nous donc c'est 4 plus grand que 5 ? Non, on ne peut pas l'utiliser. Est pour plus de quatre, supérieur ou égal En fait, oui, c'est. Donc ce qu'on va faire, c'est prendre ce 4 et y accéder. Bien sûr, en utilisant le, donc par exemple, nous sommes ici pour ce que nous allons faire est d'écrire, laissez-moi écrire la formule. Donc ce que nous allons obtenir en fait, c'est que nous allons mettre à jour cette valeur à quatre heures en autre chose. C' est MA, au poids que nous avions. Donc c'est la façon dont nous travaillons avec moins le poids que nous allons prendre. Et dans ce cas, c'est avant. Bien sûr, ce n'est pas une formule définie. Nous allons avoir besoin d'ajouter cette valeur ici à partir de la valeur par défaut que nous obtenons. Donc il est plus 20, je suis un f à 0 en fait. Donc c'est 0 MA à 0. On va le regarder et c'est 0. Donc 0 plus 20, on va en avoir 20. Maintenant, pensons-y une seconde. Qu' est-ce qu'on a fait ici ? Eh bien, si vous l'avez fait, c'est que nous sommes au poids pour l'instant, rappelez-vous que vous avez besoin d'un poids de quatre. Et bien sûr, si vous voulez obtenir le poids de quatre à partir d'ici, vous devez avoir 0 poids et ajouter ces quatre pour être un 284, non ? Donc, par exemple, si vous voulez ajouter le poids de trois, vous allez devoir avoir un poids d'un, puis ajouter trois, nous avons ce poids de quatre, non ? Alors c'est tout. Fondamentalement, c'est comment vous pouvez le calculer. Pensez-y que si vous voulez ajouter ce poids de quatre, où préféreriez-vous le faisceau avant d'arriver à cette position juste ici ? Et en fait, la, la solution réelle est assez simple. Vous devriez être à l'index 0. Ajoutez-y ces quatre. D' ici, on va l'atteindre. C' est pourquoi nous ajoutons cette valeur à partir d'ici dans celle d'ici. Et puis on va l'avoir à 20 h, juste ici. Donc c'est l'idée derrière elle, c' est comment nous pouvons nous rassembler. Maintenant, pensons à une autre, une autre boucle. Supposons maintenant que nous en soyons à trois ans. Nous allons nous demander si quatre est supérieur ou égal à trois. Oui, ça l'est. Ce qu'on va faire, c'est prendre MA à quatre heures. On va le mettre à jour. Bien sûr, nous ne le ferons pas si c'est moins que 20 d'ici. Bien sûr. Donc nous avons ici nos 20. Laisse-moi juste le montrer ici. Donc, ici, nous avons déjà eu 0, non ? Maintenant, on y pense comme il est 20 plus grand que 0. Oui, nous devrions le mettre à jour. Donc ici, nous en avons 20. Maintenant, si nous sommes à cet arbre, ce que vous allez faire, c'est de nous demander, est-ce plus grand que quatre ? Je suis désolé, c'est génial pour plus ou moins de trois. Oui, ça l'est. On peut le mettre à jour. Maintenant, nous devons vérifier la valeur. Si elle est supérieure à 20, alors nous pouvons mettre à jour celui-ci. Si ce n'est pas le cas, alors il n'est pas logique de mettre à jour. Maintenant regardons ça. Qu' est-ce qu'on va faire ? Donc, nous disons que MA à quatre devrait être égal à MA à ce quatre moins trois plus la valeur que nous obtenons d'ici, qui est 18. Maintenant, la valeur à M, un quatre moins trois, qui est un 01, je suis désolé, est aussi 0. Donc, nous allons ajouter 0 plus 8, ce qui est égal à A1. Maintenant, on va vérifier si 20, moins de 18 ans. Non, ce n'est pas le cas. Donc on va garder la sueur 20 et ignorer celle-ci. Et bien sûr, nous allons continuer. Donc il nous reste celui-là. Et bien sûr, nous allons dire que MA à, pour peut-être égal à MA à 4 moins 2 plus la valeur que nous avions un qui est 11. D' accord, alors c'est le cas ? Donc je suis un à deux, c'est 11. Donc, nous allons obtenir 11 plus 11, ce qui est en fait 22, qui est aussi supérieur à ce 20. Donc nous pouvons le mettre à jour ici. Alors c'est tout. Fondamentalement, c'est toute l'idée à ce sujet. C' est l'idée générale à propos de ce problème de sac à dos. Maintenant, ce que nous allons faire est simplement de le rendre meilleur et le code absolu. Donc, nous avons déjà cette formule ici, mais heureux, juste supprimé et écrire à nouveau. Et belle façon. Donc ce qu'on va dire, c'est qu'on va parcourir tous les poids. Ensuite, nous allons parcourir tous les déchets d' ici pour chaque façon que nous avons dans notre tableau. Et nous allons vérifier si le poids d'ici à cet indice spécifique. Donc poids et j que ou égal à la façon dont nous avons ici, qui est moi en fait. Si c'est le cas, alors nous allons mettre à jour quelque chose. Mais nous allons mettre à jour est en fait la façon dont nous avons MDMA pour le créer. Donc MA et cet indice spécifique, qui est I, devraient être égaux au maximum entre deux choses. Donc, il devrait être égal au maximum entre le premier qui est MA à i. Donc c'est le maximum entre lui-même ou le MA à I moins les poids à j. Bien sûr, après avoir terminé de cela, nous allons arriver à ajouter la valeur qui est dans le tableau val à partir d'ici. Donc, nous allons ajouter une valeur à j. Maintenant, réfléchissons une seconde. Dans ce cas, ce que nous allons dire, c'est que nous le sommes, si nous y sommes pour, par exemple, et nous sommes ici à ce quatre. Donc quatre est supérieur ou égal à quatre. C' est ça avec un J, qui est la façon dont nous accédons au score, est 4. Celle-ci est supérieure ou égale aux poids à j. Oui, nous allons les mettre à jour a à quatre. Dans ce cas, le MA à quatre, il devrait être égal à la valeur réelle et le MA à quatre, ou le MA à quatre moins quatre, qui est 0, plus la valeur à cet indice spécifique, qui est 20. Alors c'est tout. Fondamentalement, c'est la formule. Et bien sûr, vous devriez toujours commencer par penser au tableau que vous avez conçu auparavant, puis trouver une solution réelle. J' ai essayé de réfléchir à la façon dont nous utilisons les valeurs d'avant et nos indices réels ici. Et en fait, vous devez vraiment passer par tous les exemples pour voir le modèle réel de cette formule. Cela étant dit, c'est la fin de cette vidéo. On se voit. 19. Prise avec répétition Java: Oh, ok, donc dans cette vidéo, nous allons résoudre le problème du sac à dos avec la répétition. Donc, la première chose que je vais faire est de créer une fonction. Ce sera donc public, statique. Et je vais l'appeler sac à dos. Ensuite, nous allons obtenir les paramètres pour le premier devrait être le poids, comme nous l'avons dit, le second devrait être la longueur des valeurs et des éléments. Ensuite, nous avons la valeur, les valeurs, et ensuite nous avons le poids. Maintenant, ouvrons ça. Et maintenant, ce que nous allons faire est de créer notre liste actuelle. C' est le, MA. Nous allons le définir comme un tableau. Dans ce cas, une intime. Et pour avoir des signes de W plus un, nous avons dit. Et bien sûr, par défaut en Java, tous ceux-ci devraient être des zéros. Donc, nous ne nous soucions pas vraiment de mettre le premier à 0 et ainsi de suite et ainsi de suite. Donc, nous pouvons sauter ceci et commencer directement avec notre boucle for. Pour le premier sera à I égal à 0 et tout le chemin à la fin et incrémenté. Ensuite, la seconde boucle devrait être la moitié j et dans ce cas, nous allons aller jusqu'à la fin des valeurs et des poids. Ensuite, nous allons le mettre à jour. Et bien sûr, ce que nous allons faire maintenant, c'est vérifier si ces poids sont inférieurs ou égaux à ceux que nous traversons. Ensuite, nous allons mettre à jour la valeur à l'intérieur de cette formule, à l'intérieur de cette liste. Donc c'est ça. On va juste utiliser celui qu'on a utilisé avant. Laisse-moi revenir en arrière et l'écrire ici. Donc, si les poids à j sont inférieurs ou égaux au poids ou à l'œil. Maintenant rappelez-vous que je représente le poids, le poids réel. Donc, si nous sommes à moi égal à quatre, cela signifie que nous avons, ce qui est, c'est la façon dont nous représentons. Enfin, nous allons finir avec la dernière façon dont nous avons besoin, soit dix. Et c'est ce que nous visons réellement. Donc si l'attente, je suis désolé, on a une faute de frappe. Donc, si les poids à j est inférieur ou égal à, je, peut mettre à jour les PMR pour la cravate maire devrait être égal au maximum entre deux. Donc ce qu'on va faire, c'est utiliser Mad Max. Et bien sûr, on va l'utiliser. Soit je suis un à i ou autre chose qui est à i. Comme nous l'avons dit, cinq, nous soustrayons juste les poids à j. Et bien sûr, nous allons ajouter la valeur des valeurs à j. Donc c'est tout. Fondamentalement, c'est comment nous pouvons le mettre à jour. Et ici, nous avons une faute de frappe. Laisse-moi juste l'éclaircir. Ils ont dit que c'est notre formule, c'est comme ça que nous pouvons la mettre à jour, juste utiliser cette formule à partir d'ici. Maintenant, ce que nous allons faire est simplement de retourner les derniers dans la liste. Donc, retournez un a au poids réel que nous voulons. Maintenant, utilisons-le ici. Donc, à créer simplement une fonction principale, je vais juste définir quelques paramètres. Supposons donc, utilisons le même problème exact ou les mêmes paramètres exacts d'ici. Donc, nous avons le poids égal à 10, alors nous avons les valeurs qui sont 5, 4, 3, et 2. Donc, c'est un moins un tableau. Les valeurs doivent être 5, 4, 3 et 2. Ensuite, nous allons passer aux poids réels, qui sont aussi je peux juste copier cela à partir d'ici, 28201811, donc 2828 et 11. Ensuite, nous allons finir avec les valeurs de cette longueur. Et bien sûr, c'est, bien sûr, ce que nous allons faire maintenant est d'appeler la fonction réelle. Laisse-moi juste imprimer ici. Donc système dot out, point print à imprimer est en fait le sac à dos. Donc, je vais appeler cette fonction ici avec, à côté des paramètres suivants, donc wvaleurs. Et maintenant ce que nous disons, eh bien, nous avons un problème ici. Laisse-moi juste vérifier. Méthode. Ce n'est pas un playbook. D' accord. D'accord. On les a oubliés. Nous devrions ajouter cette désolation Fondamentalement maintenant si nous allons de l'avant et exécutons celui-ci. Donc on a 0, laissez-moi vérifier les valeurs et les poids. D' accord ? Donc je, ok, donc ici nous avons des poids et vous aurez des valeurs. Est juste commutation fait par erreur. Maintenant, si on recommence, on en aura 58, ce qui est exactement le même résultat que celui qu'on a trouvé ici et ici. Nous avons donc vu cela en utilisant trois façons. Le premier est d'utiliser nos pensées et de penser à y penser. Ensuite, on utilise celui-ci et on en a 58. Et finalement nous l'avons utilisé dans notre code. Donc, très probablement, c'est la bonne façon. Maintenant, ce qu'on va faire est de le visualiser une dernière fois. Nous allons visualiser tout le tableau. Donc, au lieu de revenir, appelez simplement un, je vais retourner un tableau. Et bien sûr, je vais créer une boucle for, non ? Oui. Désolé. Donc, trop longtemps à faire est d'itérer tout cela. Donc je vais le nommer aussi ici, MHC2, et je suis un sac à dos de W et de valeurs et de poids. Maintenant, allez tout le chemin pour être une longueur. Et bien sûr, on va les imprimer. Donc je vais simplement imprimer et avec le sous-espace de votre course à nouveau, nous allons obtenir la même chose exacte que nous avons d'ici. Nous avons donc quarante sept cent cinquante quatre et cinquante huit. Donc, ils ont dit fondamentalement, c'est pour le problème de knapsack en utilisant Java. 20. Prise avec Reptition avec une Implementation JavaScript: Ok, Donc dans cette vidéo, nous allons résoudre le sac à dos avec problème de manipulation en utilisant JavaScript. Donc la première chose que je vais faire est de créer notre fonction. Donc, la fonction et le nommer Knapsack. Je vais prendre les paramètres pour qu'on attende la longueur des articles. Tu as des valeurs et E. Maintenant, ouvrons ça. Maintenant, nous allons faire, est de créer réellement cette méthode ou cette moins extensible et un. Alors laissez-moi revenir en arrière et laissez-le un nouveau tableau de taille n. Nous avons dit que la taille devrait être le poids que nous avons plus 1. Maintenant, ce qu'on va faire est de le remplir avec des zéros. Ensuite, nous allons commencer avec nos deux boucles imbriquées pour. Alors laissez je égal à 0, je suis inférieur ou égal au poids. Et moi plus. Donc nous ne faisons rien, mais ce B est discuté ici, donc nous avons juste ces deux pour les boucles. Le premier de 0 à w, Le second est deux. Et pour que N1, nous avons j égal à 0 jusqu'à la fin et j plus, plus. Ensuite, nous allons vérifier si les poids auxquels nous avons affaire sont en fait inférieurs ou égaux au gaspillage que nous sommes sur cette liste. Et c'est le cas, alors nous devons le mettre à jour avec sont juste à venir pour le faire en JavaScript. Donc, si le poids au spécifique et qui est inférieur ou égal à l'indice, je l'adoucit. Nous allons mettre à jour le MBA chez I devrait être égal au maximum entre deux choses. Devrait être égal au maximum entre lui-même. Ou je suis à des ondes I moins P. Comme nous l'avons dit plus tôt. Et bien sûr, nous allons ajouter la valeur de la liste des valeurs à i j aussi. Donc, il y a un, fondamentalement c'est notre fonction réelle. Maintenant, ce que vous allez faire est de, après avoir terminé de ces deux boucles pour, aller retourner le MA à WWW. Maintenant, si on veut juste l'essayer, on va le faire. Définissons réellement. Alors laissez w égal à 10, va prendre le même exemple exact de lui. Donc w égal à 10, nous allons avoir des valeurs qui sont égales à. La valeur réelle est 28, 2018 et 11. Donc, les valeurs sont égales à 2828 et 11. Ensuite, nous avons les poids. Les poids égaux à cela sont égaux à 5, 4, 3 et 2. Ensuite, nous allons avoir n, qui est la longueur des points de valeurs. Ensuite, ce que nous allons faire est d'appeler la fonction à côté de ces paramètres. Donc W et les valeurs et les poids. Et bien sûr, on va l'exposer. Donc le journal de la console. Et nous obtenons après que nous allons faire est en fait juste haut et bas invite de commande. Et puis je vais me diriger vers mon répertoire à l'intérieur de ce bureau de tâches, j'ai JavaScript ici. Je suis un peu copier ça et je vais y aller. Et puis je vais exécuter ce problème en utilisant le nœud. Donc noeud sac à dos avec des répétitions, le ab.js et nous avons obtenu un a et par conséquent, indiquant que ce n'est pas un nombre. Laisse-moi vérifier. Tout semble bon pour les cheveux et le maximum. Donc le problème est, accord, donc le problème est juste là. Donc nous l'avons fait, nous devons le fermer comme un plus. Juste pour que ceci soit la formule réelle. Maintenant, si on y retourne et Annette aura 58 comme le nombre maximum qu'on peut obtenir de cette formule. Maintenant, ce que nous allons faire, c'est d'imprimer tout ça. Donc, au lieu d'avoir juste le dernier, je vais le faire juste pour le bien de ce problème. Donc, comme nous pouvons le voir concerne 000 011, 1822. Et si on retourne ici, on verra 000 011, 1822. Et bien sûr, c'est tout le chemin jusqu'au 2936404912, qui est exactement un 293640 quarante sept cinquante quatre cinquante huit. Donc, avec cela, nous pouvons nous assurer que notre problème fonctionne et nous avons obtenu le même résultat que celui que nous avons effectué manuellement ici dans cette liste. Donc c'est tout, fondamentalement c'est tout pour implémenter le knapsack avec leur pétition en utilisant le script java. 21. Prise avec répétition Mise en œuvre Python: Ok, Donc dans cette vidéo, nous allons résoudre le sac à dos avec problème de répétition en utilisant Python. Donc la première chose que je vais faire est de créer la définition ou la fonction. Je vais l'appeler sac à dos. Et à côté des paramètres que nous allons utiliser. Donc wn valeurs et poids. Maintenant, ouvrons-le. La première chose à l'intérieur de cette fonction, nous allons visualiser le tableau de liste réelle qui a MA, organisme, MA, et qui ne peut pas l'avoir à portée de. Donc, ce sera de zéros et ce sera pour moi dans la gamme de w plus un. C' est ainsi que nous pouvons créer cette liste en utilisant une ligne de code en Python. Alors ce que nous allons faire est de commencer avec nos deux boucles imbriquées pour. Donc, pour moi dans la gamme de W, cygne, nous allons créer une autre boucle pour, qui est pour j dans la gamme de AMP. Ensuite, nous allons commencer par la condition. Donc on n'a rien fait pour l'instant. Nous venons de créer ces deux pour les boucles. Maintenant, nous allons vérifier si les poids à j sont inférieurs ou égaux à I. Donc, si les poids à j sont inférieurs ou égaux à i, nous allons mettre à jour l'AMA à I. Donc je peux ajouter, je devrais être égal à l'une des deux choses. C' est le maximum entre la valeur réelle que nous avons, ou le maximum ou l'autre, qui est MA à Pi moins les poids à j plus la valeur de j. Maintenant, revenons en arrière et écrivez-le. Donc max à MA ou à la seconde, qui est MA aux poids à j. Ensuite, bien sûr, nous allons y ajouter les valeurs à j. Donc c'est tout fondamentalement. Ce qu'on va faire, c'est simplement rendre le MA au dernier, qui est à W. puisque nous allons juste avoir besoin de celui-là d'ici. Donc nous allons juste le retourner comme il est maintenant pour l'essayer, laissez-moi juste créer vos affaires. Nous allons utiliser le même exemple exact que nous avons utilisé ici. Donc w égal à 10, les poids sont 5432. Donc poids égal à une liste de 5432. Ensuite, nous avons les valeurs qui sont 28201811. Puis enfin, nous avons la longueur de ces valeurs de poids. Maintenant, ce que nous allons faire est d'appeler cette fonction et de l'imprimer. Vous pouvez donc simplement imprimer ce sac à dos à côté de ces valeurs et poids W. Maintenant, si nous allons ici et l'exécuter, donc je vais taper Python à côté de knapsack avec des répétitions et l'exécuter. Et nous allons obtenir 58 comme nombre maximum autorisé pour cet exemple spécifique. Maintenant, pour visualiser la liste réelle que nous avons créée ici, laissez-moi juste imprimer au lieu de MA et puis je retourne et une, toute la liste au lieu de retourner le dernier élément. Maintenant, si nous retournons et rafraichir et courir à nouveau, nous allons obtenir 0011182258. Et si vous les comparez, ils sont exactement les mêmes que l'exemple que nous avons fait auparavant. 01118, vingt deux vingt neuf, trente six quarante, puis quarante sept, cinquante quatre et cinquante huit. Donc, cela dit fondamentalement, c'est comment nous pouvons utiliser Python pour créer cette fonction, le sac à dos sans répétition. Alors on se voit dans la prochaine vidéo. 22. Sans répétitions: Très bien, donc dans cette vidéo, nous allons discuter du sac à dos sans problème de répétition. Maintenant, ce problème spécifique ne fonctionnera pas avec cette méthode que nous avons créée ici pour la quantité illimitée ou la quantité illimitée d'articles que nous avons. Nous allons donc utiliser un tableau 2D et nous en parlerons dans une seconde. Mais avant que nous allons utiliser exactement le même problème ou exercer cet exemple. Alors rappelez-vous qu'avec la, sans version, nous avons obtenu 57 comme réponse finale. Nous allons utiliser exactement le même exemple. Et on verra si on va avoir ça et 57 en conséquence. Donc, pour ce faire, permettez-moi juste de supprimer tous ces éléments et de les supprimer également à côté de cela. Maintenant, nous pouvons commencer, ce que nous allons faire est de créer un tableau 2D. Laisse-moi juste le créer et te voir dans un peu. Comme nous le savons, c'est la liste ou le tableau que nous allons créer et peut penser à ceux-ci comme le poids. Puisque nous avons besoin d'un poids de 10, ce que nous allons faire en fait, c'est d'extraire ces endroits vides par quelques valeurs. concerne, sont, étant donné que nous avons, par exemple, ce tube. Donc il y a deux SD attendre, laissez-moi juste les écrire ici. Comme nous l'avons dit plus tôt. Nous avons déjà, par exemple, ces deux. Et il a la valeur ou le montant de 11. Nous en avons trois avec 18, quatre avec 20, et cinq avec 28. Laisse-moi juste les essayer ici très vite. Donc, nous avons le montant. Nous avons 11, 18, 20 et 28. Donc ce qu'on va faire ici, alors laisse-moi juste, d'accord. Donc, la première chose à laquelle nous allons penser dans ce problème est que nous allons remplir ces endroits vides en supposant que nous n'avons que cet élément à remplir. Donc, par exemple ici, si nous voulons remplir le poids de 0 avec cet article, nous ne pouvons pas, donc nous allons juste le laisser vide avec 0. Maintenant encore, si nous avons un poids d'un et nous n'avons que cet article. Maintenant, nous pouvons regarder le poids de cet article qui est deux, qui est supérieur à un, alors nous ne pouvons pas faire avec réellement. Maintenant, nous nous demandons, si nous avons un poids de deux, vous avez un article qui a un poids de deux. Pouvons-nous vérifier ? Et on le stocke ici ? Oui, on peut. Donc, il va juste stocker sa valeur, qui est 11. D' accord, alors laissez-moi changer la couleur en vert et laissez-moi juste supprimer tout ça, les écrire à nouveau avec le vert. Donc, comme nous l'avons dit, ici nous avons 0, 0, et ici nous pouvons nous adapter à cela aussi. Donc, on va l'adapter. C' est 11. Maintenant, comme vous pouvez le voir, nous allons nous demander si nous avons un poids de trois et nous n'avons qu'un article de largeur deux, peut-on le stocker ? Oui, on peut. Donc magasin bio 11 ici. Et c'est la même chose pour tout ça, nous allons nous poser la même question. Donc, si vous avez un poids de 10, par exemple, et que nous avons seulement un article qui a un poids de deux. On peut le stocker ? Oui, on annule. Nous allons stocker sa valeur. Alors on va passer à ça. Maintenant, nous ne cherchons pas seulement ce poids de trois, recherche des deux 32. Donc ce qu'on va faire, c'est d'écrire 000. Et ici, on ne va pas stocker de zéros. Parce que rappelez-vous que nous allons avoir ces deux objets ensemble. Donc c'est soit on peut stocker deux ou trois, soit les deux en même temps. Maintenant, comme nous avons seulement ça comme un poids de deux, nous allons stocker cet article qui est 11. Alors ce qu'on va faire, c'est passer à trois. Maintenant, on va se demander si on peut stocker ça ici ? Oui, parce que c'est égal à un. Donc ce que nous allons faire remonte jusqu'à trois fois ici. Donc nous sommes les 11, nous allons aller 1, 2, et 3 aller à celui-là qui est 0. Et ici, nous en avons 18. Donc on va vérifier avec 18 plus 0 est plus grand que celui-ci. Alors on va l'ajouter. Dans ce cas, c'est le cas. Donc, je vais lui ajouter 18. Alors pensez-y de cette façon. Donc, vous pouvez stocker ou vous pouvez stocker trois. Dans ce cas, si vous voulez commencer, vous pouvez simplement le stocker avec une valeur de 11. Donc, nous allons ajouter 11 ici. Cependant, si vous ne le faites pas, vous devez stocker la valeur de 18. Maintenant rappelez-vous que chaque fois que nous travaillons avec ce tableau 2D, si nous voulons avoir des réponses ou si nous voulons nous assurer qu'il nous reste un poids de trois ici, nous devons revenir trois fois comme nous l'avons fait dans le tableau 1D dans l'exemple du problème de répétition de largeur. Donc dans ce cas, ce que nous allons faire, c'est d'aller jusqu'au bout et nous allons vérifier trois fois avant. Et ce cas, si vous êtes à ce stade juste ici, nous pouvons toujours ajouter une largeur de trois et finir avec cette ligne juste ici. Donc on est bons. Nous sommes ici. Nous allons obtenir 0 plus 80 et nous allons avoir 18 comme réponse. Passons maintenant à ça pour l'instant, nous allons nous demander. D' accord, donc qui en a 11 ou nous en avons 18 plus ces quatre moins un. Donc on va avoir 4 moins 3, ce qui est 1. Nous allons arriver à ce point qui est 0. Donc, on va stocker 18. D' accord ? Donc 0 plus 18 égal à 18 est supérieur à 11. On va le stocker. Ensuite, nous allons passer à ce dossier. Maintenant, nous allons nous demander si cinq est supérieur à trois ? Oui, c'est le cas. Donc on peut commencer trois. Ce que nous allons faire, c'est d'aller à gauche , laissez-nous y penser au début et r hat. Donc, si nous avons un poids de cinq, nous pouvons sûrement stocker les deux articles avec lesquels sont 23. Bon, donc on va les ajouter, 11 plus 18, ça va être 29. Maintenant, réfléchissons-y. La façon dont nous traitons ce problème, c'est que si nous sommes à cinq ans, nous allons simplement en soustraire trois, donc c'est 2. Nous allons aller jusqu'à deux, pour regarder la valeur ici, et il est 11. Donc nous allons soit stocker ce 11, juste pour l'ajouter ici, soit nous allons prendre 11 plus 80, soit 29, et 11 plus 80 mètres 29, ce qui est plus grand. Ensuite, on va commencer à 29 ans. Maintenant, nous allons faire exactement la même chose pour celle-là. Donc, il est soit 11 plus 18 ou 11, donc il choisirait sûrement 29. Donc 29, tout le chemin jusqu'à la fin. Maintenant, nous allons faire exactement la même chose ici. Nous allons nous demander, ici, nous pouvons stocker n'importe quoi. Cependant, puisque nous en avons déjà 11 ici, nous allons l'ajouter. Et nous allons arriver à ce point où nous en avons quatre. On va vérifier si c'est 20 plus les 4 moins 4. On va remonter jusqu'à 0. Donc 0 plus 20 est supérieur à 18. Oui, c'est le cas. Donc on va stocker 20, puis on va passer à 20. Nous allons également vérifier est 20 plus 5 moins 4, ce qui est à un. Donc ici, nous avons ce 0 est 20 plus 0. Il n'y en a pas. Donc je vais juste stocker 29 à la place. Donc ce que nous disons ici, c'est que nous n'avons pas vraiment besoin de ça si nous le voulons. Si vous avez seulement une largeur de cinq, nous pouvons stocker 32 et ils nous donneront une meilleure réponse de 29 au lieu d'avoir juste cet automne avec une réponse de 20. Maintenant, si nous pensons à ces six, nous pouvons réellement résoudre 24 avec une valeur de 31. Pensons-y avec la formule. Donc, nous adhérons à six, allons prendre six moins quatre, ce qui est deux, vous allez regarder 211 plus 20, 31 plus de 9029. Donc nous allons le stocker ici tout le long du chemin maintenant, nous allons y penser avec les sept. Donc, à sept ans, nous pouvons stocker 20 plus le 7 moins 4, ce qui est 3. Nous en avons 18, donc 20 plus 1838. Donc, nous pouvons soit stocker 38 ou la valeur ci-dessus, qui est 29, va choisir 38. Et on les a tous utilisés jusqu'au bout. Ici où nous en avons neuf. Maintenant, réfléchissons-y. Si nous avons 20 plus neuf moins quatre, ce qui est en fait cinq. Donc on va prendre 29 plus 20, ce qui est 49. Donc, nous pouvons choisir 49 ou 29 vous montrera choisir 2049, qui est sélecteur. Et enfin, pour les 10, nous allons avoir les mêmes 49 qu'avant. Maintenant, quant à celui-ci, nous allons avoir les mêmes valeurs exactes jusqu'au dossier. Maintenant, on va vérifier que 28 est plus grand que 29 ? Non, ce n'est pas le cas. Donc, nous allons simplement stocker 2009. Maintenant, quand j'ai dit que si c'est 28, c'est plus que 29, tu peux, tu dois faire 28 plus ça. Cinq moins cinq, ça va aller jusqu'à 0. Nous allons regarder celui ci-dessus, qui est ici 0. Donc 0 plus 28 est supérieur à 29. Non, donc on va stocker 29. Maintenant, dans ce cas à six, nous allons aussi stocker seulement 31 car il n'y a rien ici aussi à 0. Je suis désolé, juste là. Ensuite, nous allons regarder les sept. Donc ici, nous avons 38 et la valeur de celui-ci qui est vérifier. Nous avons 28 plus sept moins cinq, ce qui est à deux. Donc 28 plus 11, il est en fait 39, ce qui est supérieur à 38. Donc on va y aller avec 39. Enfin, nous allons faire, pour ces derniers, nous sommes à 8 ans. On va prendre 38 ou 28 plus 8 moins 5, ce qui est 29. Donc 28 plus 29 va nous donner 46. Nous allons le choisir alors 9 moins 5, ce qui est 4. Nous avons donc à l'automne 20 ou 20 plus 28 ou 49. Donc nous avons 48 ou 49, nous allons aller avec 49, ce qui est plus grand. Enfin, pour le dernier, nous allons vérifier si nous allons prendre 49 ou nous allons prendre 8 plus 10 moins 5, ce qui est à cinq aussi. Donc, nous avons 29 plus 28, ce qui est en fait 57. Et c'est le plus grand ou le plus grand capteur que nous pouvons avoir. Et comme nous pouvons le voir, nous avons obtenu exactement le même résultat que nous l'avons fait en utilisant notre 1000. Et dans ce cas, ce qu'on a fait, on a utilisé les cinq plus deux plus trois. Et si nous voulons nous assurer dans cet exemple, peut toujours le faire en disant simplement que vous êtes ici à ce 57. Comment l'as-tu eu ? Vous venez d'ajouter 28, qui est le poids cinq dans les dix moins cinq, qui était ici, Ce 29. D' accord ? Et ce 29 signifie que vous n'avez pas ajouté 4, vous ajoutez juste celui ci-dessus qui est à trois, non ? Donc ici, nous en avons cinq jusqu'à maintenant. Et maintenant on va vérifier que les 29 et 11 sont les mêmes ? Non, Cela signifie que vous avez ajouté 32 aussi. Donc, c'est tout essentiellement pour l'exemple pas à pas de ce problème. La prochaine vidéo que nous allons discuter ou travailler avec le pseudocode que nous allons utiliser et l'implémentation du code. Alors, voyez-vous. 23. Prise sans Repetition: Bon, donc ce que nous venons faire maintenant, c'est que nous allons passer par le pseudocode de ce problème. Maintenant que nous avons implémenté ou travaillé avec une solution et que nous travaillons à ce problème à travers un exemple, nous pouvons réellement trouver les formules que nous allons utiliser pour écrire le pseudocode. Donc la première chose que nous allons faire est de créer notre tableau ou notre matrice 2D. Maintenant, dans ce cas, nous allons supposer que c'est qu'au début nous avons une liste vide. Donc ce que nous allons dire, c'est que le premier serait vidé. Le second aura cet article. La troisième, qui est ici, aura cet article à côté de cet article aussi, la quatrième rangée aurait ces trois éléments et la dernière aurait tous ces éléments. Et quand je dis qu'ils auraient ces articles, je veux dire qu'ils peuvent choisir où ils veulent parmi ces articles. Alors c'est tout. Fondamentalement, nous commençons avec un tableau vide. Bien sûr qu'on va le remplir avec des zéros. Et bien sûr, le premier ici sera tous les zéros aussi. Donc c'est tout en gros. Maintenant, ce que nous allons faire est de créer notre matrice 2D réelle, qui est une image, MA. Maintenant, ce que nous allons faire est de spécifier les tailles. Souviens-toi qu'on a besoin d'un vide ici. Donc ce que nous allons faire, c'est d'en ajouter un. Donc, au lieu d'avoir la longueur de quatre, par exemple, supposons cet exemple. On a 2345. Donc, nous avons la longueur de quatre que nous allons faire est de créer cette matrice 2D comme une longueur ou une taille de cinq au lieu de quatre, puisque nous devons ajouter ce vide ici. Donc, ce que nous allons faire est de dire que les tailles devraient être n plus un pour les lignes et W plus une pour la colonne, indiquant que nous avons besoin de 11 colonnes ici, jusqu'à la danse que nous devons extraire. Maintenant, ce que nous allons faire est de commencer avec nos deux boucles pour. Le premier commencera à partir de, donc je serai de 0 jusqu'à la fin. Et c'est inclusif. Ensuite, nous allons créer une autre boucle for. Je vais le nommer. W va être de 0 jusqu'au grand W. Et aussi celui-ci est inclusif. Maintenant, ce que nous allons faire est de vérifier si nous sommes à une position spécifique où nous avons I égal à 0. Donc, si le rho I est égal à 0 ou la colonne est égale à 0. Donc je pourrais être 0 ou w égal à 0. Ce que nous allons faire est de mettre ça à 0. Comme nous l'avons dit, nous avons ces valeurs, zéros ici, et celles-ci seront utilisées plus tard. Donc, chaque fois que nous voulons revenir à la position précédente. Imaginez donc que nous sommes à ce 1112 et que nous demandons la position précédente de ceci et cela n'existe pas. Ainsi, nous devons avoir quelque chose avant une commande pour que nous n'ayons pas d'erreur pendant que j'écris notre code. C' est pourquoi nous avons supposé cela vide au début, qui ne sera que des zéros. Donc, si je vais à 0 ou w égal à 0, ce que nous allons faire est de dire que je suis à I et w devrait être égal à 0. C' est donc la première condition. Maintenant, la deuxième condition, si les poids que nous avons en passant par ces poids sont inférieurs ou égaux à la manière réelle qui pourrait le passer à travers. Maintenant, dans ce cas, ce que nous allons faire est de mettre à jour le MA ou cette matrice 2D. Alors réfléchissons-y une seconde. Supposons que nous sommes à cette position quatre, et nous en sommes là. On a la température 3. Donc nous ne connaissons pas encore cette valeur. Donc on va vérifier. La première chose que nous allons vérifier est qu'en passant par ceci, donc si ces trois sont inférieurs ou égaux à quatre, maintenant c'est le cas, c'est vrai, alors nous pouvons le mettre à jour. Comment pouvons-nous le mettre à jour ? Nous pouvons soit passer par 4 moins 3, ce qui sera un, et y ajouter cette valeur de trois, qui va être 18 plus 0. Ou nous allons prendre la valeur au-dessus, qui est 11. C' est pourquoi nous devons vérifier si les poids sont réellement inférieurs ou égaux à ce formulaire. Et bien sûr, si ce n'est pas le cas, ce que nous allons faire est de simplement prendre la valeur d'en haut. Et bien sûr, un exemple de cela pourrait être que nous sommes à ce poids trois. Je vais vérifier si ce poids est inférieur ou égal à deux et il n'est pas inférieur ou égal à deux. Ce que nous allons faire, c'est simplement prendre la valeur d'en haut. Donc nous allons accéder au même un A au même poids. Cependant, nous allons y accéder avec un index minus1 pour avoir la valeur de ce qui précède. Donc c'est ça fondamentalement laissez-moi juste prendre toutes ces choses et les rendre un peu plus petits. Et je vais les écrire ici. Ensuite, continuons avec notre code. Donc nous avons dit que si f égal à 0 ou w égal à 0, nous allons le faire. Maintenant. La deuxième condition est de vérifier si les poids au poids spécifique sont inférieurs ou égaux au poids que nous avons ici. Et si c'est le cas, nous devons mettre à jour la matrice 2D réelle. Donc, ce que nous allons faire est de vérifier si ce poids, donc poids à un indice spécifique, je vais le laisser vide pour l'instant, est inférieur ou égal à w si cette condition est satisfaite. Mais nous allons faire est de mettre à jour ce i w spécifique pour être égal à l'un ou l'autre, donc le maximum entre deux choses. Donc c'est soit le K i, donc je vais l'écrire ici. Donc c'est soit à I moins 1 w. donc c'est soit la valeur ci-dessus, soit la valeur de la liste. Donc nous sommes à cette matrice 2D, nous allons, comme nous l'avons dit, nous allons reculer par un. Et comme pour les colonnes, nous allons à partir de W. Donc, supposons que nous sommes à cette valeur quatre et nous sommes à ce poids de trois. Et je fais quatre moins trois, ce qui est égal à un. Donc on va faire w, ce qui est quatre moins les poids à un indice spécifique auquel on a affaire. Et puis ce que nous allons faire est d'ajouter cette valeur à partir des valeurs. Nous allons donc ajouter la valeur de notre nouveau poids. C' est, par exemple, celui-ci, 18 ou 20, ou 28 ou plus. C' est donc le maximum entre celui ci-dessus ou celui d'ici. Donc, c'est fondamentalement la formule que nous allons utiliser. Maintenant, nous avons, toujours la dernière condition. Donc, si ces deux conditions sont remplies, la dernière est de simplement prendre la valeur d'en haut. Et comme nous l'avons dit, ce n'est pas plus grand. Je suis désolé, ce n'est pas inférieur ou égal à notre poids. Nous allons juste copier la valeur d'en haut. Sinon, ce que nous allons faire est de spécifier que l'index à i, w, je suis désolé, la valeur de a doit être égale à la valeur à I moins 1 w. Donc c'est tout essentiellement pour notre pseudocode pour ce problème. Dans les prochaines vidéos, nous allons les implémenter dans notre code ou dans nos langues. Alors, voyez-vous. 24. Prise sans répétitive: Très bien, donc dans cette vidéo, nous allons implémenter notre fonction en utilisant Java. Donc la première chose que je vais faire est d'initialiser notre fonction qui est une statique publique. Et puis-je retourner l'entier ? Je vais faire un sac à dos. Et cela va prendre quelques paramètres tels que l'attente. Et je prends un tableau de poids, puis nous allons prendre des valeurs profondes comme un tableau aussi. Et enfin, vous, je vais prendre la capacité ou la longueur de ces valeurs et poids. Maintenant, ce que nous allons faire est de, au début et elle ment et w. Ensuite, nous allons construire notre matrice 2D, qui va être appelé un a. Et il va avoir n plus un et W plus un comme la taille de la longueur n. Rappelez-vous donc que nous avons dit que nous avons besoin de n plus un parce que nous avons créé un tableau vide ou une liste vide ici. Et chaque fois que nous allons passer par, par exemple, si vous êtes là et suivant, il va avoir une liste vide plus celle-ci. Ou si vous y êtes, hey, nous allons avoir celui-ci plus celui-ci, et ainsi de suite et ainsi de suite. Donc, c'est pourquoi nous avons ajouté n plus 1 ici indiquant que nous avons et plus un grandit. Ok, donc maintenant ce qu'on va faire, c'est commencer par notre boucle for. Donc le premier qu'on a dit qu'il allait s'appeler « I » tout le long du chemin. Et le second sera j, ainsi de suite. Désolé, W. Donc w est égal à 0, puis w inférieur ou égal à, créer un w. donc w est inférieur ou égal à la majuscule W et W plus bouton. Ensuite, nous pouvons vérifier si i o w est égal à 0. Nous allons simplement ignorer mais en stockant à I et w la valeur de 0. Maintenant, le deuxième cas est que si le poids à i moins1, et nous verrons pourquoi il est I moins 1 est inférieur ou égal à w. Si c'est le cas, alors nous allons mettre à jour celui-ci et faire le maximum entre deux choses. Autrement dit, la première devrait être la valeur réelle que nous avons. Donc, je suis un à w et cette valeur de p au-dessus. Ou ce qu'on va faire, c'est aller au-dessus. Et quant au W, nous allons ajouter w moins les poids à I moins 1. Alors c'est tout. Fondamentalement, c'est comme ça que nous pouvons le faire. Bien sûr, nous devons ajouter un, quelque chose qui est la valeur ou la valeur des articles que nous avons. Et on va le voir dans un peu. Mais pour l'instant, je vais simplement ajouter des valeurs à I moins 1. Alors réfléchissons une minute. Qu' est-ce qu'on dit ici ? Donc, nous disons que si les poids à I moins 1 sont inférieurs ou égaux à w. maintenant, nous allons nous référer à ceci par moins un. Pourquoi utilisons-nous I minus1 ensemble d'IA ? Rappelez-vous que nous avons ajouté ici une liste vide. Donc, si une valeur, par exemple, si nous traitons avec celui-ci, elle aura un index de un. Cependant, dans la liste que nous allons obtenir, nous allons les avoir comme 2345. Supposons qu'ils soient comme ça. Donc 2345 et leurs valeurs ou montants sont les suivants. A 11182028. Ce sont donc les indices. Nous avons donc l'indice 0, 1, 2 et 3. Donc, si vous voulez y accéder à partir d' ici, nous avons les poids et ici nous avons les valeurs. Et bien sûr, si nous voulons les stocker dans la liste, nous allons devoir faire un tri. Par exemple, supposons que nous soyons ici à I. Si nous voulons accéder à celui-ci, nous sommes maintenant à l'index 1. Cependant, cet indice est à 0 et cette liste de poids, parce que nous avons ajouté cette liste vide, qui a pris une place. Donc, si nous voulons accéder à ces poids et valeurs en utilisant I et w, nous devons rappeler ou nous souvenir de cette liste vide. C' est pourquoi nous allons y accéder en utilisant le par moins un. Alors c'est tout. Fondamentalement, c'est pourquoi nous utilisons I minus1 ici, ici, et aussi ici quand nous accédons aux valeurs à I moins 1. C' est ainsi que nous pouvons le changer. Et nous avons encore la dernière condition, qui est si ces deux conditions ne sont pas satisfaits avec juste fait un retour sont. Placez la même valeur que ci-dessus dedans. Et c'est tout en gros. Maintenant, chaque fois que nous terminons cette boucle while, nous allons juste retourner la valeur à et, et le capital W. Donc c'est tout essentiellement pour ce problème. Allons-y et essayons-le ici. Donc, ce que je vais faire est de créer une fonction principale où je vais avoir une valeur. Supposons donc que nous allouons des valeurs sous forme de liste. Je vais avoir un 2345 divisé. Alors je vais avoir des poids. Je suis désolé, je viens juste de monter. Donc, nous avons les poids. Et les valeurs devraient être les suivantes, 11182028. Et bien sûr, nous allons avoir besoin du w, qui est dix. Et puis nous allons avoir n, qui est la longueur des points de valeurs. Donc c'est tout maintenant qu'on doit encore appeler le sac à dos. Donc, je vais le retourner dans les résultats du problème de sac à dos avec, côté de ceux-ci, tous ceux-ci. Maintenant, ce que je vais faire, c'est simplement l'imprimer ici. Donc, je vais imprimer le résultat. Maintenant, si je vais de l'avant et que je l'exécute ici, et que je vais obtenir comme la valeur 57, ce qui est en fait la même valeur que celle que nous avons obtenue de celui-ci. C' est juste ici, 57 en utilisant cet exemple et en utilisant notre éducation avec où nous avons 57 en utilisant également trois plus deux plus cinq. Donc c'est tout pour ce problème. Si vous voulez voir ces deux, le tableau, vous pouvez simplement le créer ou le retourner juste là, je suis désolé. Donc, nous pouvons simplement le retourner ici dans un tableau 2D. Et au lieu de retourner ce spécifique, un, peut simplement supprimer cela et retourner ici ce tableau 2D comme suit. Et bien sûr, en fait, ce que nous allons faire est de les stocker dans un résultat. Ensuite, nous pouvons aller dans une boucle for en commençant par le résultat, cette longueur. Et nous allons ajouter le résultat à par la longueur. Ensuite, nous allons simplement les imprimer. Donc résultat. Et puis ajoutez j plus un peu d'espace, puis imprimez une ligne r1. Et nous allons obtenir ce tableau 2D. Et bien sûr, si nous vérifions celui-ci que nous avons construit ici, il semble exactement le même. Nous avons donc 000 jusqu'à 11, puis nous avons 001111, puis 929 000, 011, 820, 29, 31, et puis trente huit, quarante huit, quarante neuf. Quarante neuf. Donc c'est correct. Et la fin avec 46, 4957, et nous les avons ici. C' est donc le tableau 2D exact que nous avons manuellement. Donc, notre solution est correcte, et c'est la bonne façon d'implémenter ce problème en utilisant Java. Vendre le sac à dos problème sans répétition. Donc c'est tout pour cette vidéo. On se voit dans la prochaine. 25. Prise sans répétitive: Ok, Donc, dans cette vidéo, nous allons implémenter notre fonction pour le problème de sac à dos sans répétition en utilisant JavaScript. Donc la première chose que je vais faire est de créer notre fonction, qui est le sac à dos. Et il va prendre les paramètres suivants. Donc le W, le poids, les valeurs de poids réelles. Et puis on pourra l'ouvrir. Maintenant, ce que nous allons faire est de définir ces deux indices que nous allons utiliser. Ensuite, nous allons créer notre tableau fonctionnel ou 2D. Et dans ce cas, ce sera un tableau et plus un, comme nous l'avons dit. Ensuite, nous pouvons commencer avec notre boucle for. Donc je serai égal à 0, comme nous l'avons dit, ça ira jusqu'à la fin. Et puis je vais sortir ensemble, puis nous allons avoir p w. dans ce cas, w est égal à 0, puis tout le chemin jusqu'à la capitale W et mis à jour. Maintenant, chaque fois que nous entrons dans cette boucle, mais nous allons faire est de créer un nouveau tableau à un index spécifique de I. Donc, ce sera un nouveau tableau de longueur w plus un pour le remplir. Et maintenant, dans ce cas, nous allons vérifier si je suis égal à 0 ou w est égal à 0. Ce que vous allez faire est simplement d'ajouter à cela et je W une valeur de 0. Maintenant, la deuxième condition est si les poids à un indice spécifique et je vais désigner par I moins 1. Nous allons en parler dans le lit, est inférieur ou égal à w. c'est le cas. Ensuite, nous devons mettre à jour ce W dans l'une des deux choses. Donc, le maximum entre la valeur au-dessus. Donc c'est vrai, suis-je moins 1 w ? Ou la deuxième chose qui est, comme nous l' avons dit, nous allons aller au-dessus et ensuite aller à gauche en utilisant w moins les poids à l'indice spécifique, donc c'est à I moins 1. Et bien sûr, ce que nous allons faire est d'y ajouter de la valeur. Donc, les valeurs à I moins un. Et puis c'est ce qu'on va finir avec. La dernière condition est à ces deux conditions ne sont pas satisfaites, mais nous allons faire est de simplement donner cette position spécifique, la valeur au-dessus. Donc je moins 1 W. Donc c'est tout en gros. Maintenant, parlons de pourquoi nous utilisons le I moins 1 au lieu de I dans ce cas. Et la réponse est que, rappelez-vous que nous utilisons un tableau vide ici. Donc un critère de liste vide. Et ce que nous avons fait, c'est que nous avons l'indice de 0 pour cela, alors nous avons l'indice d'un pour ceci, un, index de deux pour cela, et ainsi de suite et ainsi de suite. Cependant, lorsque nous obtenons les entrées, nous allons les obtenir comme suit. Donc, à 11 a la valeur de l'indice de 0. Et si vous regardez cette affaire, nous l'avons comme un index d'un et la matrice 2D. Donc ce que nous allons faire si nous voulons y accéder, nous allons utiliser I moins 1, qui est 1 moins 1. Nous allons avoir 0 et nous pouvons ajouter ensemble correctement. La même chose s'applique à tous. Donc, si nous sommes à l'index 2 ici, comment pouvons-nous y accéder en utilisant deux moins un, qui est l'index un. Donc c'est tout Fondamentalement, c'est pourquoi nous avons utilisé par minus1 ici, ici et là. Donc c'est tout pour ce problème, la dernière chose que nous allons faire est simplement de retourner le dernier ici, qui est à et, et le grand w. maintenant essayons. Donc, je vais créer des valeurs de 2345, je suis désolé. Les poids. Ensuite, je vais avoir les valeurs de 11182028. Alors je vais avoir le poids de dix. Et enfin, à la fin de cette longueur, donc valeurs cette longueur. Et maintenant, on va appeler le sac à dos. Donc je vais me connecter à sac à dos. Et à côté de ceux-ci, donc w poids , puis valeurs, et puis , ok, maintenant passons ce problème ou programme. Donc, ce que nous allons faire est de naviguer vers ce répertoire et nous allons appeler, laissez-moi juste l'appeler ici. Donc noeud knapsack sans répétition, ab.js va l'exécuter et je vais obtenir 57 comme valeur de définition, ce qui est le même que nous avons ici. Et bien sûr ici. Donc c'est ça, c'est comme ça que nous pouvons le résoudre. Maintenant, la dernière chose que je vais faire est de visualiser tout le tableau 2D. Donc, au lieu de retourner un entier spécifique, je vais retourner le tableau entier. Maintenant, si je le lance à nouveau et je vais obtenir est un tableau et nous avons le premier coup, deuxième, troisième, quatrième, et 550. Ce qu'on va faire, c'est juste les comparer. Donc pour les AVC, en fait tous les zéros, qui est fondamentalement ce que nous attendions ici. Ensuite, nous en avons 000 et ensuite tous 11. Hey, nous avons les 29 autres, donc nous aurons raison. Ensuite, nous avons 3849 graphique ici. Et enfin, nous avons 46, 4957. Et ils sont là. Donc c'est essentiellement pour ce problème. C' est ainsi que nous pouvons nous assurer qu'il est correct et notre mise en œuvre de notre code est réellement correcte. Donc, c'est tout pour le Knapsack sans répétition en utilisant JavaScript. Cela dit, c'est la fin de cette vidéo. se voit dans la prochaine. 26. Prise sans répétition sans répétition, mise en œuvre Python: Ok, donc dans cette vidéo, on va résoudre le sac à dos sans problème de permutation en utilisant Python. Donc, la première étape que je vais faire est de créer une fonction et peut simplement le nommer knapsack. Et c'était un gros gong de prendre quelques paramètres tels que le poids, les valeurs de poids et n. Alors ouvrons ça. Et la première chose qu'on va faire est de créer notre matrice 2D. Et cette matrice devrait prendre deux paramètres. Maintenant, comment pouvons-nous le construire en utilisant une ligne de code ? Nous voulons simplement spécifier cela pour la ligne. Donc pour x dans la gamme de W plus un. Et puis comme pour les colonnes, je suis désolé, c'est pour les colonnes et comme pour la ligne, je vais le faire pour la plage et plus1, comme nous l'avons dit. Maintenant, nous pouvons commencer avec notre boucle for. Donc, la première boucle pour devrait commencer dans 0 et se terminer par n plus 1. Donc, pour I dans la portée et plus un, alors la seconde pour la boucle devrait commencer une plage de 0 à W plus un. Désolé, nous avons W. majuscule et commençons par notre code. Donc la première chose que nous allons faire est de vérifier si je suis égal à 0 ou w est égal à 0. C' est le cas. Ensuite, nous allons simplement vouloir mettre à jour ou allons simplement ajouter 0 dans cette valeur. Donc c'est tout maintenant autrement. Donc ce qu'on va faire est de vérifier si les poids à I moins 1. Nous allons parler de moi moins 1 Lebanon bit. Mais pour l'instant, pensons-y comme ceci. Donc, si elle est inférieure ou égale à w, ce que nous allons faire est de mettre à jour l'œil, le tableau 2D aux indices spécifiques dans le maximum entre deux choses. Le premier est la valeur réelle que nous avons au-dessus. Donc je moins1 comme il est, J'indique la route et w ou autre chose, c'est le MA à I moins un. Et quant à la colonne, nous avons dit que nous devons soustraire de W, les déchets que nous allons obtenir. Donc ce Pi moins un dans ce cas. Et bien sûr, nous allons ajouter la valeur de celui-ci, qui est à I moins un aussi. Et enfin, ce n'est pas le cas. De plus, nous allons faire autre chose. C' est juste de prendre la valeur au-dessus et de l'ajouter à celui-ci juste ici. Donc je suis à I moins un qui est au-dessus. Donc, c'est fondamentalement maintenant ajouter le score que je moins1 dans le, attendez. Pourquoi on l'a utilisé ? Parce que si nous revenons à notre pseudocode, comme nous pouvons le voir, nous avons dit que nous avons un tableau vide ici. Et si nous pensons à nos poids et valeurs, nous avons des poids, des valeurs et leurs indices sont les suivants, 0123. Cependant, dans notre tableau 2D, si vous voulez accéder à celui-ci, ce n'est pas à l'index 0, index1. Ici, nous avons l'indice 0, 1, 2, 3, 4 et 5. Donc, si vous voulez y accéder, c' est à l'index 2 ici. Cependant, il est à l'index un et notre entrée. C' est pourquoi, si nous voulons accéder à celui-ci, nous soustrayons simplement d'un. Donc, si nous sommes à l'index 3, cela suppose que nous avons 0, 1 , 2 et 3, nous sommes ici. Donc, à l'index 3, comment y accéder pour utiliser notre empathie. Donc, nous faisons l'indice 3 moins 1, qui est 2. Maintenant, nous pouvons y accéder en utilisant des poids et des valeurs à l'index deux. Donc, c'est toute l'idée sur le i1 x1 et comment les utiliser. Et bien sûr, si vous êtes confus avec cela, nous pouvons simplement toujours ajouter 0 ici et ici. Donc, cela commencera à 0, et cela commencera à 1, 2, 3. Mais pour ne pas être complexe ou pas, rendre compliqué, j'ai simplement ajouté i moins un au lieu de I. Donc c'est maintenant ce que nous allons faire est de simplement retourner le MA à l'ET réel, et w. donc c'est la dernière entrée. Maintenant, essayons-le. Donc, les valeurs ici sont en fait, comme nous l'avons dit, nous avons 11182028. Ensuite, nous avons les poids qui sont 2, 3, et 4, et 5. Ensuite, nous avons le W, le poids dont nous allons avoir besoin pour être égal à 10, et juste la longueur des valeurs. Maintenant, essayons-le. Je vais imprimer le sac à dos. Dans ce cas, je vais avoir des poids w, puis des valeurs, alors. Et maintenant, si nous allons de l'avant et nous dirigeons vers notre CMD, ce que nous allons faire est d'exécuter le knapsack Python sans répétition. Je l'ai exécuté. Et ici, nous avons alors index valide. Vous avez un dicton étroit que 0 pour x et les gains de 0. Ok, donc nous avons, nous ne nous sommes pas engagés, c'est juste avoir fiancé. Essayons à nouveau. C' est une faute de frappe. Nous avons une longueur, nous avons oublié d'ajouter le n ici égal à maintenant je pense que nous sommes bons. Maintenant magnétique, on va obtenir ce résultat de 57, comme vous pouvez le voir ici. Cela indique donc que nous avons atteint notre objectif. Maintenant, ce que nous allons faire est de visualiser l'ensemble du tableau 2D. Donc, au lieu de retourner cette dernière valeur, je vais juste retourner tout le tableau. Maintenant, si je recommence à essayer, je vais avoir ça comme on l'a dit. Donc, nous aurons la première ligne, deuxième colonne. Et bien sûr, si vous voulez vous assurer que c'est correct, ce que nous ne faisons pas, c'est simplement les comparer à ceux-ci. Donc, la première rangée, comme nous l'avons dit, devrait être tous les zéros. La deuxième rangée est 0, 0, jusqu'à 11. Et le troisième serait 000 011, 1818, et ensuite tous, 29, puis nous avons 000 011, 1820, 29. Ensuite, on finira avec 49 et 49. Et la dernière rangée se terminera par quarante six, quarante neuf et cinquante sept. Si on regarde ça, on a 46 4957. Cela indique donc que notre solution est correcte. Donc c'est tout pour cette vidéo. se voit dans la prochaine. 27. Nombre de sous-ensembles qui correspondent à un nombre spécifique: Bonjour et bienvenue. Dans cette vidéo, nous allons discuter du problème de trouver le nombre de sous-ensembles pouvant s'ajouter à un nombre spécifique. Maintenant, dans cet exemple, nous avons un ensemble de quatre chiffres, 1345, et nous avons le numéro neuf, que nous allons utiliser dès maintenant. Donc, ce que nous allons faire est de vérifier si nous avons un sous-ensemble ou plus d'un sous-ensemble qui peut additionner jusqu'à neuf. Et dans cet exemple, nous avons deux sous-ensembles. Le premier est 135, et le second est pour N5. Et les deux additionnent jusqu'à 90. Si vous additionnez tous les indices d'éléments à l'intérieur du sous-ensemble, et vous obtiendrez neuf comme une valeur finie. Maintenant, pensons-y une seconde. La première approche que nous pouvons faire est de tout résoudre en utilisant la récursivité. Et la raison pour laquelle je dis ça, c'est parce que si vous voulez y penser ou que nous le résolvons en utilisant un morceau de papier. Donc, par exemple, pensons à cela. Si on a un set vide juste ici. Laisse-moi le dessiner ici. Ce que nous allons faire est de passer à travers chaque élément et de l'inclure une fois et de s'en débarrasser l'autre. Donc, par exemple, Au début, nous avons un ensemble vide. On va vérifier si c'est égal à 9. Ce n'est pas le cas. Ce que vous allez faire est d'ajouter celui-ci d'ici. Laisse-moi changer la couleur. Nous allons ajouter ce numéro 5200 à la fois. Et on va le garder tel qu'il est pour la deuxième fois. Maintenant, ce que nous allons faire est de vérifier aussi avoir cela est égal à 9. Ce n'est pas le cas. Ce qu'on va faire, c'est aller à l'autre numéro, qui est quatre. On va l'ajouter une fois. Et gardez juste cinq, l'autre terme. Et ici, nous allons l'ajouter et le garder vide. Maintenant, nous pouvons passer au troisième numéro, qui est le 3. Et les travaux que nous allons faire sont exactement la même chose. Donc, ici, nous avons 5, 4, 3, et ici nous avons je suis désolé. Oui. D'accord. Donc 54. Et bien sûr, nous allons avoir ici 53 et nous allons le garder cinq, juste ici, et ainsi de suite et ainsi de suite jusqu'à obtenir toutes les combinaisons possibles que nous pouvons obtenir. Et bien sûr, nous allons vérifier à chaque fois que nous avons construit un écran, nous allons vérifier si c'est égal à quatre. 29 par exemple, ou cela est égal à neuf. Donc, nous avons 54 est égal à neuf. Alors j'incrémente le compteur. Donc peut-être que vous avez un compteur variable ou quelque chose, et cela sera incrémenté. Donc nous en avons neuf pour l'instant. Ensuite, nous allons vérifier, par exemple, l'autre solution qui est 1, 3, et 5, elle comprend cinq, est ici, cinq, 53. Et nous allons avoir un 531, ce qui va aussi être vrai. Et nous allons inclure ou incrémenter le compteur. Et comme nous pouvons le voir pour construire ce q, nous devons utiliser la récursivité ou c'est la façon la plus logique de le faire. Maintenant, ce que nous allons faire est d'écrire le pseudocode pour cette méthode de récursion. Ensuite, nous allons essayer de l'optimiser en utilisant la programmation dynamique ou la mémorisation. Alors allons-y et faisons-le ici. Très bien, donc une fonction prendra trois paramètres. Le premier est la liste que nous allons avoir. Donc je donne juste un nom à la liste. Alors on va prendre un total. Je vais l'expliquer dans une seconde. Et enfin, un index I. Alors réfléchissons une seconde. Qu' est-ce qu'on va faire ? Au début, nous allons construire ce tableau qui est vide ou moins, qui est vide. Et puis nous allons ajouter 52 à la fois et nous allons le garder comme il est pour ça. Et comment allons-nous faire ça ? Laisse-moi juste le mettre ici. Alors laissez-moi supprimer ceci et continuons. Donc, ce que nous allons avoir, c'est un indice qui indique ce numéro cinq. La première fois que nous commençons, alors ce que nous allons faire est d'ajouter ce fichier, par exemple, à la liste. Ensuite, ce que nous allons faire, nous allons reculer un par un jusqu'à ce que tous les éléments soient en boucle. Et supposons que nous ajoutions cet élément, qui est quatre. Laisse-moi juste noté en rouge. Supposons donc que ce que nous allons faire est de vérifier si nous pouvons construire une liste ou construire ce numéro neuf en utilisant cette liste, seulement les éléments qui comprend quatre et avant. Donc, ce que nous allons faire est de vérifier ou de créer une fonction qui nous donne ce nombre exact, combien d'ensembles que nous pouvons faire et que vous pouvez en avoir deux pour que nous obtenions ce numéro neuf en utilisant seulement ces éléments. Donc, si l'index est ajouter ces trois ici, nous avons la liste de 13 seulement. Donc, nous voulons inclure 45. Donc c'est ce que nous entendons par là que je vais le décrémenter. Et. Vérifiez combien de listes nous pouvons avoir un ordre pour avoir ce numéro neuf. Maintenant en ce qui concerne le total, mais nous ne voulons pas faire est de décrémenté chaque fois par le nombre à l'index spécifique. Et vous pouvez comprendre en une seconde une fois que nous nous sommes assis avec l'écriture du code. Et ce que nous voulons faire est d'obtenir enfin le numéro du possible afin que nous puissions avoir un ordre pour obtenir ce numéro neuf. Alors laissez-moi juste supprimer ceci. Et commençons par notre procédure pas à pas. Et nous allons parler et l'expliquer tout en le traversant. Donc la première chose que je vais faire est, donc c'est notre fonction. Alors laissez-moi simplement indiquer ces paramètres comme ceci. Et ce que nous allons faire est de vérifier une fois que nous atteignons un total de 0, cela signifie que nous avons consommé tout ce nombre. Nous avons un total de 0, alors c'est bon. On peut en retourner un. Puisque c'est comme un cas de base. Par exemple, ici, si nous arrivons au total de 0, qui est cinq plus quatre, est égal à neuf, alors le total de ceci restera ou sera 0 dans ce cas, puisque nous allons décrémenter neuf par cinq, puis décrémenté par quatre, nous allons obtenir un total ici, qui est égal à 0. Ce que nous allons faire, c'est de nous arrêter ici et d'augmenter notre fonction. Alors laissez-moi juste le nommer récursivité. Alors nommez-le se reproduire. Et dans ce cas, si le total est égal à 0, cela signifie que nous avons pu arriver à un sous-ensemble qui additionne jusqu'à neuf. Et cette affaire, ce que nous allons faire pour simplement en retourner un. Maintenant, pensons si le total est inférieur à 0 dans ce cas, comme cet exemple, ou peut-être celui-ci ici. D' accord, donc nous n'avons traité aucun point où le total est inférieur à 0 autre que celui-ci. Donc peut-être que nous allons juste prendre ce 5 plus 4, qui est égal à neuf plus trois, ce qui est égal à 12. Et ce cas, si le total est inférieur à 0, alors ce que nous allons faire est de simplement retourner 0. Donc, si le total est inférieur à 0, nous ne pouvons pas retourner 0. Maintenant gardez à l'esprit, nous voulons, en fait arriver à ce point. Nous pourrions arriver à un point où le total est inférieur à 0 et d'autres cas où 54 ne sont pas sous-ensemble d'un sous-ensemble possible. Donc par exemple, peut-être qu'on a un autre sexe ici et qu'on a 6 plus 5. Plus 6 plus 5 est en fait 11 et c'est plus grand que quatre, plus que neuf, je suis désolé. Donc, dans ce cas, nous allons retourner 0. Alors c'est tout. C' est pour le deuxième cas de base. Passons maintenant au troisième cas de base, qui est si nous arrivons à un point où nous avons atteint l'indice minimum dans avoir l'indice est inférieur à 0, I inférieur à 0. Ce que nous allons faire est de simplement retourner 0, ce qui indique que nous avons atteint le plus à gauche de notre tableau. Et dans ce cas, nous n'avons pas trouvé de sous-ensemble pouvant additionner jusqu'à neuf. Donc, si j'ai moins de 0, retournez simplement 0. Donc c'est tout pour les cas de base. Maintenant, nous pouvons commencer avec notre fonction de récursion. Donc ce que je vais faire, c'est de les placer juste ici. Et celui-ci aussi, je vais les placer comme son héritier. Et maintenant passons à la deuxième partie ou la partie amusante juste ici. C' est la récursivité en fait. Donc maintenant ce que nous allons faire est de vérifier comme je le ferai, total est inférieur à un nombre spécifique. Donc, par exemple, si nous sommes à ce numéro quatre, d'accord, alors ce que nous allons faire est de vérifier si le total qui nous reste, soit neuf moins cinq, soit quatre, est inférieur à ce nombre. Si c'est le cas, on ne peut pas en ajouter quatre. Cependant, quatre ne sont pas moins de quatre, il est en fait égal. Nous pouvons donc inclure une tendance ici. Nous avons donc deux affaires. Le premier est si ce nombre est inférieur à quatre, donc n est inférieur au nombre que nous avons au total. Laisse-moi juste l'écrire et ensuite l'expliquer plus loin. Donc, si le nombre total que nous avons laissé est inférieur au nombre réel dans cette liste, il est donc inférieur à la liste à un index spécifique I. Et c'est le cas. Cela signifie que nous pouvons additionner notre, nous pouvons ajouter ce numéro 4 à notre liste ou à notre sous-ensemble. Ce que nous allons faire, c'est simplement déplacer la flèche dans les autres éléments. Comment faites-vous ça ? Nous retournons simplement la même fonction. Alors. Récursivité dans la liste. Le même total puisque nous n'avons pas utilisé ce total et je moins1 indiquant que nous n'avons plus besoin de cela pour plus. Maintenant, si ce n'est pas le cas, ce que nous allons faire est de retourner deux choses. La première chose est que nous ajoutons ceci pour la seconde est que nous ne l'ajoutons pas comme nous l'avons dit ici. Donc, par exemple, si vous êtes à ce moment précis où nous avons cinq et ensuite nous sommes arrivés à l'index qui est à cet élément pour ce que nous allons faire est abord ajouté et puis juste garder la liste telle qu'elle est. Et ce que nous allons faire est d'obtenir les sous-ensembles possibles de cette partie de l'arbre et tous les sous-ensembles possibles à partir de ce k. positif puis les ajouter, les ajouter et obtenir tous les sous-ensembles possibles. Dans ce cas, nous en avons un. Donc nous en avons un ici et nous en avons un ici. Ce que nous allons faire est d'ajouter un plus un et cela prendra deux. Et puis nous allons revenir à la valeur finale de qualité possible que nous avons. Alors comment on fait ça ? Nous allons prendre aux fonctions de récursion et les ajouter ensemble. La première est que nous incluons ces quatre et la seconde est juste que nous donnons la liste telle qu'elle est. Donc ce qu'on va faire, c'est que je suis désolé, on peut juste dire autre chose. Mais nous allons faire, c'est rendre deux choses. C' est la récursivité de cette liste. La première fois que nous allons l'inclure, nous allons juste décréter du total. Donc nous allons décrémenter la liste chez moi et juste aussi décrémenter notre compteur. Donc ce que vous allez faire est de l'inclure et ensuite aller à ces trois ici. Et nous allons faire exactement la même chose à tous les éléments ici. Donc c'est le premier et nous allons l'ajouter à la même récursivité. Cependant, cette fois, nous allons garder la liste ajouter est, comment ferons-nous ça ? Nous retournons simplement total au lieu de décrémenté par cet élément. Donc nous allons donner cinq, ce qui est neuf moins un, total restera pour, et cette affaire, nous allons aussi décrémenté. Donc c'est fondamentalement notre formule. Maintenant, si vous y pensez, ce que nous allons dire, c'est que nous allons passer en revue toute cette liste de droite à gauche. Et puis nous allons vérifier si l'un des cas de base s'applique. Si c'est le cas, nous allons retourner le numéro correspondant approprié. Donc, si le total est égal à 0, comme ce cas, ce que nous allons retourner est un. Sinon, vous ne pouvez pas retourner 0. Maintenant pour la récursivité, récursivité, mais nous allons faire est de vérifier si notre total est inférieur au total ici, l'élément juste ici. Supposons donc que nous ayons un total de trois et que nous ayons le numéro quatre. Donc, il n'y a aucun moyen que nous puissions ajouter quoi que ce soit à la forme qui puisse compenser ce total trois parce que trois, c'est moins de quatre. Donc, ce que nous allons faire est simplement de déplacer cet index ou cette flèche dans celui qui l'précède. C' est ce qu'on a fait ici. Et si ce n'est pas le cas, si nous pouvons juste mettre ça pour notre set. Mais nous allons faire, c'est d'ajouter deux choses et l'une à l'autre. Le premier qui fait effectivement inclus dans notre ensemble, et le second est de simplement garder l'ensemble tel qu'il est. Et puis nous allons voir les chiffres réels d'ici et d'ici et les additionner. Nous allons obtenir le numéro final en utilisant cette méthode de récursion. Donc c'est tout pour ce problème. Maintenant, ce que nous allons faire dans la prochaine vidéo est d'essayer de l'optimiser en utilisant la programmation dynamique et la mémorisation. Alors, à vous voir. 28. Solution améliorée du nombre de sous-ensembles: Très bien, donc dans cette vidéo, nous allons essayer d'optimiser notre solution pour cela. Trouver le nombre de sous-ensembles qui peuvent s'adapter à un problème de nombre spécifique. Donc, le principal inconvénient de notre solution récursive est que nous allons appeler la même fonction récursive et récursive encore et encore. Et pourquoi c'est ça ? Parce que pense à ça. Si nous sommes au numéro précis, par exemple, ici à seulement cinq ans, ce que nous allons faire est de l'appeler encore une fois pour 54, puis de l'appeler une fois de plus, 45403. Donc, ce que nous faisons, c'est que nous allons ajouter ces quatre ici. Alors on va l'ajouter ici. Et puis bien sûr, nous allons l'ajouter à chaque fois que nous allons passer par celui-ci, par exemple, ces trois, nous allons être appelés ici, ici. Et puis nous avons le Dr Chris de gauche. Et dans ce cas, il va être appelé maintes et maintes fois. Donc, ce que nous allons faire est de stocker ces valeurs dans peut-être une liste, un dictionnaire de hashmap, tout ce que nous pouvons résoudre avec. Et ce que nous allons faire est à chaque fois que nous allons exécuter cette fonction ou l'appeler, nous allons vérifier si ce paramètre spécifique ou ces paramètres spécifiques sont effectivement inclus dans la liste. Donc, si c'est le cas, nous les avons déjà inclus et nous avons déjà calculé le nombre de sous-ensembles. Et dans ce cas, nous n'avons pas vraiment besoin de le revoir. Donc, une façon de le faire est, par exemple, si nous sommes ici et que nous en avons ajouté cinq, alors nous avons ajouté pour les trois envahis. Dans ce cas, lorsque nous ajoutons ces trois ici, ce que nous allons faire est de les ajouter à la liste, par exemple. Et puis à chaque fois que nous appelons ceci 3, par exemple, ici, si c'est en fait les trois étaient dans la liste, alors nous avons déjà calculé le nombre de sous-ensembles, alors nous n'avons pas vraiment besoin de le calculer à nouveau. Et c'est, cela nous permettra d'économiser beaucoup de temps. Parce que par exemple, si nous ajoutons, par exemple, si vous êtes ici et que nous sommes prêts, nous découvrons que nous l'avons déjà fait. Ce que nous allons faire, c'est simplement ignorer le reste de l'arbre qui est ici. Donc, pour commencer, nous devons tout d'abord définir un nouveau paramètre à l'intérieur de notre fonction, c'est-à-dire le HashMap réel ou la liste que nous allons utiliser. Dans ce cas, je vais simplement le nommer ici et le nommer comme mémorisation. Donc, je le nomme mémo. Donc, ce que nous allons faire est de créer une clé et une valeur et de les stocker dans ce mémo. Donc, ce sera soit un dictionnaire ou un HashMap qui inclut une clé et une valeur. Donc, ce que nous allons faire est de stocker la clé comme le total et le sous-total de l'indice. Et allons-nous trouver un moyen de les trier dans la clé ? Et la valeur devrait être le nombre de sous-ensembles que nous pouvons avoir un donné ce nombre spécifique. Supposons qu'on ajoute à celui-ci. Ce qu'on va faire, c'est stocker une clé pour ça. Et bien sûr, nous allons stocker à la valeur, par exemple, qui est 0 pour cela parce que nous n'avons pas vraiment obtenu cela et neuf du sous-ensemble. Donc, pour ce faire , nous allons commencer par construire notre mémo au point précis. Donc, si nous appelons cette fonction, nous allons faire est de construire la clé au début. Et la clé, ce que je vais utiliser comme une chaîne. Donc, je vais utiliser une chaîne. De plus, je vais stocker la virgule totale, l'œil, qui est l'index. Donc, dans le schéma devrait être comme le, donc par exemple, ce que nous allons avoir à l'intérieur de cette clé est un. Supposons que nous soyons à ce point qui est ici, ce que nous allons obtenir est neuf moins cinq, donc le total est quatre. Donc nous allons stocker quatre, venir et l'index est 0, 1 à l'index est deux. Donc c'est notre clé. Et notre valeur devrait être en fait le nombre de sous-ensembles que nous pouvons faire dire à ce point donné. Et comment pouvons-nous calculer ? Et ça remontera tout le chemin à ce numéro, spécifique numéro un. Et puis c'est ainsi que fonctionne la récursivité. Donc, ce que nous allons faire est de vérifier au début, si cette clé est réellement dans notre mémo, alors nous avons déjà calculé. Donc nous n'avons pas vraiment besoin de le revoir, alors nous le rendons simplement. Donc, pour ce faire, nous allons simplement ajouter ici si la clé, alors laissez-moi juste rendre cela un peu plus petit. Et ce qu'on va faire, c'est vérifier si la clé est un mémo. Mais nous allons faire est simplement de retourner la valeur à l'intérieur du schéma, à l'intérieur du mémo. Donc, renvoyez le mémo à la clé spécifique que nous avons créée. Maintenant, si ce n'est pas le cas, alors nous continuons, nous allons continuer notre fonction récursive. Cependant, ce que nous allons faire ici, c'est au lieu de les retourner tout de suite, nous allons simplement les stocker dans une valeur et je vais le nommer pour retourner. Nous allons donc les stocker dans un retour à deux, ce qui est une variable simple. Et puis avant de les retourner, nous allons les stocker dans le mémo. Alors comment on fait ça ? Nous continuons à écrire le code ici. Donc on va stocker dans ce mémo, à la clé. Nous allons stocker ce que nous avons, donc nous allons le stocker pour revenir. Et après cela, nous pouvons simplement revenir. Alors revenez à revenir. Donc, c'est essentiellement maintenant ce que nous avons fait, c'est que nous construisons une clé. Ensuite, nous vérifions si notre valeur ou ce que nous visons à faire est déjà dans le mémo. Si c'est le cas, alors nous le retournons simplement. Que ce n'est pas le cas, nous allons le calculer. Et puis bien sûr, ajouté à notre mémo que avant de le retourner à nouveau. Alors c'est tout. Fondamentalement, c'est ce que vous devez faire. Et cela nous fera gagner beaucoup plus de temps et cela diminuera beaucoup la complexité parce que nous ne l'avons pas fait, nous n'appelons pas vraiment la même fonction encore et encore. Maintenant, en ce qui concerne l'exécution réelle de ce problème, Pensez-y. Donc, pour tous ces cas de base, l'exécution réelle est O d'un. Donc nous ne nous soucions pas vraiment d'eux. Quant à celle-ci, nous avons ici les fonctions que nous appelons ici et nous venons l'écrire. Donc c'est un ou deux. Maintenant, nous allons prendre pour acquis que nous allons rencontrer Stan. Donc ce qu'on va faire, c'est vérifier combien d'appels on passe ? Et la vraie solution ? Ou la réponse est assez simple parce que nous utilisons ce mémo, donc pas beaucoup d'appels. Alors réfléchissons à ça. Mais nous appelons en fait que chaque fois qu'on décrémente par liste I, je suis désolé, chaque fois qu'on décrémente par I moins un. Et dans ce cas, on va l'appeler le numéro. Il indique le nombre total de fois le nombre réel d'éléments dans cette liste. Alors pourquoi on a fait ça ? Alors pensons à ça de cette façon. Le nombre de causes potentielles que nous venons à faire est lié au total et n. Parce que rappelez-vous que nous avons une liste par opposition aux temps. C' est l'indice 0 et tout le chemin jusqu'à 0123. Donc, ce que nous allons faire est d'avoir la clé et la valeur en fonction de cela. Donc, la clé est en fait ce que nous avons fait ici, qui est le total plus l'œil. Donc, il est juste de supposer que nous avons n fois pour l'œil parce que annuel grand, Je vais aller de 0 à trois. Donc nous en avons quatre et le total sera en fait, si, supposons que nous en avons neuf, ce sera en fait neuf fois quatre possibilités que nous pouvons obtenir cette paire de valeur clé. Et dans ce cas, c'est le nombre total de fois N. et nous allons supposer le pire cas où nous allons l'appeler deux fois. Donc on va le multiplier par deux. Et c'est notre runtime qui est quatre. Maintenant, nous pouvons toujours supprimer cette constante et nous allons obtenir 0 du total des temps. Et donc c'est essentiellement pour ce problème. Maintenant, dans les prochaines vidéos, nous allons les mettre en œuvre étaient dans les langues que nous devons vous voir. 29. Nombre de sous-ensembles Java: Très bien, donc dans cette vidéo, nous allons implémenter notre fonction en utilisant Java. Donc, la première chose que je vais faire est de créer une fonction avec les quatre paramètres dont nous avons parlé. Donc je vais juste le nommer comme on l'a dit. Ou dans ce cas, peut-être que vous pouvez le changer en mémos. Bon, donc je vais le garder pour l'instant. Si public, statique. Et cela devrait retourner un entier et il se reproduira. Et les paramètres du Parlement sont la liste que nous avons, le total, l'œil et le mémo. Et bien sûr, notre liste devrait être dans un ArrayList ou moins. Je vais aller avec, je suis désolé, soit une liste de tableaux ou un tableau. Je vais aller avec une liste de tableaux. Donc liste de tableau. Et il sera de type entier dans ce cas. Ensuite, il y a notre liste. Le total doit être un nombre, la fin, aussi un nombre à un entier. Et enfin ici, nous avons la carte de hachage dans ce cas. Et il faudra une clé et une valeur. Donc alkene sera une chaîne et la valeur réelle sera un entier. Donc c'est tout maintenant que nous pouvons commencer avec notre code. Ce que nous allons faire au début, c'est vérifier, comme nous l'avons dit, nous allons construire la clé et vérifier si ces souvenirs réels et notre démo à moins d'être appelé. Alors, comment faites-vous ça ? Nous ne pouvons tout simplement pas construire la clé au début. Laisse-moi juste me débarrasser de ça. Retourne 0. Et nous avons, ce que vous allez faire est de construire forces clés de la force k égale à la chaîne du total plus la virgule plus le nombre réel I, qui a l'index. Maintenant, cette clé est en fait dans notre mémo. Nous allons le retourner jamais écrit sa valeur de notre mémo. Et comment le vérifions-nous ? Nous allons utiliser le mémo qui contient la méthode clé. Et dans ce cas, si c'est vrai, nous allons simplement retourner le mémo à la clé spécifique. Et je suis désolé, il faut qu'on note ça. Prends la porte spécifique. Ce n'est pas le cas. Ce que nous allons faire est de vérifier si le total est égal à 0. Et ce cas, ce que nous allons faire est simplement de retourner 0. Nous allons donc vérifier si le total est égal à 0. Je suis désolé, nous devons retourner un indiquant que nous avons trouvé une liste ou un sous-ensemble qui peut s'adapter au nombre spécifique. Maintenant, si le total est inférieur à 0, mais nous n'avons pas à faire est de simplement retourner 0, indiquant que nous n'avons pas trouvé de montant ou moins qui peut additionner jusqu'à neuf. C' est plus grand que neuf. Maintenant, l'index I est inférieur à 0 retournera également 0. Et enfin, nous pouvons commencer par nos fonctions de récursion ou cause de récursion. Et le premier est de vérifier si le total est inférieur cette liste à un index spécifique qui est i. Si c'est le cas, alors nous ne pouvons pas l'inclure. Nous allons simplement sauter par un index. Et comment on fait ça ? Nous allons le stocker dans une variable. Alors laissez-moi commencer par créer cette variable ici. Donc, c'est un entier à retourner et il sera initialisé en zéros d'abord. Maintenant, ce que nous allons faire est d'assigner, de revenir dans cette fonction récursive. Et il faudra les paramètres suivants. Le premier est le total de la liste, puis je moins 10, puis mémo. Et enfin, une fois qu'on va faire, c'est vérifier ou c'est la dernière condition. Donc, nous n'avons pas vraiment besoin de vérifier qui sont ensuite ajoutés au retour. Alors revenez, ça devrait être l'une des deux choses. C' est soit la liste avec le numéro spécifique sur la liste sans elle. Donc, avec total I minus1 mémo plus liste de récursivité avec total moins le moins à l'œil spécifique. Et puis on va faire la même chose I moins 1 et mémo. Maintenant, avant de retourner ça pour revenir d'ici ou d'ici, ce que nous allons faire est de le stocker dans notre mémo. Alors, comment faites-vous ça ? On va écrire des mémos. Et puis nous allons mettre à l'intérieur de ce mémo, cette clé, et la valeur est en fait de retourner. Maintenant, enfin, nous pouvons simplement retourner notre entier de retour, qui est le nombre de sous-ensembles, mais vous pouvez utiliser. Donc c'est tout fondamentalement pour cette fonction. Maintenant, ce que nous allons faire est de construire le froid, la fonction principale où nous allons appeler, appelé celui-ci et obtenir notre résultat. Alors comment on fait ça ? Je vais simplement créer une fonction principale. Je suis désolé. Alors créons à nouveau. Et dans notre fonction principale, ce que nous allons faire est de créer un HashMap. Et il faudra une chaîne et un entier, et ce sera notre mémo pour être égal à nouveau HashMap. Maintenant, ce que nous allons faire est de créer notre liste qui inclut l'exemple que nous avons fait. Donc, je vais écrire une liste de tableau, et ce sera ajouter un entier. Et puis nous allons le nommer listes, ce qui est égal à une nouvelle liste de tableaux. Et je vais ajouter quelques choses. Alors listez ça. Je vais ajouter les mêmes chiffres exacts ici pour vérifier si nous obtenons le même résultat exact. Donc 1345. Donc je vais simplement ajouter 1345. Alors ce que nous allons faire, c'est d'avoir notre total. Donc, pour être un entier appelé total, pour être égal au total que nous avons besoin de choisir ce fondamentalement neuf. Et enfin ce que nous, enfin, quand j'ai comme index que nous allons commencer, qui est i, il sera égal à la liste, cette taille moins un. Donc, c'est essentiellement pour nos paramètres maintenant, nous pouvons appeler notre fonction récursive et l'imprimer. Donc, et il suffit de l'imprimer directement. Alors répétez à une liste spécifique, total I et mémo. Et après ça, nous allons exécuter notre code. Et voyons ce qu'on va obtenir pour un alcaloïde. Et nous allons en obtenir deux comme valeur finale ou le nombre final de sous-ensembles que nous pouvons utiliser pour un nombre spécifique qui est 9. Donc c'est essentiellement pour la mémoisation, qui est en fait la récursion sans répétition. Comme nous pouvons le voir, nous avons utilisé exactement la même logique de récursion. Cependant, nous n'avions pas vraiment besoin de calculer chaque fois que nous avons besoin d'une valeur spécifique, nous pouvons les stocker dans un tableau et ensuite, bien sûr, revenir à eux plus tard quand nous devons les utiliser. Et cela permettra d' économiser, de nous faire économiser beaucoup de temps, et cela diminuera beaucoup la complexité. Donc c'est tout pour ce qu'on appelle pas à pas. On se voit dans la vidéo suivante. 30. Nombre de sous-ensembles avec JavaScript: Très bien, donc dans cette vidéo, nous allons implémenter une fonction en utilisant JavaScript. Commençons donc par définir notre fonction. Donc je vais le nommer recur, comme nous l'avons dit. Il faudra une liste et vous aurez le total, nous avons l'indice et le mammifère que nous allons utiliser. Maintenant, ouvrons-le. Et la première chose que je vais faire est de créer notre clé. Et ce sera une chaîne. Donc je vais simplement ajouter la perte totale, cette virgule plus I. Maintenant, ce que nous allons faire est de vérifier si cette clé est dans notre mémo. Alors, comment ferais-tu ça ? Nous pouvons simplement utiliser la fonction. Si ce mémo qui a la clé spécifique, c'est le cas, alors ce que nous allons faire est simplement retourner le mémo dans ce cas spécifique. Alors comment on fait ça ? On va prendre un mémo qui arrive à la clé spécifique. Et puis nous allons faire est de simplement continuer avec notre code. Donc, comme nous avons la fonction récursive, à l'intérieur de celui-ci, nous avons le total qui est égal à 0. Donc, si total est égal à 0, alors nous ne pouvons tout simplement pas l'ignorer et retourner simplement un comme valeur de retour. Parce que cela signifie que nous sommes arrivés à un point où nous avons découvert que nous avons un sous-ensemble qui renvoie un total de 0, ce qui a atteint notre objectif en premier lieu. Donc, dans ce cas, nous allons retourner 0. Sinon, si le total est inférieur à 0, cela signifie que dans une forme, il retournera 0. Et puis ce que nous allons faire est de vérifier si j'ai moins de 0, alors il renvoie aussi 0. Maintenant, nous pouvons commencer avec nos fonctions récursives. Donc, si le total est inférieur à cette liste à un index spécifique I. Dans ce cas, ce que nous allons faire est simplement de retourner la fonction recur comme nous l'avons dit, et ignorer, nous aurons total I moins1 et mémo. Et il n'y a pas une raison pour laquelle je moin1 est que, comme nous l'avons dit précédemment, nous allons simplement sauter. Parce que si, par exemple, nous avons la liste à i qui est égale à 4, et nous avons le total qui est égal à deux. Et dans ce cas, le total est inférieur à cette valeur ici. Donc, nous pouvons vraiment mettre cette valeur dans le sous-ensemble. Donc on va juste l'ignorer. Donc, c'est la raison pour laquelle maintenant ce que nous allons faire est de simplement retourner une étape définissante, recurer à moins total I minus1 mémo plus la récursion ajouter moins total moins B. Liste à i minus1 lampes sont à I. Et puis nous allons pour le décrémenter je moin1 et mammifère. Ce qu'il n'y a pas que nous ayons fait ça ici c'est parce que nous allons revenir les deux dernières fois. Le premier est que nous incluons le 5. Par exemple, si vous avez cinq ans, si nous incluons les quatre et le second, si nous ne l'incluons pas. Donc c'est ce que nous allons faire. Nous allons simplement retourner le tout dangereux. Cela signifie que nous n'avons pas inclus les quatre, et cela signifie que nous avons inclus les quatre ici. Donc c'est ça fondamentalement maintenant ce que nous allons faire est de changer cela en une variable. Donc, au lieu de taper pour retourner, je vais nommer une variable ici pour revenir et ce sera égal à 0. Ensuite, dans ce cas, retourner devrait être égal à cette fonction. Et bien sûr, nous allons faire exactement la même chose ici. Il devrait être égal à cela. Et enfin, avant de revenir à cette variable, je vais la stocker dans Zion dans ce mémo, vais utiliser un mémo qui dit, et je vais le définir à ce gamin va définir la variable de retour et ensuite je vais juste renvoyez-le. Donc, fondamentalement, pour cette fonction maintenant, ce que nous allons faire est simplement de l'essayer. Donc je vais avoir une liste de 1345 et nous en avons un total de neuf. Et nous avons le I, qui est égal à trois dans ce cas. Et puis nous avons notre mémo avec le jazz et la nouvelle carte. Donc carte mémoire, et nous sommes bons. Donc ce sont toutes des variables, alors laissez-moi juste placer une barre. Et on est bons. C' est aussi variable. Maintenant, ce que nous allons faire est d'appeler cette fonction. Je vais avoir le résultat variable. Notez que pour moi, appelez cette fonction avec ces paramètres, donc le total et la mémoire. Et enfin, je vais juste le déconnecter. Console consigne donc les résultats que nous avons. Maintenant, si nous allons ici et tapez le nombre de nœuds de façons que JS, qui puis-je obtenir tel que défini par le nombre de façons que nous pouvons avoir pour atteindre ce neuf ou la valeur spécifique que nous avons. Donc, c'est tout pour l'implémentation du nombre de façons utilisant la mémoisation et JavaScript. se voit dans la vidéo suivante. 31. Nombre de sous-ensembles Python: Très bien, donc dans cette vidéo, nous allons implémenter notre fonction en utilisant Python. Donc la première chose que je vais faire est de créer notre fonction et de la nommer. Préparez. Comme nous l'avons dit, nous prendrons les paramètres suivants. Le premier est la liste. Ensuite, nous allons avoir l'index profond total réel et le mémo qui sera le HashMap que nous utilisons ou le dictionnaire dans ce cas. Donc la première chose que je vais faire est de créer réellement la clé que nous allons utiliser. C' est l'index total des virgules. Alors comment on fait ça ? Je vais simplement le nommer une clé. Et je vais simplement écrire STR du total plus devenir un indice plus I. Donc STR acti. Et puis ce qu'on va faire, c'est vérifier si c'est dans le dictionnaire. Si c'est un mémo, donc la clé F et le mémo, ce cas. Ensuite, ce que nous allons faire est simplement de retourner le mémo au mémo de retour iso spécifique, la clé spécifique et nous en avons fini. Ce n'est pas le cas. Ce que nous allons faire, c'est simplement vérifier les autres cas de base. Donc, le premier cas de base, si nous avons réellement réussi et atteint le point où le total est égal à 0, nous allons retourner un parce que nous sommes partis où nous avons un sous-ensemble qui peut additionner le nombre spécifique. Maintenant, si le total est inférieur à 0, alors nous n'avons pas atteint un point où nous avons un sous-ensemble qui additionne jusqu'à 0, alors nous allons retourner 0. Sinon, nous pouvons aussi, nous devons également vérifier l'IA, c'est moins de 0. Ensuite, nous allons retourner aussi 0, indiquant alors nous ne parvenons pas à trouver un sous-ensemble dans cette branche de cet arbre que nous construisons. Maintenant, nous pouvons commencer par notre fonction récursive. Fonctions. Et le premier est de vérifier si le total est inférieur à l'index de la valeur qui à la fin sauf que nous ajoutons, si c'est le cas, alors ce que nous allons faire est de retourner une fonction récursive sans l'index spécifique. Rappelez-vous donc que si nous sommes, par exemple, à quatre et notre total est deux, dans ce cas, le score est supérieur à 2 dit que cela signifie que nous ne pouvons pas ajouter ces quatre dans notre sous-ensemble afin d'avoir le total que nous visons à avoir. Dans ce cas, ce que nous allons faire est simplement de retourner ce total moins I moins 1 avec notre mémo. Alors, comment faites-vous ça ? Nous me laissons simplement simplement créer une variable ici. Et cette variable devrait être initialisée par 0. Et puis nous allons ajouter au retour qui sera égal aux fonctions récursives que nous utilisons la liste fille I, minus1 et mammifères. Alors si ce n'est pas le cas, alors cela nous laissera avec deux. Parce que, bien sûr, le premier est de quitter la liste telle qu'elle est, suffit de décrémenter l'index d'un. Et l'autre est de simplement prendre la liste et de décrémenter le total par la liste à la spécifique. Je suis désolé, j'ai oublié soit t Maintenant je moins1 et mammifères. Donc, ce que nous disons ici en fait, c'est que nous allons juste l'utiliser pour une fois et l'ignorer la deuxième fois. Et c'est ce que nous faisons en fait ici, par exemple, ici nous allons ajouter ces quatre au sous-ensemble. Et il ne va pas l'ajouter en allant simplement retourner le sous-ensemble ou le rappeler sans avant. Et on en verra un. C' est commun sur plus tard. Donc c'est le fondamentalement pour notre fonction. Enfin, ce que nous devons faire, c'est simplement l'ajouter à notre mémo. Donc mémo à cette jauge est égal à retour. Et enfin notre retour. Maintenant, essayons-le. Ce que je vais faire, c'est créer notre liste, ce qui est exactement la même chose que nous avons construite ici, 1345. Alors liste à 1345, puis on en aura un total de neuf. Et nous allons aussi avoir l'indice qui est un trois. Ça va commencer par le dernier élément, qui a été trois en plus. Ensuite, nous allons avoir le mémo, qui est fondamentalement un dictionnaire. Maintenant, nous pouvons appeler notre fonction, je vais le stocker dans un résultat et l'appeler résultat, qui va être une récursion moins totale et mammifère, alors vous pouvez simplement les imprimer. Donc maintenant, si nous allons de l'avant et nous dirigeons vers CMD, allez sur le bureau. Et puis par programmation dynamique. Et puis je vais simplement exécuter ce code python nombre de façons que je vais obtenir un désordre. Nous avons donc une erreur de syntaxe non valide. Et c'est en fait parce que nous avons oublié d'ajouter la colonne ici et de les mettre fin aux critères. Donc maintenant, si nous revenons et retournons nombre de façons, désolé, donc ici nous avons des annonces. Alors c'est tout. Maintenant, nous pouvons revenir en arrière et nous avons obtenu deux comme le nombre de façons que nous pouvons avoir aussi des sous-ensembles qui peuvent additionner jusqu'au nombre spécifique neuf. C' est donc le fondamentalement pour cette implémentation de ce problème en utilisant Python pour vous voir dans la vidéo suivante. 32. Sous-séquence commune: Bonjour et bienvenue. Dans cette vidéo, nous allons discuter du problème de la plus longue sous-quence commune dans la force S2. Donc, ce que nous allons avoir en fait, c'est de la force et nous les écrivons juste là-bas. Donc nous allons avoir x, y, z, w. Et puis l'autre sera x, le a w. Maintenant, à la réponse de ceci est en fait la longueur de la plus longue sous-séquence commune. Dans ce cas, il est égal à trois. Comment on l'a eu ? Nous avons x z w, x z, W. Donc, comme nous pouvons le voir, x, z et w est la plus longue sous-séquence commune à l'intérieur de ces deux chaînes. Et nous pourrions avoir des lettres entre eux, mais l'ordre est le même, donc nous avons hache que Z et W. Alors comment résoudre ce problème ? En fait, notre première pensée que nous allions en récursivité puisque nous devons trouver les moyens possibles ou les combinaisons possibles que nous pourrions avoir une sous-chaîne de chaque sous-chaîne. Et puis nous allons vérifier que cette sous-chaîne correspond à l'autre extrémité, la deuxième chaîne. Et si les matchs allaient trouver sa longueur et ensuite simplement le retourner comme résultat. Et bien sûr, nous allons trouver la longueur maximale que nous pouvons avoir à l'intérieur de ces deux cordes. Alors, comment résoudre ce problème en utilisant seulement le papier ? Ce qu'on va faire, c'est vérifier si les deux dernières lettres sont égales. Si c'est le cas, comme vous pouvez le voir, W est égal à W, mais nous allons simplement les retirer de nos forces et nous allons incrémenter notre compteur d'un. Donc nous en avons un. Bon, donc maintenant ce qu'il nous reste est en fait x, y, et z, et la première chaîne et Ax et Ay et l'autre. Maintenant, si vous voulez comparer les deux derniers caractères, nous pouvons voir qu'ils ne correspondent pas. Ce que nous allons faire est de l'essayer avec deux façons possibles. La première façon est d'éliminer ce vertige et de continuer notre solution en utilisant x, y et t de première main et B x, z et a d'autre part. Et puis on va faire la même chose. Cependant, maintenant nous allons nous débarrasser de a, donc nous allons rester avec x, y, z, et z. Maintenant, si vous suivez ce chemin, comme vous pouvez le voir, nous avons x, y, z, et a. Et ce cas, nous allons continuer avec x et z et a, et l'autre solution devrait être x, y, et le x. donc la première fois que nous allons supprimer le y et l'autre nous allons supprimer un. Maintenant, rappelez-vous que nous devons trouver un titre spécifique c'est à la fin de ces deux volets et a devrait être égal. Maintenant, dans ce cas, si nous continuons ici, nous allons finir avec x et x à une extrémité. Et cette affaire nous en avons trouvé une qui correspond. Donc ce que nous allons faire, c'est d'incrémenter notre compteur ici. Et bien sûr, si nous continuons, Hey, nous allons aussi finir avec X et X. Donc maintenant, nous avons 11. Ce que nous allons faire en fait, c'est de vérifier à ce stade, par exemple. Supposons que nous soyons ici. Ce que nous allons faire est de vérifier le maximum entre les sous-arbres gauche et droit. Et ce cas, ils sont égaux, donc nous allons juste retourner un 1. Maintenant, nous allons faire exactement la même chose à ce poste. Cependant, nous n'avons pas encore terminé cette branche. Laisse-moi finir. On va continuer ici. Nous avons x, y, z et z. Ils sont égaux. Ce que nous allons faire est simplement d'enlever ces étourdissements du foin et d'incrémenter le compteur d'un. Et bien sûr, nous allons finir avec x, y, et x sur le premier, et nous allons avoir x et x. et d'un autre côté, je suis désolé, laissez-moi juste les supprimer. Donc nous allons avoir une fois, x et x la deuxième fois, que d'avoir XY et rien. Et chaque fois que nous n'avons rien ou une chaîne vide, nous allons juste retourner 0 puisque nous venons d'aller dans un endroit où il n'y a plus de chaîne ou de caractères. Et l'une des forces, donc nous allons juste retourner 0, indiquant que nous n'avons rien trouvé jusqu'à ce que nous ayons X et X. Ils sont égaux, donc nous devrions tenir sur un. Donc, si nous sommes à cette position, x, y et x, nous allons juste prendre le maximum entre ces deux forces et il est en fait égal à un. Donc nous en avons un. Et si nous sommes à cette phase, X, Y et Z, nous allons retourner le maximum entre celui en dessous, qui est en fait juste x, y et ajoute, et nous allons en avoir un. Donc, 1 plus 1 devrait être égal, devrait être égal à deux. Et dans ce cas, nous allons retourner le maximum entre ces deux branches. Donc vous en aurez un et nous en avons deux ici. Donc nous allons devoir le faire, et bien sûr, nous allons finir avec 2 plus 1, ce qui est en fait égal à trois. Alors c'est tout. Fondamentalement, c'est l'arbre que nous pouvons construire. Et ce que nous disons en fait, c'est que chaque fois que nous avons deux points forts, cela correspond ensemble. Deux caractères qui sont égaux l'un à l'autre. Mais nous allons faire, c'est simplement les supprimer et continuer notre travail. Cependant, nous avons deux étapes pour le faire. Soit on supprime juste occupé ou on a supprimé le a. Et nous allons savoir qui est à la sous-chaîne maximale ou sous-séquence qui peut être retourné en utilisant x, y, z et a, ou X, Y, Z et X, Z et l'autre cas. Et je vais juste retourner le maximum. Et bien sûr, chaque fois que nous avons deux chaînes ou deux caractères qui correspondent, nous allons l'incrémenter d'un. Donc c'est tout essentiellement pour cette solution Just, solution récursive. Et ce que nous allons faire maintenant, c'est d'écrire un pseudocode qui nous aide. Et la prochaine phase où nous allons l'optimiser. Et nous allons trouver une solution en utilisant un programme dynamique. Donc avant de faire ça, laissez-moi juste penser à la complexité temporelle ici. Si nous pensons aux combinaisons possibles dans une chaîne et en utilisant des statistiques, ce que nous allons découvrir est que si vous avez une chaîne de quatre lettres, disons X, Y, Z et W. Nous allons donc trouver les combinaisons possibles que vous pourriez prendre d'ici. Nous pouvons avoir x, X, Y, XYZ, alors nous avons y, y, z, y, w, et ainsi de suite et ainsi de suite. Et ce cas, ce que nous allons avoir est en fait une combinaison de quelques choses. Donc, par exemple, si vous avez une combinaison de seulement x, nous allons avoir une combinaison de un et c1. Et puis si vous avez deux lettres, X et Y auront et C2. Et puis NC3 jusqu'à b et c, et nous allons inclure toutes les lettres à l'intérieur de la chaîne. Donc, et cela est en fait égal à deux à la puissance n. Et comme vous pouvez le voir, Exponentiel. Maintenant, c'est juste pour calculer les combinaisons possibles dans une chaîne. Nous avons donc deux points forts. Nous devons le multiplier par deux. Et puis nous allons le multiplier par n. Et ce n est parce que nous devons calculer la sous-séquence si elle est commune dans les deux chaînes. Donc nous allons découvrir si c'est commun, les deux brins. Donc nous allons avoir de 0 tout le chemin à n. Et dans ce cas, c'est en fait à la puissance n fois n. Donc nous pouvons nous débarrasser de ces deux. Donc, la complexité du temps est et deux. Et comme vous pouvez le voir, et ce assez grand et avoir deux longues cordes, nous pouvons vraiment travailler avec elle et avoir un minimum de temps. Donc, ce que vous allez faire maintenant est d'écrire le pseudocode et ensuite nous allons trouver un moyen d'optimiser la solution. Alors laissez-moi juste me débarrasser de ceux-ci et je vais les supprimer aussi. Maintenant, ce que je vais faire est de commencer par un pseudocode. Cependant, permettez-moi juste de prendre toutes ces choses et plus petites, les mettre ici. Donc maintenant, nous pouvons commencer avec un pseudocode. Ce que nous allons faire en fait, c'est commencer par les paramètres. Donc, je vais juste nommer la fonction comme la plus longue sous-séquence commune. Et dans ce cas, il faudra quatre paramètres. Le premier est Penguin, la deuxième chaîne 2, et ensuite nous avons la position ou les indices que nous ajoutons. Donc, chaque fois que nous disons que nous allons supprimer ceci ou nous allons passer à celui-ci. Nous allons prendre un index qui indique simplement que tel ou tel, ou tout caractère spécifique à l'intérieur de ces deux brins. Donc pour S1, nous allons avoir hache et pour nous d'avoir Y et la première chose que nous allons commencer est notre cas de base. Donc, le cas de base est en fait où nous allons juste annuler et notre fonction, et ce sera en fait ce que nous avons une chaîne vide. Alors, comment trouvez-vous si vous avez une chaîne vide ? Comme nous l'avons dit, si x ou y est égal à 0, comme ce cas où nous avons X, Y, et ici nous avons une chaîne vide. Donc celui qui indique la position que nous sommes dans S2. Nous sommes donc à la position 0 ou moins un dans ce cas. Et si nous avons le, nous, si nous sommes à cette position, ce que nous allons faire est de simplement retourner 0. Donc fx égal à 0 ou y égal à 0. On va juste retourner 0. Maintenant, nous pouvons commencer par nos appels récursifs. Nous avons donc deux choses auxquelles nous devrions prêter attention. Donc f, le dernier caractère est égal. Donc, si le dernier caractère S1 à x moins un et est égal à S2 à y moins 1. C' est le cas. Alors nous allons continuer notre travail. Bien sûr, nous pouvons incrémenter notre compteur, ce qui est la chose que nous allons revenir. Donc, cela devrait être réellement écrit d'entier. Donc nous allons en retourner un. En plus, on va appeler la fonction. Cependant, nous allons juste enlever le pétrole, décrémenter nos compteurs d'un. Donc, si nous sommes à cette position, w et w vont juste décrémenter ce serait à z et a dans ce cas. Alors comment on fait ça ? Nous allons simplement retourner la plus longue sous-séquence commune à S1, S2. Comme d'habitude, cependant, nous avons x moins 1 et y moins 1. Maintenant, si ce n'est pas le cas, nous avons deux choses à choisir. Nous avons dit que nous devons calculer le maximum entre l'arbre gauche et l'arbre droit. Alors comment on fait ça ? Il suffit de retourner le maximum entre deux choses. C' est la plus longue sous-séquence commune. Donc le plus long commun sous S1, S2 x moins 1 y. Donc, le premier, nous allons juste enlever le premier et dernier caractère et la première chose. Et le second, nous allons supprimer le dernier personnage de la deuxième force, si longue sous-séquence commune. Et dans ce cas, nous allons retourner S1, S2, et ensuite nous avons x et y moins un. Laisse-moi juste les écrire ici. Donc nous avons S1, S2, et puis nous avons x et y moins un dans ce cas. Donc c'est tout pour notre solution récursive. Et comme nous pouvons le voir, cela prendra trop de temps puisque nous allons calculer la même chose encore et encore. Donc, par exemple, ici nous allons finir avec x et x, et x et x, x et x et x. Et bien sûr, vous continuerez ici. Nous allons aussi finir avec x et x. Donc, nous allons le calculer au moins quatre fois dans ce cas. Et comme nous pouvons le voir, nous allons juste calculer beaucoup de choses plusieurs fois. Donc, notre deuxième solution devrait être basée sur la programmation dynamique, et nous pouvons simplement nous débarrasser de ces calculs encore et encore. Donc, c'est tout essentiellement pour ce problème en utilisant la récursivité. Dans la prochaine vidéo, nous allons juste l'optimiser. Alors, à vous voir. 33. Pseudo-Code: Ok, donc maintenant dans cette vidéo, nous allons discuter notre implémentation de programmation dynamique du plus long problème de subquence commun. Donc, nous allons réellement utiliser la tabulation pour cette solution. Donc, ce que nous allons faire en fait est de stocker nos valeurs sont nos résultats dans un tableau 2D, puis les utiliser chaque fois que nous avons besoin de les regarder. Alors laissez-moi juste commencer par supprimer le pseudocode de la fonction passée. Et nous allons réellement faire est de créer un tableau 2D. Et je vous expliquerai pourquoi dans une seconde. Mais ce tableau 2D contiendrait nos deux chaînes. Donc, comme nous l'avons dit, nous avons x, y z et w, puis Z et W. Donc ici, nous avons des poussées allaient juste supposer que nous avons une chaîne vide. Ensuite, nous avons x, y, z, w. alors nous allons avoir une chaîne vide x, z, a, et W. Donc, ce que nous allons faire est de commencer par supposer que nous avons une chaîne vide ici et que vous avez une chaîne vide ici. Et nous allons juste obtenir la plus longue sous-séquence commune. Et dans ce cas, la plus longue sous-quence commune est une chaîne vide, qui est la longueur 0. Maintenant, si nous passons à la deuxième place ici, nous avons une chaîne vide et des actes que nous pouvons voir. La plus longue sous-quence commune que vous pouvez avoir est en fait de longueur 0 aussi. Et ici nous avons, nous allons continuer avec y et des chaînes vides à la fin de la chaîne et W et chaîne vide. Et nous allons juste le remplir avec des zéros et juste calculer la même chose ici, chaîne vide avec toutes ces lettres. Donc on va finir avec des zéros des deux côtés. Maintenant, nous allons continuer, aller à ce point où nous avons hache et hache. Et ce que nous allons réellement faire est de, si nous avons X et X, mais nous allons faire est de supprimer ce x d'ici et d'ici comme nous l'avons fait avec ce w. donc si vous avez w et w, et nous l'avons fait est de supprimer les w's puis vérifiez les x, y, z et la précision. Donc, la première fois que nous allons avoir ça, par exemple. Donc, si c'est le cas où nous avons X et X, alors nous allons juste supprimer ceci et vérifier celui qui ne contient pas le dernier caractère. Alors comment on fait ça ? Nous allons juste vérifier en diagonale, parce que si nous enlevons X d'ici et x d'ici, nous allons finir avec vide et vide, qui est ici. Nous allons donc en ajouter une à la valeur d'ici, qui est 0. Donc on va en finir avec un ici. Maintenant, nous allons continuer. Nous avons x maintenant et x, y dans ce cas. Donc, nous sommes à celui-ci, nous allons avoir x, y, et X. Donc la plus longue sous-séquence commune est en fait, selon notre règle que nous avons déjà trouvée, est que si nous avons deux caractères qui ne correspondent pas, dans ce cas, nous avons x, y et Ax. Ce qu'on va faire, c'est vérifier pour une première fois, X et X. et ensuite on a, donc il aura X, Y, et X. la première fois qu'on va retirer le fil. Et la deuxième fois, nous allons enlever le xo. Nous avons X et X et X, Y et chaîne vide. Alors comment on vient d'avoir cette information ? On va les récupérer de celui d'avant. Donc si on regarde celui avant, on va découvrir qu'on a X et X. Et si on regarde, on va découvrir qu'on a x, y, et une chaîne vide. Donc, nous allons calculer le maximum entre ces deux-là selon notre règle. Donc on en a 10, le maximum est un, donc on va le remplir avec un. On va faire exactement la même chose pour XYZ et Ax, en avoir un ici et un ici. Donc, si vous voulez passer sur ce x, y, z, et w. et donc si vous avez x, y, z, et w et x, ce que nous allons obtenir en fait, parce que les derniers caractères de ces deux chaînes ne correspondent pas. Nous allons continuer avec X, Y, Z et X. Et l'autre devrait être x, y, z, w, et une chaîne vide. Et dans ce cas, comment les regardez-vous ? Nous allons regarder à gauche et nous allons finir avec XYZ et agir comme nous pouvons le voir, c'est tout. Donc c'est 1. Et nous avons aussi x, y, z, et w, et une chaîne vide qui est en fait 0. Donc, le maximum entre eux est en fait un. Donc, il suffit d'implémenter notre groupe et de trouver ce que nous voulons à partir des calculs précédents. Maintenant, nous allons continuer avec Xy et X. Dans ce cas, ce que nous allons faire est de regarder à gauche et juste au-dessus de 0 ou un soviétique, nous allons continuer avec la même chose ici. Nous avons 1 et 1, 1, 1. Et bien sûr ici, nous avons x z et x, y, z, dans ce cas z et les allumettes. Donc, ce que nous allons faire est d'en ajouter un et de regarder celui qui est diagonale. Dans ce cas, nous en avons un et nous allons en ajouter un. Donc un plus un, on va juste en stocker deux dans ce cas au lieu d'un. Et si vous le regardez, la façon dont nous l'avons traité avant, si vous avez x, y et z. et ensuite nous avons x, z, mais nous l'avons fait est de supprimer ces z et z, nous allons finir avec x, Nous allons juste finir avec des actes et morts à la dernière étape où nous en avons ici un et là, nous allons finir avec deux comme une réponse finie. Alors comment on fait ça ? Nous regardons simplement les calculs précédents sans calculer x, y et x. Une fois de plus, nous allons juste prendre la valeur que nous avons vu a. Donc c'est 2. Et bien sûr, nous allons finir ici avec tout le SO2. Maintenant, nous avons 0 ou 1, qui est 1, 1 ou 1, 2 veulent aussi un ou deux vont finir avec 22 ou deux. Je vais juste finir avec aussi. Maintenant, nous allons aller jusqu'à la fin. Maintenant, si nous regardons cela, nous avons x, z, a, w x, y, z, et w. et dans ce cas, comme nous pouvons le voir, w et w que la même chose. Donc, nous pouvons juste ajouter 12, la diagonale, faites-le, ce qui est deux. Donc, nous allons finir avec trois comme valeur finale dans ce cas. Donc, ce que nous avons fait, c'est que nous avons utilisé la solution récursive. Cependant, nous stockons simplement notre travail, les résultats, dans ce cas tableau 2D, et nous les utilisons juste quand nous le voulions. Donc, au lieu de le calculer, chaque fois que nous voulons quelque chose, nous allons le stocker insiste tableau. Et comme nous pouvons le voir, nous pouvons l'utiliser ici, ici ou ici. Alors rappelez-vous que nous avons deux appels récursifs. Dans la solution précédente, nous avons celui s'ils correspondent, et ce cas il est diagonale et nous avons celui s'ils ne correspondent pas, nous allons prendre le maximum entre celui-ci ou celui-ci. Donc, au début, nous allons supprimer un élément de ce tableau ou cette chaîne. Et puis nous allons supprimer un élément de cette chaîne et nous allons calculer le maximum et le retourner ici. Donc, fondamentalement, pour ce problème maintenant, ce que vous allez faire est d'implémenter en utilisant un pseudo-code. Et bien sûr, nous allons l'implémenter dans nos langues. Alors faites ça, laissez-moi juste supprimer ceci et minimiser celui-ci. Et bien sûr, ce que je vais faire est de supprimer cela. Et je vais prendre tout ça et le placer ici. Maintenant, nous pouvons commencer avec un pseudocode. La première chose qu'on va faire est d'appeler une fonction. Je vais le nommer le plus longtemps. Subséquence commune comme d'habitude. Maintenant, nous allons devoir ArrayList ou tableau ou une liste. Donc, je vais juste les calculer comme juste S1 est une liste. Sauvegardez cela et se tenait comme une liste. Et bien sûr, nous allons avoir les indices auxquels nous sommes. Dans ce cas, je vais le nommer x et y. Maintenant, la première chose que nous allons faire est de construire notre matrice 2D tableau et juste nommé la plus longue sous-séquence commune, LTS. Et ce sera 2D. Et bien sûr, ce que nous allons faire est supposer que nous avons à zéros et des chaînes vides. Donc, la longueur de ceci devrait être de longueur ou de taille x plus 1. Donc x plus un, y plus 1. Maintenant, nous pouvons commencer avec nos boucles for. Nous allons le remplir ce tableau 2D. Et donc nous avons le premier à aller de 0 jusqu'à x, ou la longueur de ceci. Donc, ce sera tout le chemin jusqu'à x plus 1. Et puis nous avons I plus 1, I plus, plus, donc je de 0 à ceci. Et puis nous avons quatre j de 0 à y plus 1. Bien sûr y plus 1, l'un n'est pas inclus, ou l'autre est x plus 1. Et puis nous avons j plus. Et maintenant, nous pouvons commencer avec la solution M. Donc la première chose qu'on va faire est si i ou j est égal à 0, c'est juste les remplir avec des zéros. I égal à 0 ou j est égal à 0. Ce que nous allons faire est de remplir le LCS i, j avec 0. Ensuite, nous allons vérifier si x à une position spécifique comme égale. Dans ce cas, ce que nous allons faire est de reculer d' un et ensuite nous allons stocker la position spécifique. Alors, comment faites-vous ça ? Maintenant, rappelez-vous que nous avons S1 et S2 comme compagnon comme liste. Et ce cas, ce que nous allons avoir comme S1 car ce x, y, z, et w. S2 devrait être de x, z, a et w. Maintenant, comme vous pouvez le voir ici, nous avons l'index de cet axe est 0. Cependant, si vous voulez les calculer dans cette matrice 2D, c'est à l'index 1. Donc ici, nous avons 0, 1, 2, 3, 4. Donc, chaque fois que nous voulons travailler avec cela, nous devrions juste décréter par un seul. Donc, pour ce faire, ce que nous allons faire est de vérifier si, laissez-moi juste rendre cela plus petit un peu et juste enlever cela aussi le rendre plus petit. Et maintenant, on peut travailler. Donc la première chose qu'on va faire est de vérifier si d'autre. Ce caractère spécifique que nous sommes, ADH est en fait égal au caractère spécifique que nous avions et à la deuxième chaîne. Donc, si s1 à un x moins 1 spécifique est égal à S2 à un y spécifique moins 1. C' est le cas. Ce que nous allons faire est de remplir à LCS x, y, je suis désolé, ici nous avons I et J. Donc je et J. Et bien sûr ici, nous avons moi et J. Donc, si elles sont égales, nous allons faire est de prendre la seule. Ils vont le faire. Alors, comment faites-vous ça ? A I moins 1, j moins 1 et incrémenté d'un. Et il n'y a pas ça. Nous supposons que nous prenons la condition à un cygne I moins 1. J moins 1 est parce qu'en fait nos listes pensaient avec l'index 0. Cependant, notre matrice 2D que nous calculons d'abord pour la chaîne vide. Donc x ici est à un et il est à 0 juste ici. Alors comment on fait ça ? Nous prenons simplement I minus1, qui est si vous êtes à cet index I, qui est égal à un, et prenez juste ceci, nous allons prendre 0 moins 1, qui est 1 moins 1. On va prendre 0 et on peut obtenir ce X de la liste comme un. Donc, nous avons j moins y et dy moins un. Si c'est le cas, alors nous allons juste le calculer à partir de la position diagonale. Maintenant, si ce n'est pas le cas, nous allons finir avec la dernière chose que nous allons faire est de calculer le maximum entre deux choses. Le premier est celui en position gauche et le second est celui au-dessus. Alors comment on fait ça ? Qui va juste prendre et stocké dans le LCS i et j. Donc LCS, laissez-moi juste écrire ici. Je vais juste déplacer ça ici. Et je vais écrire que SES chez I et J égal au maximum entre deux choses. Donc, le maximum entre le LCS à I moins 1 et j tel qu'il est, ou le maximum, ou le second qui est LCS à I et j moins 1. Donc, c'est fondamentalement pour Dieu, c'est notre solution de programmation dynamique. Nous venons de calculer toutes les implémentations possibles en utilisant seulement un tableau 2D. Maintenant, si nous pensons à la complexité temporelle, si nous avons m as, nous avons x et y comme longueur de S1 et S2, et nous construisons notre matrice 2D. Donc, comme nous pouvons le voir, nous avons x, y, une complexité temporelle de notre code. Et puis notre solution devrait être la dernière et notre matrice 2D, qui est trois dans ce cas. Donc c'est tout pour ce problème. Et la prochaine vidéo, nous allons l'implémenter en utilisant nos langages. Alors, à vous voir. 34. Mise en place la plus commune: Très bien, donc dans cette vidéo, nous allons implémenter notre fonction en utilisant Java. Donc la première chose que je vais faire est de créer la fonction. Il devrait être public, statique, entier. Et je vais le nommer subquence commune, et il faudra les paramètres suivants. Le premier est un tableau appelé S1. Ensuite, nous avons un autre est d'avoir les indices x ou x et y. Donc maintenant ce que nous allons faire est de créer notre tableau 2D et il sera de taille et le nommer le long. Et dans ce cas, la longueur devrait être x plus 1 et y plus 1. Maintenant, nous pouvons commencer avec nos boucles for. Donc, comme nous l' avons dit, nous allons faire est de passer par tous ces de 0 à x et d'un 0 à y. donc pour créer une boucle for. Et dans ce cas, pour aller jusqu'au bout, ouais, qui aurait pu utiliser la taille de contenu longue ou la longueur ? Et le second serait en fait tout le chemin jusqu'à y. Maintenant, ce que nous allons faire est de vérifier si je suis égal à 0 ou j égal à 0 suppose simplement que l'Islam devrait être à I et j devrait être égal à 0. Dans ce cas, nous aurions pu juste l'ignorer parce que chaque fois que nous créons un tableau 2D à la matrice ou un tableau en Java, la valeur par défaut est en fait 0, donc nous pouvons juste ignorer cela, mais nous ferons comme notre pseudocode. Alors gardez-le juste ici. Ce n'est pas le cas. Nous allons vérifier si le S1 à I moins 1 est égal à S1 ajouter j moins 1. Donc, sinon, si S1 à I moins 1 est égal à S2 à j moins un. Si c'est le cas, ce que nous allons faire est de placer des annonces longtemps I et J, celle en diagonale. Comment faites-vous ? Je moins 1, j moins 1. Et puis on va en ajouter un. Et bien sûr, si ce n'est pas le cas, ont toujours la dernière condition, qui est de vérifier le maximum entre celui sur la gauche et celui sur ce qui précède. Donc, nous allons commencer à long terme I et J. Le maximum à. Donc math.max, le poumon à I moins un j et à long terme à I j moins 1. Alors c'est tout. Fondamentalement, c'est notre code réel. Maintenant, ce que nous allons faire est simplement de retourner la dernière valeur, qui est au X et W. Donc, après avoir terminé de ces deux boucles qui vont simplement retourner le poumon, le x et le y. Maintenant, pour l'essayer, Je vais faire est de créer une fonction principale où nous allons implémenter ou donc nos variables alors nous allons appeler la fonction. Donc, nous allons avoir S1 pour être fondamentalement égal à une liste ou un tableau de x. Puis y, je suis désolé, je vais juste les mettre en tant que caractères, donc x, y, et ensuite nous avons z et w. Z et w. Fermez-le, et nous ont S2, qui est aussi un tableau de X, Z et W. Donc x, z, et puis nous avons un et w. maintenant, nous sommes bons. Nous pouvons continuer avec les x et y réels. Donc ce sont les indices qui devraient être à. C' est donc la longueur qui est de quatre dans ce cas. Donc, les deux x et y sont égaux à 4. Maintenant, j'ai oublié de faire est d'imprimer la fonction. Donc, je vais stocker le résultat, la fonction réelle, et puis bien sûr je vais l'imprimer. Donc, je vais imprimer le résultat. Nous avons une faute de frappe, c'est w. Maintenant, si nous allons continuer et exécuter ce code, ce que nous allons faire pour obtenir un CI est trois, ce qui indique que c'est le nombre de caractères ou la longueur de sa sous-séquence que nous avons. Maintenant, pour le visualiser, ce que vous allez faire est d'imprimer simplement chaque fois que nous entrons dans cette boucle. Ensuite, j'imprime notre position. Et bien sûr, je vais avoir de l'espace ici et une ligne imprimée ici. Maintenant, si nous allons de l'avant et exécutons ce code, obtenez le même résultat exact que nous avons construit ici. Nous avons des zéros, un, deux, et le dernier est en fait trois, ce qui indique que c'est notre résultat ici. Donc c'est tout pour cet exemple. C' est l'implémentation de ce code en utilisant Java. 35. Mise en place la plus commune: Ok, Donc, dans cette vidéo, nous pouvons implémenter notre fonction en utilisant JavaScript. Donc la première chose que je vais faire est de créer la fonction. Je vais émettre la plus longue sous-séquence commune. Et il faudra les paramètres suivants. Donc, nous avons S1, S2, ce sont deux listes et tableaux. Et nous avons aussi les indices et nommez-les x et y. maintenant, nous pouvons ouvrir cette fonction. Et maintenant ce que nous allons faire ici, nous avons une faute de frappe. Donc, c'est la fonction. Maintenant, ce que nous allons faire est de créer notre tableau. Alors je vais le nommer. Peut-être. Et dans ce cas, il pourrait s'agir d'un nouveau tableau de taille x plus 1. Et bien sûr, nous allons avoir un nouveau tableau à l'intérieur de chaque position et le faire. Je le ferai dans une seconde. Donc, notre première boucle pour devrait commencer à I égal à 0, puis tout le chemin à x inclus, puis incrémenté. Maintenant, la seconde boucle pour devrait être, devrait commencer à j égal à 0. J est inférieur ou égal à y et incrémenter j. Et bien sûr chaque fois que nous arrivons à une position de I, nous allons créer un nouveau tableau, y plus 1. Maintenant, ce que nous allons faire est de vérifier si je suis égal à 0 ou x est, je suis désolé, ou j est égal à 0. C' est donc le cas. Ce que nous allons faire, c'est simplement stocker chez I et j à la valeur de 0. Maintenant, si ce n'est pas le cas, ce que nous allons faire est de vérifier si à la position S1 et S1, S2 J moins un. Si elles sont égales, alors nous allons faire un tenseur comme si la disposition, qui est S1 à I moins 1 est égal à S2 à J minus1. C' est le cas. Ce que nous allons faire est d'incrémenter i et j d'une valeur plus d, qui est à cette position, I moins 1, j moins 1, qui est la position diagonale de la valeur spécifique. Maintenant, comme vous allez le faire, si ce n'est pas le cas, nous allons prendre le maximum entre deux choses. Le premier est à la position qui est à gauche, et le second qui est à la position ci-dessus. Donc, ce que nous allons faire est de commencer à cette position spécifique, qui est I j. Le maximum entre le premier qui est un long terme à I moins un et, et je suis désolé j. Et puis le long I et j moins 1, cette affaire. Maintenant, c'est notre code. Enfin, après avoir terminé ces deux boucles pour, ce que vous allez faire est simplement de retourner la dernière valeur que nous avons obtenu, qui est le long, venez à x et y. maintenant, si nous allons de l'avant et l'imprimer, laissez-moi Commencez simplement par créer des listes de x, y. Ensuite, nous allons avoir z et w. Z. Ensuite, nous avons w. et nous avons la liste de, laissez-moi simplement les nommer variables. Nous avons donc des variables. Et dans ce cas, le second devrait être de x, y a, je suis désolé, x, z et a et W. Donc x, z, a et W. Et maintenant, ce que nous allons faire, c'est avoir les indices qui sont à position 4 pour l'instant. Donc var x est égal à 4, y, ce qui est également égal à quatre. Maintenant, ce que nous allons faire est simplement d'appeler la fonction et de la verrouiller. Donc je vais le stocker dans le résultat. Venez et on va l'appeler S1, S2, x, et y. et enfin, je vais le déconnecter pour que l'ensemble. Maintenant, ce que nous allons faire est de nous diriger vers notre cmd. Et bien sûr, nous pouvons ajouter notre programmation dynamique de bureau et JavaScript. C' est si mauvais. Et puis bien sûr, nous allons exécuter notre code en utilisant Node C dot js. Si nous exécutons notre code, nous allons en obtenir trois comme valeur finale que nous avons obtenu de cette fonction. Et c'est la plus longue sous-séquence commune que nous puissions obtenir. C' est x, y, et w rien que nous allons faire est visualiser cette fonction ou cette matrice 2D que nous venons de créer ici. Donc, au lieu de retourner la dernière valeur, je vais retourner tout le tableau 2D, matrice 2D. Et si nous le faisons à nouveau, nous obtiendrons le même résultat exact que nous avons construit à la main juste ici. Comme vous pouvez le voir, nous avons des zéros , des, et tout le chemin jusqu'au dernier, qui est en fait un trois qui dit, par exemple, pour cet exemple, c'est l'implémentation de ce problème en utilisant JavaScript. 36. Mise en place La plus longue des séquences communes: Très bien, donc dans cette vidéo, nous allons faire est de créer la fonction en utilisant un Python. Donc, je vais juste créer ce fichier subquence. Et maintenant, ce que nous allons faire est de commencer par notre définition ou la fonction que nous allons utiliser, juste pour photographier le cancer du poumon et prendre les paramètres suivants. Donc nous avons S1, S2. Vous avez également x et y comme paramètres ou les indices que nous allons utiliser. La première chose que je vais faire est de créer le plus long sous-marin commun. Et ce sera la liste que nous allons utiliser. Et pour être une liste de listes. Et le premier devrait être pour I dans la gamme de x plus 1. Et puis bien sûr, la deuxième unité sera dans la plage de y plus 1. Alors c'est tout. Maintenant, ce que nous allons faire est de commencer par notre boucle for. Donc pour être dans la plage de 0 jusqu'à x plus un, puisque x plus 1 n'est pas inclus. Donc c'est le premier, comme pour le second serait enraciné de 0 tout le chemin jusqu'à y plus 1. Maintenant, ce que nous allons faire est de vérifier si i ou j sont égaux à 0. Si I est égal à 0 ou j est égal à 0, c'est le cas. Ce que nous allons faire est simplement d'implémenter ou d'ajouter à cette position, la position spécifique à I et j a une valeur de 0. Maintenant, si ce n'est pas le cas, nous allons vérifier si à Assouan High moins 1 est égal à S2 moins S1. Donc S1 I moins 1 égal à S2 à j moins un. Donc, si c'est le cas, ce que nous allons faire est simplement de prendre la valeur diagonale que nous avons et de la stocker en incrémentant une seule valeur. plus longue sous-quence commune à I moins 1, j moins 1, et nous allons en ajouter une, et c'est tout. Maintenant, la dernière condition que nous allons avoir est que si ces deux conditions ne s'appliquent pas, nous allons juste stocker le maximum entre deux choses. Le premier étant à gauche. Donc, ce sera le maximum entre la plus longue sous-séquence commune, I moins1 et j, qui est la verticale, donc c'est au-dessus. Et le second sera chez moi, puis j moins 1. Donc c'est tout maintenant, après avoir fini de creuser ceci vers la gauche ou vers le tableau, ce que vous allez faire est simplement de retourner les valeurs aux indices spécifiques. Maintenant, pour l'essayer quand vous allez faire, c'est simplement de créer la liste. Donc, nous avons x, y, alors nous avons z et w. Ensuite, nous avons S2, qui se compose de x. Nous avons z, puis nous avons un, et ensuite nous avons w. C'est fondamentalement maintenant comme pour la hache égale à quatre, y égal à 4. Maintenant, on va l'imprimer. Nous allons imprimer s1, S2, x, et y. Alors maintenant, regardons ça. Je vais y aller et je vais y aller par programmation dynamique. Cinq, désolé, si dynamique, désolé, nous avons des fautes de frappe et nous allons faire est simplement d'exécuter le code. Donc maintenant, nous allons l'exécuter en utilisant Python et Python. Si la plus longue sous-quence commune dot py. Donc, ici, nous avons une erreur. Donc, je suis désolé, ici nous avons ensemble d'utiliser LCF, nous avons LF et Python. Donc LF, Python. Donc, nous devons aussi payer et ce que nous avons fait cela, nous appelons la fonction et l'imprimer. Laisse-moi juste le ranger, je suis désolé. Et en conséquence, donc je vais juste le placer et les résultats d'erreur, puis juste l' appeler ou imprimer après avoir terminé avec le calcul de la valeur du sel. Maintenant, après ça, ce que nous allons faire, c'est simplement aller ici et traîner à nouveau. Et comme nous pouvons le voir, nous avons obtenu trois, la valeur finale, qui est la plus longue séquence commune que nous puissions obtenir. Maintenant, au lieu de retourner toute cette liste ou le dernier élément de la liste, je vais retourner cette matrice 2D. Maintenant, si vous revenez et rafraîchissez, et comme vous pouvez le voir, nous avons notre fonction, notre matrice 2D, et comme nous pouvons le voir, c'est exactement la même chose à moins que nous ayons juste construit à la main. Donc c'est tout pour ce problème, la dernière valeur est en fait ce qui nous intéresse. C' est donc l'implémentation de cette fonction de subquence commune la plus longue en utilisant Python. Alors on se voit dans la prochaine vidéo. 37. Sous-séquence plus augmentante: Bonjour et bienvenue. Dans cette vidéo, nous allons discuter du problème de la plus longue sous-séquence croissante. Donc, l'idée de ce problème est que nous recevons une liste d'entiers et nous allons retourner la longueur de la sous-séquence croissante la plus longue. Donc, par exemple, si nous avons cette liste ici, nous avons 15, 7283, alors ce que nous allons retourner est le numéro cinq, indiquant la sous-séquence la plus longue dans ce cas, soit O157 que huit et 10. C' est donc la plus longue sous-séquence commune et nous allons retourner la longueur de celle-ci. Maintenant, la première fois que j'ai pour résoudre ce genre de problème est généralement la récursivité. Puisque nous avons besoin de trouver la sous-séquence croissante la plus longue, nous pouvons penser à l'idée de trouver la sous-séquence la plus longue pour chaque indice. Donc, par exemple, si nous sommes ici, la sous-séquence la plus longue pour cet élément spécifique est en fait une. Maintenant, ici, ce qu'on va en avoir, c'est deux, parce qu'on en a 15. Puis à sept heures, c'est trois, puis deux. Je suis de retour à deux. Puisque nous en avons 12, nous pouvons faire face. Alors ici, à huit heures, ça va être quatre. Et puis bien sûr à trois ans et ça va être 1, 2, et 3, ce qui est 3, et à dix, ce sera cinq. Donc, c'est essentiellement l'idée de ce problème. Maintenant, ce que nous allons faire est de vérifier comment nous pouvons l'implémenter en utilisant la récursivité. Donc la première chose que nous allons faire est de construire l'IC que nous allons avoir. Rappelez-vous donc que chaque fois que nous voulons résoudre ce problème, supposons que nous sommes à la position spécifique, qui est au numéro d'index 0, 1, 2, 3 et 4. Nous sommes donc à l'indice 4. Comment pouvons-nous résoudre ce problème pour le climat spécifique ? Comment pouvons-nous savoir que la plus longue séquence commune pour cet élément est en fait quatre. Donc la première chose que nous allons faire est de créer la condition ou la fonction pour l'index pour. Et ce que nous allons faire en fait, c'est de vérifier le maximum entre tous ces avant cet index spécifique, puis d'y ajouter un s'il est supérieur aux nombres réels. Alors comment on fait ça ? Nous allons ajouter un au maximum entre F3 et F2, F1 et 0. Et bien sûr, ils devraient tous être inférieurs ou égaux à cet élément spécifique à un index spécifique. Donc c'est un must, et bien sûr, c'est la fonction que nous allons faire maintenant, rappelez-vous que c'est juste pour, euh, pour, maintenant, si vous voulez calculer f 0, F1, F2 et F3, nous allons faire exactement la même chose ici. Donc, par exemple, nous avons ceci et nous avons ici devra calculer pour F1 et F2. Et comme vous pouvez le voir, nous construisons lentement un arbre où nous allons trouver juste pour cet élément spécifique de quatre, nous allons calculer tous ces éléments et les calculer encore et encore et encore. Et bien sûr, nous allons faire exactement la même chose pour tous ces indices ici dans notre liste. Donc, comme vous pouvez le voir, cela prendra une approche exponentielle et l'exécution sera exponentielle. Laisse-moi te montrer peut-être le pseudocode de ça. Jim. Et bien sûr, nous allons essayer de l'optimiser en utilisant la programmation dynamique. Donc la première chose que nous allons faire dans cette approche récursive est de construire la fonction. Donc, je vais simplement le nommer la plus longue augmentation et il faudra les paramètres suivants. Je vais avoir le tableau ou la leçon. Je vais lui donner le nom de la liste. Et je vais avoir l'entier et indiquer la longueur de cette liste. Ce que nous ne voulons pas faire, c'est vérifier le cas de base. Maintenant, rappelez-vous que nous devrions retourner la longueur maximale. Donc peut-être que je peux créer une variable globale à l'extérieur. Peut-être que je l'appellerai Max longueur. Et dans ce cas, je vais le mettre à jour dans notre code ici. Donc, ce que nous allons faire est de vérifier si vous êtes au cas de base, qui est n égal à 0 ou 1 dans ce cas, ce que nous allons supposer est que nous allons commencer par un. Donc, nous n'avons pas vraiment besoin de calculer 500. On va commencer par F1, F2, et ainsi de suite. Donc, un ventilateur égal à 1 est égal à un que nous allons faire est simplement de retourner un, car c'est le premier élément de la liste et nous devrions retourner sa longueur, qui est fondamentalement égale à un. Et si ce n'est pas le cas, rappelez-vous que nous devrions calculer tous ces quatre. Index spécifique. Donc, si nous sommes à U4, nous devons calculer F3, F2 et F1. Donc, dans ce cas, nous avons besoin d'une boucle for pour le faire. Et pour chacun d'eux, nous allons vérifier la valeur de retour. Et si elle est supérieure au maximum que nous avons déjà, nous devrions mettre à jour notre maximum. Alors comment on fait ça ? Nous allons simplement définir deux variables. Notre résultat que nous allons obtenir. Et bien sûr, le maximum, qui est le maximum actuel. Donc je vais juste le nommer Current Max. Et maintenant, ce que nous allons faire est de calculer ça. Alors comment on fait ça ? Nous allons appeler cette fonction pour ces indices spécifiques. Donc, nous allons commencer avec l'œil jusqu'à la valeur de n. Et bien sûr, nous pouvons l'incrémenter au fur et à mesure que nous traversons. Ensuite, ce que vous allez faire est d'obtenir les résultats de cette fonction. Nous allons donc stocker dans le résultat la fonction d'augmenter avec notre liste et les indices. Maintenant, je suis désolé, l'index est en fait, maintenant ce que nous allons faire est de vérifier si cette liste à l'index spécifique I moins 1 et n moins un. Si c'est inférieur à n moins un, alors nous devrions le mettre à jour. Alors comment on fait ça ? Laisse-moi prendre ça et le rendre plus petit. Et regardons ça comme ça. La nourriture est à cette position spécifique où nous devons calculer ce permettre. Ce que nous allons faire, c'est passer par toutes ces F1, F2 et F3. Et nous allons vérifier si la position spécifique est l'élément dans cette liste est inférieur à l'élément de permettre. Donc, par exemple, si nous sommes à cette F1 et laissez-moi supposer que c'est un quatrième. Donc c'est l'indice 4, 1234. Et ce que nous allons faire en fait, c'est vérifier si cette position spécifique est inférieure à celle-ci. Il l'est. Alors ce que nous allons faire est de vérifier la longueur maximale dans ce cas, laquelle est-ce ? Moins que la longueur maximale à cette position spécifique, qui est fondamentalement 0 dans ce cas. Et donc si c'est plus grand que celui-ci, si c'est le cas, alors nous pouvons prendre cela incrémenté d'un et le mettre ici, ce qui est fondamentalement deux. On va faire exactement la même chose ici quand on calculera celui-là. Donc la longueur ici est de deux. Est-il supérieur ou égal à 2 ? Oui, ça l'est. Ensuite, nous prenons juste deux plus un et incrémenté si c'est le cas. Maintenant, comme vous pouvez le voir, cinq, c'est moins que, je suis désolé, c'est plus grand que deux, alors on peut le faire. Nous avons donc deux étapes ou deux conditions à remplir pour que nous puissions mettre à jour ce maximum actuel. Laisse-moi juste les écrire. La première chose que nous allons vérifier si la liste à la position spécifique, qui est I moins un, parce que nous commençons à un et ces indices commencent par 012, 34, et ainsi de suite. Donc, si cette liste I moins 1 est inférieure à la liste spécifique à la fin à laquelle nous avons affaire. Donc n moins un, si c'est le cas et notre résultat plus un. Donc, nous devons nous rappeler que si vous êtes à la position spécifique, nous prenons juste les résultats de la fin incrémenté d'un, puis vérifions. Donc, si ce résultat est supérieur au maximum actuel que nous avons, max actuel, alors ce que nous allons faire est simplement de mettre à jour le max actuel. Donc, le max actuel serait, dans ce cas, leur résultat devrait être égal au résultat plus 1. Donc c'est le fondamentalement c'est comment nous pouvons mettre à jour notre maximum actuel. Maintenant, après avoir terminé de cet ensemble pour la boucle, qui est de cela. D' accord, alors laisse-moi juste le dessiner. Ce que nous allons faire est simplement de vérifier si le maximum actuel que nous venons d'obtenir dans ce cas est supérieur à la longueur maximale du tableau total ou de la liste totale P. Si c'est le cas, nous devons mettre à jour cette longueur maximale. Donc F total, je suis désolé, si le max actuel est plus grand, alors le maxlength. Nous devons mettre à jour le curseur. La longueur maximale doit donc être égale au max actuel. Donc, c'est en gros c'est notre code entier et notre code. Maintenant, après avoir fini tous ces, ce que nous devrions retourner, cette fonction n'est pas la longueur maxlength, est le courant max. Et la raison pour laquelle c'est ? Parce que laisse-moi juste prendre tout ça et les rendre un peu plus petits. Je suis désolé. Laisse-moi le faire à partir d'ici. Je vais prendre boucle et juste le minimiser et le placer ici comme avant. Et il n'y a pas que nous allons retourner ce max actuel est parce que notre fonction est à propos de cette correspondance actuelle. Alors rappelez-vous, si nous sommes à cette boucle quatre, ce que nous allons faire est de prendre ce max actuel de chacun de ces éléments, donc nous devrions retourner le max actuel. Cependant, lorsque nous avons besoin d'appeler cette fonction ne sera pas fondamentalement intéressé par ce genre de mathématiques. Nous sommes intéressés par la version mise à jour de la maxlength que nous traitons. Donc, pour dire que fondamentalement pour ce pseudocode, et comme vous pouvez le voir, cela fonctionne d'une manière exponentielle comme nous calculons ce poumon. Merci à chaque fois que nous avons terminé cette boucle pour et nous l' appelons tant de fois parce que c'est une récursive. Donc c'est essentiellement pour cette vidéo. Dans la prochaine vidéo, nous allons essayer de l'optimiser en utilisant la programmation dynamique. Alors, à vous voir. 38. Pseudo-Code: Ok, Donc dans cette vidéo, nous allons essayer d'optimiser notre fonction récursive et en utilisant la programmation dynamique. Donc, la chose est, chaque fois que nous utilisons la récursivité, c'est que nous appelons cette fonction encore et encore. Par exemple, si nous sommes à cette position spécifique de jamais pour ce que nous faisons fondamentalement est de coder F1, F2 et F3. Et dans ce cas un F2, nous allons appeler F1 et F3, nous allons appeler F1 et F2 à nouveau. Donc, au lieu de faire tout cela, ce que nous allons faire est simplement de créer une boucle for qui boucle à travers tous ces ensemble. Donc F1 et F2 et F3 et vérifie le maximum entre eux. Et après ça, nous allons le retourner ou simplement le placer dans ce F4. Et bien sûr, nous allons l'incrémenter d'un. Donc, au lieu d'utiliser ce pseudocode où je vais faire , c'est simplement de m'en débarrasser et de recommencer. Donc, ce que nous allons commencer par est en fait de construire la fonction où nous allons avoir la liste et l'index. Et donc je vais juste l'appeler le plus long serveur SQL en croissance. Il faudra une liste et l'entier. Et maintenant, ce que nous allons faire est de créer une liste où nous allons stocker la plus longue sous-séquence croissante jusqu'au point de ces indices. Donc, par exemple, si vous êtes à cette position spécifique, qui est l'index un, mais nous allons stocker dans l'autre liste que nous allons créer est la plus longue sous-séquence croissante de ce cas, qui est en fait deux . Ok, alors laisse-moi faire ça ici. C' est notre deuxième liste, donc je vais la nommer L I, S, indiquant que c'est la plus longue sous-séquence croissante. Et il sera de taille. Et dans ce cas, comme d'habitude, maintenant aller faire est d'initialiser nos indices I et notre valeur maximale. Donc nous avons moi, J et Max. Et tous ces éléments devraient être initialisés à 0, donc maximum à 0. Maintenant, ce que nous allons faire est de commencer avec notre boucle for, Salem, le LINCS avec un. Puisque dans chaque indice, nous avons, par exemple, si nous sommes à l'index deux, le nombre minimum ici est un. Donc, la longueur de la sous-séquence minimale possible est en fait un, et il inclut juste ce nombre lui-même. Donc, par exemple, si vous êtes à cette position spécifique cinq, la longueur minimale que nous pourrions avoir est en fait un, qui est à ce cinq ici. Donc, pour ce faire, je vais me permettre regarder de tout le chemin jusqu'à n et simplement stocker et LINCS à la position spécifique I, la valeur d'un. Ensuite, ce que nous allons réellement faire est de créer à un actif pour les boucles, de passer par tous ces éléments ou tous ces éléments dans cette liste. Et puis à chaque élément. Supposons donc que nous soyons à cette position spécifique, c'est-à-dire la position spécifique 3. Mais nous allons faire, c'est de passer à 012, obtenir le maximum entre ces deux. Et tant que la valeur à l'intérieur de ces positions est inférieure à la valeur à deux et que le maximum ici est supérieur à cela, alors nous pouvons la mettre à jour. Donc, ce que nous allons faire est de me laisser juste l'écrire ici, mais avant cela, laissez-moi minimiser cela et ensuite continuer. Donc ce que nous allons dire, c'est que nous allons avoir une boucle for de I jusqu'à n. Et puis à l'intérieur de cette boucle pour, nous allons commencer à partir de 0 jusqu'à I. Bien sûr, je devrais commencer à 0. Alors ce que nous allons faire est de vérifier, comme nous l'avons dit, si la liste à cette position spécifique, je suis plus grande que la liste à, je suis désolé, ici nous avons j de 0 jusqu'à ISO, j égal à 0 le chemin jusqu'à i. Et ici nous ont I égal à 0 tout le chemin jusqu'à n et est inférieur à I est supérieur à la liste. Donc, si nous sommes, par exemple, ici et que nous avons un égal à 3 qui supposent que ce que nous allons faire est de regarder à travers tous ces éléments de 0 à. Et ce que nous allons faire est de vérifier si ces articles sont inférieurs à l'article que nous avons. Alors si c'est le cas, ce qu'on va faire. Nous allons donc y mettre fin avec la plus longue sous-séquence croissante. Supposons donc que nous soyons à cette position spécifique où nous en avons un. On va en prendre un et y ajouter un. Donc, ça en fera deux. Et rappelez-vous que nous avons initialisé tout ça à un seul. Donc, si vous êtes la position spécifique qui est à l'index trois, et que nous allons avoir une AD comme sous-séquence croissante la plus longue. Pour l'instant, nous allons prendre 1 plus 1, ce qui est égal à deux. On va vérifier si deux est supérieur à un. Si c'est le cas, alors nous devons mettre à jour ceci. Donc, pour ce faire, nous allons vérifier à une position spécifique, qui est j plus 1 est plus grand que le LINCS à la position de I. Si c'est le cas, alors nous devons mettre à jour notre LAS à atoi. Donc je vais être à, je devrais être égal à S à j 1. Donc c'est tout maintenant qu'on va en avoir une liste ici. Donc nous allons avoir 1, 2, 3, 2, 4, 3 et 5. Et bien sûr, pour obtenir le maximum, nous allons créer une autre boucle pour qui nous aide à obtenir le maximum de cette liste Elias. Donc, pour faire ça, laisse-moi juste faire ça ici. Et ce que nous allons faire maintenant est de créer une autre boucle pour, en boucle à travers I égal à 0 jusqu'à la fin. Et nous allons trouver un maximum sans distorsion et la variable maximale juste ici. Donc, si Elias chez moi est supérieur au maximum, nous allons stocker et maximiser cette valeur d'Elias chez moi. Donc c'est tout maintenant ce que nous allons retourner est simplement de retourner le max que nous venons de calculer, ce qui est en fait la longueur de la sous-séquence croissante la plus longue que nous ayons écrit. Donc, nous retournons simplement Max, et maintenant nous sommes bons. C' est donc notre fonction. Maintenant, si nous voulons l'appeler, nous pouvons simplement l'exécuter en utilisant le tableau ou moins que nous avons et c'est l'index ou la taille de celui-ci. Donc c'est tout maintenant, pensant à la complexité du temps. Ici, nous utilisons deux boucles imbriquées, partir de 0 jusqu'à n. Et nous avons aussi de I égal j égal à 0 jusqu'à ce que i, qui est fondamentalement dans le pire scénario, nous allons avoir n, donc nous ont m carré juste ici. Et ce que nous avons fait dans l'espace auxiliaire, c'est que nous les avons vendus dans un tableau ou une liste, et cela prendra un espace de n. Donc, la complexité temporelle est O n carré et la complexité de l'espace est O de n. essentiellement pour ce problème. Dans la vidéo suivante, nous allons l'implémenter en utilisant nos langages. 39. Plus de nouvelles séquences de sous-séquence: Oh, hey, donc dans cette vidéo, nous allons implémenter notre fonction en utilisant Java. Donc, la première chose que je vais faire est de créer la fonction que nous pouvons utiliser. Donc c'est statique publique, et je vais le nommer le plus long, en augmentation. Et il faudra le gris. Et maintenant, ce que nous allons faire est de créer la plus longue sous-séquence croissante, qui sera également un tableau de taille n, comme nous l'avons dit. Ensuite, nous allons initialiser nos indices. Et bien sûr, nous allons initialiser le maximum que nous allons utiliser. Après ça. La première chose que nous allons faire, comme nous l'avons dit, est de remplir la liste la plus longue sous-séquence croissante avec celles. Donc, nous allons commencer avec I égal à 0. Je suis inférieur ou égal à n, et nous allons l'incrémenter. Ensuite, ce que nous allons faire est de remplir la plus longue sous-séquence croissante à la position spécifique I, la valeur d'un. Après cela, nous allons continuer avec notre boucle for. Donc, nous avons deux imbriqués pour les boucles I moins de n et I plus plus. Ensuite, nous allons continuer avec j égal à 0, j inférieur à i, et implémenter j. Comme nous l'avons dit dans notre pseudocode, nous allons vérifier si ces valeurs à la liste ou le tableau à I est supérieur au tableau à j. Et nous allons vérifier si la plus longue sous-séquence croissante à j plus un est supérieure à la plus longue sous-séquence croissante chez moi. C' est le cas. Nous devons mettre à jour la sous-séquence croissante la plus longue à une position spécifique. Donc, si le tableau à I est supérieur au tableau à j, et comme nous l'avons dit, la sous-séquence croissante la plus longue à j plus un est supérieure à la sous-séquence croissante la plus longue à j'ai ceci est le cas, alors nous devons mettre à jour ça. Si la sous-séquence croissante la plus longue, je devrais être égale à celle à j plus un. Donc, fondamentalement, c'est comme ça que nous pouvons construire notre tableau. Maintenant, après la pression de ces deux imbriqués pour les boucles, nous devons trouver le maximum et le stocker et la valeur maximale. Donc, nous allons regarder à travers I égal à 0 moins de n, puis incrémenter I. Ensuite, nous allons vérifier si le maximum est inférieur à la sous-séquence croissante la plus longue à la position spécifique que c'est le cas, alors nous devrions mettre à jour le maximum pour être la valeur que nous avons ici. Maintenant, après cela, mais nous allons faire est de simplement retourner le maximum que nous avons. Maintenant, essayons-le. Ce que je vais faire est de créer une fonction principale où je vais créer le tableau que nous voulons. Maintenant. Donc l'aération soit, laissez-moi utiliser le même exemple exact. Nous avons 15 728310, donc 157283. Et puis nous avons la longueur n, qui est fondamentalement la longueur, la longueur de ce tableau, 1, 2, 3, 4, 5, 6, 7. Donc n égal à sept. Maintenant et je vais faire est de stocker le résultat dans un entier appelé résultat. Et je vais appeler cette fonction, qui est la plus longue séquence croissante. Et bien sûr, je vais imprimer le résultat comme ici, alpha, allez-y et exécutez ce code. Je vais en obtenir cinq comme la plus longue sous-séquence croissante. Et si nous revenons ici, vous pouvez constater que notre moins se compose de cinq éléments indiquant que la longueur de cette liste est en fait de cinq. Donc c'est ça fondamentalement maintenant 400 aller plus loin dedans et visualiser cela. J' énumère la plus longue sous-séquence croissante qui se compose de 1232435. Ce que je vais simplement faire est de retourner une liste ou un tableau au lieu de cela. Et je vais simplement revenir ici la plus longue sous-séquence croissante. Alors ce que je vais faire est de le stocker dans un résultat comme celui-ci. Et je vais créer une boucle for. Et bien sûr, je vais l'imprimer comme un peu d'espace. Et si nous allons de l'avant et relancez ce code, nous allons obtenir 1232435. Maintenant. Il faut qu'on y arrive. Donc nous avons 1232435 et comme nous pouvons le voir, nous avons 1232435. Les résultats correspondent donc à nos attentes. Et c'est la documentation de la plus longue sous-séquence croissante en utilisant Java. 40. La plus longue implication Javascript: Comment k. Donc, dans cette vidéo, nous allons implémenter notre fonction en utilisant JavaScript. Donc la première chose que je vais faire est de créer notre fonction et je vais la nommer. Je vais obtenir une liste et l'entier et indiquer la taille de cette liste. Maintenant, ce que nous allons faire est de créer une autre liste qui est la plus longue sous-séquence croissante. Je vais le nommer Ally. Et un tableau de et c'est la taille. Et j'allais le remplir avec un 1. Donc c'est tout en gros. Maintenant, initialisons les indices I et j. Et puis nous allons initialiser un maximum que nous allons utiliser, qui sera égal à 0. Ensuite, on va commencer de I à 0. Je suis désolé, de je égale à un jusqu'à ce que je égale à et, et juste mis en œuvre. Ensuite, nous allons prendre J, ce qui est égal à 0. Donc j de 0 à I, et bien sûr nous allons l'incrémenter. Maintenant, nous allons faire la même chose que le pseudocode. Nous allons vérifier si la liste à i est supérieure à la valeur inférieure à j. Donc si la liste à i supérieure à a, inférieure à j, et nous devons vérifier si le Elias à j plus unestsupérieur à DALYS à i. est Donc si la liste à i supérieure à a, inférieure à j, et nous devons vérifier si le Elias à j plus unestsupérieur à DALYS à i. besoin de mettre à jour cette alliance chez I pour être égal à Ls à j plus 1. Ensuite, après cela, nous pouvons retourner le maximum. Maintenant, ce que nous allons faire est de rechercher le maximum à l'intérieur de la liste. Donc, nous allons commencer à partir de 0 jusqu'à et, et mis à jour. Ensuite, nous allons vérifier si Max est inférieur l'Elias à la position spécifique dans laquelle nous allons le mettre à jour. Donc Max devrait être Elias chez moi et bien sûr après cela, nous devrions simplement retourner le maximum. Alors c'est tout. C' est ça. C' est la fonction que nous allons utiliser maintenant, je vais faire est de créer notre liste, donc pour l'exécuter, donc nous sommes juste égaux à la même liste exacte que nous utilisons. Nous en avons 15, 7283 et 10. Donc 157283 et 10. Ensuite, nous avons n qui est égal à 7, fondamentalement. Ensuite, après cela, je vais stocker le résultat dans une variable appelée résultat. Et deux seront les plus longues, augmentant comme moins de 10. Après ça, je vais le déconnecter. Donc, je vais déconnecter les résultats après ça. Ce que je vais faire est de me diriger vers mon répertoire, qui est la programmation dynamique JavaScript. Et puis je vais exécuter ce code en utilisant le script Java Node. Je suis désolé, noeud. Et le nom du fichier le plus long point de sous-séquence croissante js. Et donc nous avons une erreur ici. Voyons donc, à l'intérieur du module introuvable. Donc je crois que je l'ai mal écrit. La plus longue sous-séquence croissante. Donc, il augmente le noeud de sous-séquence apprendre augmentation de la sous-séquence qui n'a pas de criminalistique et nous allons en obtenir cinq comme la plus longue sous-séquence croissante que nous ayons. Et si vous voulez visualiser réellement cette liste de la plus longue sous-séquence croissante, qui est 1, 2, 3, 2, 4, 3 et 5. Nous pouvons simplement retourner l'Elias au lieu du maximum ici. Et maintenant, si je vais de l'avant et revenir en arrière, lire à nouveau, je vais obtenir 1232435 comme le résultat que nous attendions et comme le résultat que nous avons réellement généré à la fin ici. Donc, c'est tout fondamentalement pour ce problème est, est que pour la plus longue sous-séquence croissante en utilisant JavaScript. 41. Plus de nouvelles séquences de croître: Ok, Donc c'est l'implémentation Python du problème de sous-séquence croissante le plus long. Donc, la première chose que je vais faire est de définir la fonction. Je vais nommer la plus longue augmentation. Et il faudra le tableau ou la liste que nous allons avoir une liste simplement nommée. Ensuite, nous allons avoir l'index n ou la taille de cette liste. Ce que nous allons faire en fait, c'est de stocker et une nouvelle liste. Je vais nous émettre Ally. On va stocker une fois et ils ne le seront pas. Et une fois. Après cela, nous pouvons commencer par aller ou les deux pour les boucles. Donc, pour moi dans la plage de 1 n, nous allons aller de j dans la plage de 0 à i. Et nous allons vérifier, comme nous l'avons dit précédemment, à l'intérieur du pseudocode, nous pouvons vérifier si la liste à i est supérieure à la liste j. Alors laissez-moi l'écrire vers le bas très vite. Donc moins chez moi est plus grand que la liste L, j. Et nous avons aussi, désolé, et nous allons avoir le LINCS. J plus 1 est plus grand que le chapeau LAS I. J plus 1 est en fait plus grand que les Elias à i f. C'est le cas. Alors ce que nous allons faire est de mettre à jour l'ALS à L2. Je vais ajouter j plus 1. Après cela, nous pouvons définir le maximum que nous allons utiliser. Donc, le maximum devrait être au premier 0. Ensuite, nous allons examiner toute la liste Elias, qui a la plus longue sous-séquence croissante pour chacune. Et c'est, et dans ce cas pour moi dans la gamme de 0 tout le chemin. Et donc je vais simplement écrire, et si le maximum est égal, plus grand que la variable maximale réelle que nous avons ici, alors nous devons mettre à jour celui-ci ici. Alors comment on fait ça ? Nous pouvons simplement écrire le maximum est inférieur au LSAT. Je vais mettre à jour le maximum pour être à une position spécifique i. Après cela, ce que nous allons simplement retourner comme le maximum que nous avons créé en ce moment. Maintenant pour vérifier, ce que je vais faire est de créer une liste, qui est exactement la même chose que nous, hey, donc nous avons 15728310. Donc nous allons avoir dans cette liste 15, 7283 et 10. Ensuite, nous allons avoir n, ce qui est égal à 7. Après cela, je vais stocker un résultat, la plus longue sous-séquence croissante avec moins et n. Et bien sûr, je vais imprimer le résultat. Maintenant, regarde ça. Ce que je vais faire est simplement de me diriger vers le bureau CMD et vers le répertoire de programmation dynamique Python. Et je vais exécuter ce code. Si la plus longue sous-séquence croissante point py. Donc, ici, nous avons une erreur parce que nous avons créé un résultat variable et nous ne pouvons pas l'utiliser en Python. Donc maintenant, si nous revenons en arrière et actualisons, comme vous pouvez le voir ici, nous allons en obtenir cinq comme la plus longue sous-séquence croissante à l'intérieur de cette sous-séquence d'entiers. Maintenant, si nous voulons voir toute la liste, c'est ce que, les 1, 2, 3, 2, 4, 3 et 5. Nous pouvons simplement revenir en arrière le maximum, juste l'allié comme, tel qu'il est. Maintenant, si vous revenez et recommencez, nous allons avoir cette liste 1, 2, 3, 2, 4, 3 et 5. Il s'agit donc de la sous-séquence croissante la plus longue pour chaque index dans notre liste d'entrées. Donc je n'avais pas 0 aux ingrédients les plus longs. Le muscle oblique est un, index, un, il est 23. Et ici nous en avons deux parce que nous, à la position spécifique, c' est-à-dire que nous sommes, nous devons, la plus longue sous-séquence croissante est 12 et sa longueur est en fait 2. Donc c'est tout maintenant ce que nous avons fait à la fin est de calculer le maximum de ceux-ci, qui est cinq, et de le retourner comme notre résultat. Donc c'est tout pour ce problème. C' est l'implémentation de la plus longue sous-séquence croissante en utilisant Python. 42. PROJET: Ok, Donc, dans le dernier problème, nous avons résolu la longueur de la plus longue sous-séquence croissante en utilisant une complexité temporelle de O n carré, comme vous pouvez le voir ici. Donc, ce que nous avons fait est de trouver la longueur de la plus longue sous-quence dans une liste d'entiers comme celui-ci, et c'est la plus longue est 15, 7, 8, 10, et sa longueur est en fait 5. Maintenant, ce que vous supposez faire est d'améliorer l'heure de la solution pour trouver un moyen amélioré en termes de complexité temporelle. Donc notre complexité temporelle est O n carré. Votre tâche est de l'améliorer en o et connectez-vous. Donc, ce que vous devez faire est de penser à une méthode et implémentée en utilisant votre langage de programmation préféré et d'améliorer la solution en termes de complexité temporelle. Maintenant, gardez à l'esprit lorsque vous faites face à un tel problème, vous pouvez sacrifier la complexité de l'espace pour avoir une meilleure complexité temporelle. Par exemple, si nous n'utilisons pas de tableau ou si nous utilisons une liste, nous pouvons en utiliser plus. Vous pouvez utiliser une matrice 2D, un HashMap ou n'importe quoi de ce genre afin d'améliorer votre complexité temporelle. Donc, nous nous concentrons sur la complexité temporelle et ignorons l'espace pour l'instant. Alors c'est tout. C'est votre tâche. J' espère que ça vous plaira. Notez, et n'oubliez pas de déposer votre projet dans la section projet. Et bonne chance et profitez-en. 43. Conclusion: Félicitations, vous venez de finir ce cours. Ce n'est qu'un bref résumé de ce que nous avons couvert. Donc, la première chose que nous avons fait est d'utiliser la séquence Fibonacci pour définir la mémorisation et la tabulation et apprendre les différences entre eux. Ensuite, nous résolvons certains des algorithmes de programmation dynamique les plus célèbres. Et au début, nous dessinons les arbres, leurs IRA ou matrice 2D à côté du pseudocode que nous allons utiliser. Après cela, nous les avons mis en œuvre en utilisant nos langues. Alors maintenant, juste des conseils rapides. Chaque fois que vous avez vendu ce genre de problèmes de programmation dynamique, vous devez le résoudre par un 100 assoiffé essayé trouver la solution qui fonctionne, peut-être par récursivité. Et bien sûr, après cela, vous pouvez commencer par l'optimiser et trouver une meilleure solution en utilisant la mémoisation et la tabulation. Donc, cela étant dit, c'est la fin de notre cours. J' espère que ça vous a plu. Enfin, si vous avez des questions, des suggestions ou des améliorations, je peux faire le discours. Ou si vous voulez que je couvre des problèmes supplémentaires, s'il vous plaît demandez-le dans la section Q&R. Et ce serait génial de laisser un commentaire afin que je puisse améliorer ce cours. Merci d'être ici et bonne chance pour votre prochain voyage.