Programação dinâmica: Java, Javascript e Python

1. Introdução: Olá a todos e bem-vindos a este novo curso que é sobre programação dinâmica. Meu nome é 100 unidades e serei seu instrutor ao longo deste curso. Então, primeiro de tudo, deixe-me começar mostrando o esquema com o esboço deste curso. Vamos começar definindo programação dinâmica. E nós vamos aprender sobre duas das técnicas mais populares que geralmente são usadas dentro deste tópico. O primeiro é memorização, e o segundo é tabulação. E vamos aprender sobre eles usando a sequência de Fibonacci. Vamos resolver este problema usando três métodos. O primeiro é usar a recursão generativa que todos conhecemos. E vamos passar para a memorização e tabulação. E vamos ver as diferenças entre eles. E vamos aprender quando e onde usar cada um deles. Depois disso, o que vamos fazer é resolver alguns dos exercícios mais famosos usando programação dinâmica. Então a primeira coisa que vamos fazer é tentar construir uma árvore ou talvez uma espécie de matriz ou uma matriz 2D deste problema. Depois disso, vamos tentar escrever um pseudocódigo que nos ajude a implementar esse problema. E, finalmente, vamos realmente implementado usando três linguagens, Java, JavaScript e Python. Então, passando pelas seções, você pode notar que vamos resolver um problema principal em cada seção. E o problema contém a explicação do problema juntamente com o código ou exemplo de trabalho. Então vamos ter um pseudocódigo que explica nossa lógica e fórmulas. E depois disso vamos implementá-lo usando as três línguas mencionadas anteriormente. Nós também temos um recurso adicional que é este site. Eu criei este site para que você execute seu código e testado. Então aqui temos alguns problemas que vamos resolver. E você pode ir em frente e escolher um dos problemas. Tente resolvê-lo aqui antes de voltar para a explicação em vídeo e implementação que temos e discurso. Então isso disse basicamente, este é o esquema ou o esboço do nosso curso. Espero que gostem e nos vemos na próxima seção. 2. Requisitos: Antes de começarmos, há uma lista de requisitos que você precisa baixar de acordo com o idioma que você vai usar. Então, por exemplo, se você estiver usando Java, mas você precisa baixar é Eclipse ou algum tipo de IDE onde você pode executar Java. Então é claro que você vai precisar baixar Java. Você está indo para o Java SDK e eles apenas meio que pressionar e concordar e tal download gratuito. E você terá sua versão mais recente. Se você estiver usando Python, por exemplo, você precisa baixar Python. E, claro, vou baixar o Visual Studio Code onde vamos executar nosso código com Python e JavaScript. Finalmente, para JavaScript, vamos usar Node.JS para executá-lo em nosso servidor. Portanto, estes são os requisitos que você precisa. Vou adicionar os links na seção de descrição. E espero que tenha gostado desta aula. Vejo vocês na próxima seção. 3. Sequência de Fibonacci: Tudo bem, então olá e bem-vindo. E esses dois vídeos, vamos responder a questão do que é programação dinâmica? Então vamos começar com algo simples. Essa é a sequência de Fibonacci. E a sequência de Fibonacci é na verdade uma sequência onde cada número é a soma de seus dois números anteriores. Então, nossos casos básicos são na verdade os dois primeiros números, isto é 01. Estes são os dois primeiros números na sequência de Fibonacci. E o resto deles são, na verdade, a soma dos números anteriores. Por exemplo, se um eu obter esse número, é 0 mais um é um. Então temos 1 mais 1, 2, 1, 2, 3, 2 mais 35, assim por diante e assim por diante. Então esta é a sequência de Fibonacci. Agora, sempre que queremos resolvê-lo, nosso primeiro pensamento entra em recursão. vez que cada vez que queremos calcular o número em uma posição específica, precisamos voltar para os números anteriores. Então deixe-me escrever os índices bem aqui. Então este é o índice 0, 1, 2 , 3, 4, 5, 6 e 7. Agora deixe-me desenhar uma árvore onde vamos representar esses números. Então vamos supor que eu queira calcular o Fibonacci de cinco. Então, para calcular o Fibonacci de cinco, eu preciso calcular o Fibonacci de quatro e seguida, o Fibonacci de três e, em seguida, somá-los juntos. Agora, a fim de obter este Fibonacci de quatro, o que eu realmente deveria fazer é calcular o Fibonacci de três e, em seguida, o Fibonacci de dois. E a mesma coisa se aplica aqui. Então eu quero obter f de 2 e f de 1. E aqui vamos nos encontrar para obter f de 1 e f de 0. E lembre-se que f de 1 e f de z são os casos básicos. E sempre que chegarmos a este ponto, devemos realmente apenas retornar esses dois valores que temos aqui. Então aqui temos f de 1 também e f de 0. E a mesma coisa se aplica aqui. Então eu só vou escrever estes pontos. Então é isso basicamente agora, se pensarmos sobre a complexidade do tempo deste algoritmo, ele tomará uma forma exponencial, já que, como podemos ver, estamos calculando os mesmos números repetidamente. Então aqui temos f de 2, 2, e aqui temos f de 1, 1 e 1. E você está realmente computando-os uma e outra vez, como podemos ver. Portanto, nossa solução pode funcionar, ou ela realmente funciona para números pequenos, mas levará muito tempo, pode levar segundos, minutos ou até mesmo horas para calcular uma grande sequência de Fibonacci. Então, como código absoluto pode parecer? Então deixe-me escrever o Fibonacci e deve ser igual a este código. Então a primeira coisa que vamos fazer é escrever os nossos casos básicos. Se n for igual a 0. Então, se n está no índice 0, devemos apenas retornar este valor que é 0. Então eu vou simplesmente retornar 0 neste caso. Agora, se n é igual a 1, o que devemos retornar como realmente este valor em um índice específico um, que é na verdade um. Então eu vou simplesmente devolver um. Agora podemos começar com o nosso caso base ou sinto muito, com a nossa recursão. O que precisamos retornar, na verdade, são os dois números anteriores. Então, se estamos a Banaji de n, que é igual a cinco, devemos fingir Fibonacci de quatro mais Fibonacci de três. Então, como fizemos isso? Nós simplesmente chamamos a função Fibonacci de n-minus-1. E então resumimos com o Fibonacci de n menos 2. Então é isso. Basicamente, isto é para o nosso pseudocódigo. Agora o que eu vou fazer é pegar o espírito de Deus e realmente implementado usando Java. Tenha em mente que nós só vamos usar Java com a finalidade de visualizar a complexidade do tempo neste problema e o resto de seus problemas será apresentado em todas as linguagens, Java, JavaScript e Python. Então, para fazer isso, deixe-me ir ao Eclipse. E o que eu vou fazer é escrever este código aqui. Então f n é igual a 0. Eu vou fazer é simplesmente retornar 0. Agora, se n é igual a um, eu vou devolver um. E se estes não são os casos, o que vou fazer é simplesmente voltar. Então eu vou retornar Fibonacci de n menos 1 mais Fibonacci de n menos dois. Agora, depois disso, vou-me embora, desculpa, esqueci-me daqui. Agora, para testar isso, o que eu vou fazer é criar uma função principal e chamar o Fibonacci de um número específico impresso, imprimir o Fibonacci de 7 neste caso. Como você pode ver, se eu seguir em frente e executar este código aqui. Mas, na verdade, vou ficar como P número 13. E se você voltar aqui, podemos ver que este Fibonacci deste específico e X7 é na verdade 13. Então nosso código funciona corretamente. No entanto, se eu voltar agora e vamos tentar o Fibonacci 50. E se rodarmos este código terça-feira, algum tempo para ser executado desde que temos chamadas recursivas onde vamos executar o mesmo código ou executar a mesma função uma e outra vez. E isso vai levar talvez segundos ou talvez minutos neste caso. Então precisamos ter uma maneira melhor obter essas sequências de Fibonacci ou os resultados neste caso. E aqui vem na programação dinâmica. Então, temos duas técnicas que vamos apresentar. O primeiro é chamado de memoização, e o segundo é chamado de tabulação. E vamos apresentá-los nos próximos vídeos. Então, vejo você então. 4. Memoração: Certo, então encontramos a solução onde usamos recursão para resolver esse problema de Fibonacci. No entanto, temos um problema por causa de sua complexidade de tempo. Porque estamos executando a mesma função ou chamando a mesma função uma e outra vez. Então, como lidamos com isso? Aí vem a programação dinâmica. Então a primeira técnica que vamos usar é chamada de memoização, que é basicamente apenas para armazenar os valores que vamos usar uma e outra vez. Então, a fim de fazer isso, em vez de apenas chamar f de 2 aqui uma vez e aqui outra vez. Mas nós realmente vamos para dois para resolver este f de dois na primeira vez que o vemos. Então nosso código vai funcionar assim. Vamos ligar para f de 5, 10. Neste caso, ele chamará de f de 4, 4, 3. No entanto, antes de chamar isso, ele vai por aqui. Então o fluxo do nosso código está realmente sendo f de 5, 4, 3, e então nós vamos até 21, e nós estamos bem e então nós vamos voltar até aqui. E como você pode ver bem ali. Então este é o fluxo do nosso código. Agora o que fizemos para basicamente fazer é armazenar todos esses valores cada vez ou a primeira vez que vamos vê-los. E, claro, sempre que quisermos usá-los novamente, vamos tirá-los da nossa memória. Então, para fazer isso, o que eu vou realmente adicionar neste caso é uma lista aqui. Então deixe-me deletar isso. E eu vou mudar os parâmetros aqui, de N para N e uma memória. E neste caso, o que realmente vamos fazer é pegar essa memória e usá-la mais tarde. Então, antes de fazer tudo isso, vamos verificar se o fibonacci desta sequência, e é realmente armazenado dentro de nossa memória. Então, como fazemos isso? Deixe-me apenas mudar a cor para que possamos visualizar as mudanças. Então, se a memória nesta posição específica e não é igual a 0. Agora lembre-se que sempre que criarmos essa memória, vamos colocar zeros e a posição de Annette e FDA, que é n, não é igual a 0. O que realmente vamos fazer é simplesmente devolvê-lo como está. Então vamos devolver a memória nesta posição específica. E agora, se este não for o caso, vamos continuar com o nosso código como antes. No entanto, antes de devolver este aqui, o que realmente vamos fazer é armazená-lo dentro de nossa memória. Porque lembre-se que Fibonacci n é devolvido por este quadril direito. Então, para fazer isso, eu simplesmente vou armazená-lo na memória em n e, em seguida, retornou. Então deixe-me fazer isso simplesmente pegando tudo isso e talvez empurrá-los para ouvir. E o que eu vou fazer agora é pegar isso e colocá-lo aqui. Agora, vamos continuar. Então, em vez de devolver este, e eu vou fazer é apenas colocá-los dentro de nossa memória e devolver a memória real. Então deixe-me tentar aqui. Temos memória em n será igual a este. E, claro, depois disso, vamos simplesmente devolver a memória nesta posição específica. E então é isso agora, em vez de chamar todas essas funções uma e outra vez, quem apenas vai verificar se eles estão nessa memória? Se for esse o caso, vamos simplesmente devolvê-los. Se este não for o caso, vamos computá-los e armazená-los dentro da memória pela segunda vez, vamos usá-los. Claro, funcionará corretamente. Agora, vamos em frente e usar esse pseudocódigo e nosso Java. Então, em vez de ficar, vou tirar uma memória. E, claro, quando chamarmos os nazistas aqui, também devemos retornar a memória. No entanto, antes de devolvê-lo, o que devemos realmente fazer é apenas adicionar uma cauda. Então a memória em n deve ser igual a ds, e é claro que devemos caber na memória. E depois disso, agora, vamos chamar de critério. Então, como você pode ver, este grande número levou algum tempo para obter e é negativo porque estávamos usando inteiros. Então talvez vamos usar 24 agora. No entanto, precisamos incrementá-lo. Então vamos ter uma nova extremidade de tamanho 21 para usar dentro do pseudocódigo. Agora, se voltarmos e rodarmos este código, como podem ver, temos o nosso resultado que é 67, 65, que é, não demoramos muito tempo como antes. Deixe-me verificar o número 30. E como podemos ver, para não descoberto, nós vamos obter esse grande número e esse número que poderia não ter apenas computado usando a função recursiva original porque estamos chamando as mesmas funções exatas uma e outra vez. Então agora o que vamos fazer é tentar um número muito grande, como 20000. Neste caso, se formos em frente e executá-lo, podemos ver que recebemos um erro. E esse erro é realmente StackOverflow. Então nosso código será executado rapidamente. No entanto, sempre que chamamos essas funções uma e outra vez. Então, se estamos em uma posição específica onde temos 10 mil, vamos chamar dez mil, novecentos mil, novecentos e noventa e nove mil, novecentos e noventa e oito todo o caminho até o último que está em 0. Então, todos estes uma chamada de volta funções ou callback SysML vão ser ou o ou apenas armazenado em uma pilha. E nossa equipe pode não levar tudo isso ou encaixar tudo isso juntos. Então o que vamos fazer é usar outra técnica chamada tabulação. E também é uma técnica de programação dinâmica, e vamos vê-lo no próximo vídeo. 5. Tabulação: Certo, então no último vídeo, usamos memórias para resolver esse problema de Fibonacci. No entanto, temos um problema em que tivemos um erro de estouro de pilha porque estávamos usando muitas instruções de retorno, retornos de chamada e estamos armazenando todos eles dentro de nossa pilha e isso não poderia caber neles. Então agora, o que vamos fazer é usar tabulação para resolver este problema de Fibonacci. Agora, se sabemos que precisamos obter este f de cinco, e para obter este f de 5, precisamos obter f de quatro, f de 2 e f de um. Então faz sentido resolver tudo isso de antemão e apenas armazená-los em uma espécie de lista de array ou algo assim. E, em seguida, apenas retornar f de 5. Então o que vamos fazer é começar do fundo até o último elemento. E isso é chamado de tabulação, que é basicamente programação dinâmica de baixo para cima. E realmente chamou isso porque nós vamos construí-lo de baixo, um por 12, pregando nosso propósito. Então o que vamos realmente fazer é começar de 0, preencher nossa função, ou através de nosso descanso, e então retornar o último que precisamos. Então deixe-me deletar todo esse pseudocódigo e escrevê-lo novamente com tabulação. Então eu vou realmente fazer é criar uma função e será uma função iterativa, tão iterada. E neste caso o que vamos fazer é ter um número e que vamos retornar. E neste caso, o que eu vou fazer é criar talvez uma lista ou um array. Vou simplesmente chamar-lhe uma lista. E será de tamanho e mais um. E o que vamos fazer na verdade é preencher esta lista com esses valores aqui. Assim, a lista no índice específico 0 deve ser igual a 0. E então a lista em um índice específico 1 é igual a um. E então podemos começar com um loop for começando em I igual a dois todo o caminho até n. E cada vez dentro desta lista vamos armazenar esse índice específico I, o valor da lista em i menos 1, e o mais em I menos dois. Então, ele vai levar um grande O de n. Então esta é a complexidade do tempo de execução porque estamos percorrendo todos os elementos de 0 a n. E sempre que alcançamos o último elemento que está em um índice específico, e podemos retorná-lo. Então, depois de terminar de tudo isso, simplesmente retornamos a lista na posição. E neste caso, então é basicamente isso agora, em vez de ligar de volta cada vez que precisamos chamar isso, por exemplo, f em 99, 99, podemos simplesmente armazená-lo em nossa lista e, finalmente, obtê-lo sempre que quisermos. Então, neste caso, deixe-me apenas ler digite esta função aqui usando tabulação. Então, em vez de obter tudo isso, o que eu vou fazer é simplesmente criar uma função e será. E em vez de armazenar esse parâmetro, vou simplesmente escrevê-lo aqui. Então eu vou ter a senhora bem aqui do tamanho n mais um. E neste caso, o que eu vou fazer é armazenar em Mamute 0 o valor de 0, a mãe de um será um. E agora podemos começar com o loop for, começando de I igual a dois todo o caminho. E assim incluído. E é claro que vamos incrementá-lo depois disso. O que eu vou fazer é começar nesta posição específica em i, o valor de m em I menos 1, e adicionar a ele o valor de n menos dois neste caso. Como podemos ver, se formos em frente e retornar o valor de e no final, o que vamos obter realmente como o valor correto deste 20000 aqui. Então, se eu executar este código, eu vou obter 93637285. E esta é a sequência correta de Fibonacci em um índice específico de 20000. Então nós apenas nos livramos dos problemas StackOverflow que costumávamos ter usando memoização e nós já usamos tabulação nesta solução. Então isso dito basicamente para a memorização e tabulação, o que vamos fazer a seguir é realmente resolver alguns dos mais famosos problemas de programação dinâmica usando memoização e tabulação. Então o que vamos fazer é ver o problema, ler através dele, e trabalhar através de um exemplo de um tentou resolvê-lo usando uma mão. E depois disso, vamos criar ou apenas gerar um pseudo código. E isso nos ajudará a implementá-lo em nossas linguagens, Java, JavaScript e Python. Assim, o esquema de nossos custos será o seguinte. Vamos ter o problema do que o pseudocódigo e, em seguida, a implementação. Então é isso, basicamente o que este vídeo vê você no próximo. 6. Número mínimo de contas para devolver uma quantidade: Tudo bem, então neste vídeo vamos passar por um dos exemplos mais populares que geralmente é resolvido com programação dinâmica. E o problema é assim. Então imagine que você tem uma loja e um cliente entra e encomendou com $60 em comida. Agora ele te entrega uma nota de 100 dólares e, neste caso, você vai devolver os restos, que são os 40 dólares. Então, por exemplo, vamos supor que temos 100 dólares e ele compra com 60 dólares e deve devolvê-lo. Agora, para o bem deste problema, vamos supor que temos quatro tipos de sinos. Então vamos supor que temos a nota de 1 dólar. Eu escrevo aqui mesmo. Então nós temos o cheiro e é o $1, nós temos os cinco dólares. Nós também temos 10, e nós também temos o 25. Então é isso. Então nós temos esses quatro tipos de sinos. Agora, se quisermos resolver este problema usando um algoritmo ganancioso, vamos tentar aqui mesmo. Para este exemplo, temos um retorno de $40. E neste caso, o algoritmo ganancioso é assim. A primeira coisa que vamos fazer é procurar a maior conta possível com a qual podemos pagar. Então, neste caso, devemos devolver $40. Então deixe-me escrevê-lo aqui. Então estes são os $40 que devemos devolver. Agora vamos verificar ao lado destes quatro tipos, qual é a maior quantidade que podemos extrair deste 40? Neste caso, temos o 25, então $40 menos 25. Então usamos isso 11 vezes. Agora vamos ter 15. E neste caso, também temos um 10 que é menor que 15, então 15, podemos extraí-los. Então, usamos este 10 também uma vez. E isso nos deixará com cinco e depois escapa. Finalmente, temos cinco menos cinco, que é igual a 0. Para resolver, também usamos este 5 uma vez. Então acabamos com 25 mais 10 mais 5. E neste caso, esse algoritmo ganancioso realmente funciona e nos dá a solução mais ideal, que é usar notas de 25, 10 e 5 dólares. Agora, imagine que nós também temos uma nota de 20 dólares em vez de apenas ter esses quatro tipos. Então deixe-me deletar tudo isso e vamos tentar de novo. Então, se eu tiver aqui mais notas de 20 dólares, e vamos tentar o algoritmo ganancioso mais uma vez. Neste caso, agora já temos dólares inadimplentes que devemos devolver. E neste caso, o algoritmo ganancioso funcionará exatamente como antes. Então vamos procurar o cinto mais ou o maior que podemos extrair deste $40 deve ser menos do que este $40. No entanto, temos 25. Então, estamos bem. Ficaremos com 15. E neste caso, se quisermos trabalhar com 20 dólares, não podemos, porque agora temos 15. Precisamos procurar por qualquer coisa que seja igual ou inferior a 15. E este caso. E então vamos ficar com a mesma coisa que antes. E esta não é claramente a solução ideal. Então, a solução ideal é simplesmente usar as notas de 20 dólares vezes duas. Então vamos usar essas notas de 20 dólares duas vezes e vamos conseguir os 40 dólares que precisamos para retornar ao cliente. E neste caso, como você pode ver, o algoritmo ganancioso não vai funcionar. Na verdade, não será a solução ideal. Então vamos usar programação dinâmica em vez disso. Então deixe-me limpar tudo isso e vamos passar por outro exemplo usando o método de programação dinâmica. Certo? Então este é outro exemplo. Então temos $7 que devemos devolver e temos os cintos 1, 3 e 4. Neste caso. Estes sinos constituem os que desenhamos antes. Então não se preocupe com isso, ajusta com eles e aliste-se. E neste caso, o que vamos fazer é construir uma matriz ou uma lista. E vamos falar sobre isso em um segundo. Mas antes de tudo, deixe-me apenas construir e este array será upsized, este sete mais um. Então, neste caso, eu vou apenas desenhar sete. Tudo bem aqui, então 3, 4, 5, 6, 7. E como dissemos, alguns mais um, que é um caso S, os índices serão 0, 1, 2, 3, 4, 5, 6 e 7. Então, como dissemos, temos oito elementos nesta lista. E o que vamos fazer é passar por esta lista de sinos um por um e verificar se há uma possível implementação de uma possível adição neste quadril direito. Então, em outras palavras, o que vamos fazer é verificar, por exemplo, se só temos uma nota de $1, o que vai acontecer com estes aqui? Então, neste caso, vamos tentar com a nota de $1. Então, por exemplo, se tivermos este $1, mas quantas notas precisamos para constituir o 0? E, neste caso, não precisamos de nenhum construído, então nós apenas escrevemos 0. Então este é apenas um caso básico. Agora, vamos supor que precisamos devolver $1. Quantas notas de $1 precisamos para devolver $1? Só precisamos de um. Agora, vamos passar para o segundo. Então, por exemplo, se tivermos, precisamos devolver $2. Quantos $1 conta fazendo isso para retornar esses $2 só precisaria de $1 contas. Então, neste caso, o que estamos dizendo que precisamos de $1 contas para retornar o valor que é $2. Então, para tornar isso um pouco mais fácil, estes são o valor e estes são simplesmente o número mínimo de contas que devemos devolver neste caso. Então o que estamos dizendo aqui é que nós só temos esta nota de $1, e este é o número mínimo de notas de $1 que devemos devolver se quisermos ter esses valores. E bem, sem passar por tudo isso, é a mesma coisa. É bem simples. Precisamos de notas de 3 dólares para devolver uma quantia de 3. Precisamos do 4567. Então é isso. Basicamente, é disso que precisamos. Deixe-me apagar isso e vamos continuar com isso. Então, neste caso, acabamos de passar pelo $1 bem aqui. Então o que precisamos fazer agora é checar os $3. Agora vamos supor que nós apenas, nós não temos apenas um diabetes. Temos o $1, bem como os $3. Mas neste caso, o que vamos fazer é verificar desde o início. Então, em 0, quantas notas de dólar precisamos para representar o valor 0? Não precisamos de nenhum. Agora, três, quantas notas de $3 precisamos para representar uma que possamos para evitar uma com notas de $3. Então, passamos para dois. Neste caso, vamos verificar também e viemos apresentar dois com notas de $3. Então, vamos passar para este três aqui. E neste caso nos perguntamos, quantas notas de US$3 precisamos para representar esse valor de US$3? E a resposta é bem simples. Não precisamos de três, só precisamos de um. Agora, o que estamos dizendo aqui é que precisamos de uma nota de três dólares para representar esse valor. E vamos passar para o quarto. Então, quantos bits precisamos para representar esses quatro? E na verdade nós só precisamos de contas, que é a nota de US $3 mais a nota de US $1 para apresentar isso para. Então nós não precisamos de cintos, nós só precisamos e este caso, é três mais um. Então, o que fazemos? Cancelamos isso e substituímos aqui também. E quanto aos cinco dólares, quantos bits precisamos para apresentar a quantidade de 5? E, na verdade, precisamos de três bits. Essa é a nota de $3 mais um mais $1, então é de 3 anos bem aqui. Quanto ao sexo, e quantos pedaços precisamos para apresentar o sexo? Nós realmente precisamos, apenas para lembrar que três, nós temos quantos quisermos. Então, em vez de representá-lo com seis, podemos apresentá-lo, representado com dois três. Neste caso, só precisamos passar para o sétimo. E neste caso, o que vamos fazer é usar nascimentos de 3,3 dólares, sinto muito. E isso é $2 a $3 notas e $1 nota. E neste caso, vamos acabar com algo assim. Temos 01212323. Agora, vamos passar para a final. Isto é representar o quarto. Então agora também temos o cinto de $4. Neste caso, temos os números 1, 3 e 4 dólares todos de uma vez e podemos usar todos eles neste caso. Agora o que nós vamos fazer é pular todos esses até os quatro porque nós não podemos representar nenhuma das quantidades menores, 0, 1, 2 e 3. E nós vamos até o quarto. E neste caso vamos nos perguntar como antes, quantas notas de US$4 precisamos para representar o valor padrão do dólar? E a resposta é uma. Então, quantos? Para notas de dólar ou qualquer sinos, precisamos apresentar os cinco e a resposta é bastante direta. Ou seja, precisamos de $4 nota mais $1 nota. E neste caso, há dois. E a mesma coisa vale para isso. Então aqui temos dois. E é claro que vamos verificar. Então agora temos também quatro. Então quatro mais um mais um é igual a US $6. Então, neste caso, usamos três cintos, e isso não é ótimo. Já temos uma solução que funciona melhor com duas correias. São as notas de 2 $3. Se tivermos três ou dois, escolheremos ficar com estes dois. E finalmente, se vamos pedir a nós mesmos o último, são os $7. Neste caso, vamos precisar de 4 $3. Então pode representá-lo com três em vez de um conjunto de três. Então é isso. Basicamente, foi assim que chegamos com uma resposta finita. Ou seja, podemos representar esse valor usando apenas dois sinos. Então isso é tudo para a idéia do trabalho através de agora. Pequeno pseudocódigo para ver exatamente o que está acontecendo e como podemos pensar sobre isso dessa maneira. Então, o que dissemos quando tínhamos três ou quatro anos? Nós dissemos que podemos ignorar todos estes, 43 já que eles são menores que três. E vamos denotar isso, na verdade, pelos sinos bem aqui. Então estas são as crenças que temos. Estes são o número mínimo e este é o valor. Agora, neste caso, se o sino, então os sinos são 1, 3 e 4, então sino significa 12 ou três. E neste caso, se este projeto de lei é menor ou igual ao valor que nós, que estamos procurando. O que vamos fazer é atualizar o número mínimo. E se voltarmos ao nosso exemplo, podemos ver que o número mínimo deve ser uma de duas coisas. Ou é este aqui ou precisamos atualizá-lo como aqui. Então, por exemplo, 012, não precisávamos atualizá-los. Então eles enviaram os mesmos ou os atualizados, seja, 1, 2, 2 e 2, como podemos ver acima. E neste caso, como conseguimos esses números atualizados? Então, se olharmos para os quatro neste caso e estas quatro notas, o que realmente fizemos é que nós pegamos este quatro de cada uma das quantias que nós. Então vamos pensar sobre isso por um segundo. Então, por exemplo, neste caso, quando tínhamos esses cinco aqui, então temos $5 para devolver. E neste caso, o que fizemos foi subtrair $4 daqui. Então temos 5 menos 4, então ainda temos $1. E neste caso, o que vamos fazer é olhar para o valor de $1 bem aqui na tabela. Este é o valor de $1. E neste caso, o que fizemos foi que pegamos esse número mínimo aqui e adicionamos a quantas notas, quantas notas de US$4 usamos? Aqui? Só usamos uma nota. Isso é o $4 e ainda precisamos devolver o valor que sobra que é $1. Neste caso, o conjunto de dados aqui. Temos um bem aqui. Então esta é a quantia que devemos devolver. Então 1, 4 notas de dólar mais 1 nota de $1. E neste caso, a resposta é dois, como podemos ver, que é usar esta fórmula. Então o que vamos fazer depois disso é que vamos escrever pseudocódigo para isso, na verdade. E então vamos implementá-lo em Java. 7. Código do problema: Certo, agora que sabemos como esse algoritmo funciona, e passamos por um exemplo real. Já sabemos a ideia por trás disso. Agora, vamos tentar criar um pseudocódigo que vai nos ajudar e nosso código escrever um pouco. Então, se quisermos passar pelo pseudocódigo, como dissemos, a nota pesada é menor que a quantia. Neste caso, o que vamos fazer é que vamos atualizar este número mínimo aqui. Então o que vamos fazer é passar por toda essa lista para cada um desses cintos. Então vamos ter dois para loops aninhados um no outro. O primeiro é será, será o ciclo de contas contas, e o segundo será o número mínimo que vamos atualizar cada vez que passarmos pelo número. E neste caso, o que vamos fazer é atualizar o número mínimo cada vez que a conta for menor ou igual ao valor. Neste caso, por exemplo, tivemos para o exame 4, 3 projeto de lei. Nós já temos este 012 e há menos que três, então não precisamos atualizá-los. Começamos com a quantidade que é maior ou igual, este cinto bem aqui. Então, como dissemos, começamos a partir daqui até o fim para cada um dos cintos bem aqui. Então o que vamos fazer é verificar o mínimo entre duas coisas. Como dissemos, o mínimo entre este número aqui e o número real que podemos atualizar. Então o que precisamos fazer é mudar o número mínimo. O número mínimo a este montante específico deve ser atualizado. Neste caso, será igual a 2, uma das coisas que é o mínimo entre eles. Assim, será igual aos homens entre a primeira coisa e a outra. E como dissemos, a primeira coisa é a quantidade real que já temos. Então, será o número mínimo do valor. Então é o mesmo que antes, ou precisamos ter um menor. Então o que estamos realmente fazendo é simplesmente verificar se nossa nova solução é melhor do que a outra. Então, como dissemos aqui, já temos essa solução 01234567, e eles são representados com esta nota de $1. No entanto, para a quantidade de três, por exemplo, podemos representá-lo com a quantidade de 3, 0, a nota de três dólares. Neste caso, removemos esses três sinos e acabamos de adicionar um cinto é $3. E neste caso, é muito melhor e mais eficiente usar nota de dólar 13 em vez de 3 notas de $1. Então o que nós realmente fizemos aqui é que nós pegamos este valor três e apenas, apenas, apenas atacamos a conta S3 daqui. Então sobrou com 0. E este caso nós fizemos todo o caminho de volta a quantidade de 0 e nós olhamos para este número mínimo e neste caso 0. E então o que nós realmente fizemos é que nós só usamos uma pílula bem aqui. E, em seguida, verificamos este valor 0. E nós realmente usamos um sino 0 aqui. E isso nos deixará com um antígeno de sino. Então é por isso que temos três aqui. E a mesma coisa vale para este seis aqui. O que realmente fizemos foi que usamos 2 notas de $3. Então nós este x aqui, menos duas vezes três, que é igual a 0. Então este três é usado duas vezes. Então use tuplas. E nós fizemos todo o caminho de volta para o número mínimo ou a quantidade de 0 e nós verificamos que é o número mínimo, que é na verdade 0. Então nós, usamos 02 menos 0 para mais 0, desculpe, é igual a dois. Então acabamos tendo que bater nele. Então este é o trabalho real através. Então, se você quiser pensar sobre isso de outra maneira, para estes seis cintos bem aqui, o que nós realmente fizemos é que nós dissemos que ou 6 notas de US $1 ou outra coisa usando estes três, Dahlberg bem aqui. E neste caso, o que realmente fizemos foi que acabamos de pegar essa nota de US$3. Então são seis menos três. E neste caso, acabamos com três, certo? Então, só usamos uma nota daqui. E então verificamos a quantidade de três, que está bem aqui. Quantos, qual é o número mínimo neste caso que precisamos acabar com um retorno de todos os montantes que temos neste caso para três, podemos ver claramente que é um. E foi assim que conseguimos um sino mais 1, que é igual a duas notas. Então é isso. Esta é uma ideia geral. Se tivermos multiplicação neste caso, podemos usá-lo diretamente. No entanto, este é o caminho real. Então deixe-me, deixe-me deletar isso e estamos bem. Podemos continuar. Então aqui nós, Sr. Bem, eu sinto muito. Então aqui temos o Bill. Então, se o projeto é menor do que montar, como dissemos anteriormente, precisamos atualizar o número mínimo, que será igual ao mesmo ou o, nós adicionamos um, como dissemos. Então é uma nota mais o número mínimo no valor menos a conta. Isso faz sentido. Então deixe-me escrever e depois explico. Então mínimo entre a quantidade real que temos menos o cinto que nós pad que temos. Então é basicamente isso. Agora, se quisermos passar por este exemplo usando esta fórmula, vamos em frente e fazê-lo. E, claro, não vou passar por todo o exemplo. Só vou tomar situações específicas. Então, por exemplo, vamos supor que estamos neste cinco aqui. E só temos as notas de 3 dólares que podemos representar este 51 e este caso o que vamos fazer. Então, estamos nesta fase bem aqui. E vamos pensar no processo. Temos estas notas de 3 dólares. E neste caso, o que vamos fazer é adicionar um. Então, ou é o mínimo entre duas coisas, certo? Então, ou é este aqui, que é cinco. Você não vê isso agora porque nós apenas removemos antes, mas está bem aqui. E este é cinco. Então são cinco ou outra coisa. E usar esta fórmula é um mais a quantidade mínima, mínimo entre quantidade, mente, espírito. E neste caso, o que vamos fazer é, então são cinco ou um, mais. Nós estamos indo para percorrer todo o caminho para o número mínimo de quantidade. Neste caso, o valor é cinco. O Cupido construtor é três. Então o número mínimo adicionar 5 menos 3, que é número mínimo em dois. Neste caso, vamos olhar para isto. E como podemos ver, temos o número mínimo neste caso é dois. Então 1 mais 2, que é 3. Então o mínimo entre 53 é na verdade três. E isto é o que temos aqui, é o número três. Então podemos representar as notas de $5 com uma nota de três dólares e notas de $1. Então é isso. É assim que podemos usar esta fórmula. E se for tentar pela última vez, podemos tentar por este aqui. Então, antes disso, tínhamos um três aqui. E neste caso o que estamos realmente fazendo é que vamos adicionar um para a nota de dólar. Então deixe-me deletar isso e vamos continuar. Então o mínimo entre duas coisas, a quantidade real que temos ou o número mínimo real que já temos, ou precisamos atualizá-lo adicionando um para a nota de dólar. Então ele tem um. Além disso. Nós vamos para o número mínimo na quantidade que é 7 menos wL, que é 4. Então 7 menos 4 é 3. Então, vamos até este três aqui. Vamos olhar para o número mínimo. Neste caso, é um. Vamos adicionar um aqui, então é o mínimo entre 32. Então a resposta é dois. É isso. Basicamente é assim que podemos usar esse pseudocódigo para nos ajudar a escrever nosso código agora, esta é a parte mais difícil. Nós apenas surgiu com este método real ou algoritmo real ou idéia que podemos usar para resolver o problema específico. E usando esse método, conseguimos encontrar a solução mais ideal. Ao contrário do algoritmo ganancioso que tínhamos no início. Neste caso, como dissemos, podemos representar este $7 construído com um para notas de dólar e 13 crédulos. E neste caso, a resposta é dois. E com isso dito, este é o fim do pseudo código aqui. E o próximo vídeo vamos implementar nossa função usando Java. Então, vejo você então. 8. Implementação de Java mínima: Certo, então agora que sabemos como esse algoritmo funciona exatamente, e escrevemos o pseudocódigo que vai nos ajudar em nosso código passo a passo. Agora mesmo. Podemos começar com a codificação. E, na verdade, este é um dos mais importantes, mas você deve sempre começar com isso, algo assim. Então você pode escrever seu código ou escrever seus pensamentos em um pedaço de papel e talvez desenhar algumas coisas. Neste caso, desenhamos esta lista e atualizamos cada vez que passamos por um sino. Então você tinha sido uma necessidade de trabalhar com uma caneta e papel e não apenas visualizar todas as coisas dentro de sua cabeça. Especialmente em programação dinâmica. Porque visualizar algo ou você teve trabalhos geralmente frustrar problemas mais simples. No entanto, em alguns problemas profundos ou complexos, você sempre precisa usar uma caneta e papel. E neste caso, vamos ao nosso Eclipse. E neste caso o que vamos fazer é começar com a criação da função. Então eu vou simplesmente, nós só precisamos Min retorna o número mínimo de mudança, que é um número inteiro e uma função vazia número mínimo, neste caso, o que nós vamos levá-lo, a quantidade que irá retornar e é denotado por N. E quantos ou o tipo de cintos que temos. Neste caso, vamos chamá-los de sinos. Então vamos abri-lo e vamos começar com implementado isso. Então a primeira coisa que vamos fazer é criar esta lista que falamos anteriormente, e este é o número mínimo. Então, para criá-lo, vou simplesmente criar uma lista de números mínimos. E é realmente contradiz o, é o mesmo que o método, certo? Quatro, tão íntimo diferente. E neste caso, este será o tamanho, o número ou a quantidade de mais um, como dissemos. E o que vamos fazer é primeiro preenchê-lo com o valor máximo que pudermos. Então vamos usar matrizes que sentiram. E o que vamos fazer é preencher esses sinos com inteiro, esse valor máximo. É assim que podemos armazenar o máximo de valor inteiro aqui. E parece que precisamos importar arrays. Então nós apenas tentamos o espaço de contraste, pressione Enter, e ele vai apenas levá-lo aqui. Agora, esta área, bom que não devolvemos o número inteiro ainda, mas podemos lidar com isso mais tarde. Mas por enquanto, o que vamos fazer é lembrar que sempre queremos começar com uma quantidade de 0. Portanto, o número mínimo deve ser 0. Neste caso, o que vamos fazer é armazenar e o, sinto muito, não é duplos é o número mínimo aqui. E nós vamos começar no número mínimo em 0, nós vamos armazenar 0. Então este é o primeiro passo. Agora vamos passar por todos os dados reais. Então o que vamos fazer é passar pelo ônibus e dentro de cada um, bem, nós vamos passar através da quantidade neste caso. Então int eu igual a 0 todo o caminho para os sinos, esse comprimento e, em seguida, atualizado. Agora, o segundo será j igual a 0. Então J é menor que o número mínimo. Eu sinto muito. Então aqui eu adicionei S por engano. E agora estamos bem. Então vamos percorrer todo o caminho até o número mínimo que o comprimento e, em seguida, atualizado. Agora, o que vamos fazer é verificar se a campainha é menor que a quantidade. Então, como você faz isso? Simplesmente verificamos se os sinos em mim são menos do que algo, que é a quantidade. E neste caso, a quantidade é, na verdade, o índice. Como podemos ver, a quantidade é o índice desta matriz número mínimo ou menos. Então é, se for menor ou igual a essa quantidade, nós vamos fazer algo sem nada. Nós vamos, nós não vamos fazer nada. Neste caso. O que vamos fazer é pegar a diferença entre este valor e o sino. Então, podemos dizer que este j é a quantidade e contas no ISB sino real. Então a diferença será j menos sátira cinto. E também queremos calcular o sino neste caso. Então eu estou indo para denotado por talvez ele pode ser o número mínimo neste caso, novamente, eu apenas denotado por B. E o que nós vamos fazer é adicionar este mais o valor ou o número mínimo. Essa diferença. Então o que nós realmente fizemos aqui é que nós calculamos a fórmula. A fórmula diz que é o número mínimo. E o mínimo. Este é o novo atualizado. Será um mais este aqui. E como calculamos isso é que nós realmente pegamos o número mínimo e quantidade menos sino e isso o atinge. Então 1 mais 1 mais o número mínimo. Então é assim, este é o número mínimo no valor menos a conta. E calculamos a diferença apenas na linha anterior. Neste caso, temos o que pode ser atualizado. Então, neste caso, o que vamos fazer é voltar. Só disse que cintos em I será a matemática, mas os homens. Então é uma de duas coisas. É a desculpa, o número mínimo na I e J. Sinto muito. E será uma de duas coisas. Será o mesmo que antes e, ou o BI que acabamos de criar anteriormente. E neste caso, podemos atualizar esses números mínimos facilmente. Então o que fizemos na verdade é que pegamos a diferença entre o valor e a conta, calculamos que o número mínimo, apenas calculamos essa fórmula e temos isso aqui. Em seguida, dissemos que o número mínimo a este montante deve ser igual ao número mínimo neste em torno ou um mais o número mínimo de quantidade 2012. E este caso, nós o temos aqui, nós o atualizamos. Então, ou é o mesmo ou o que é TBI. Agora, o que vamos fazer é verificar se o número mínimo no final ou no sim. Assim, na quantidade não é igual ao valor Emax. E você vai dizer o porquê em um segundo. Nós vamos retornar o número mínimo em e então retornar menos um. Então o que nós realmente fizemos aqui é que nós verificamos, nós podemos realmente fazer ou devolver esse valor. Neste caso, se pudermos obter esse último valor não deve ser o valor máximo. Deve ser um número natural. E se for esse o caso, devolvemos este número. E se não, vamos retornar menos 1, mesmo que não podemos calcular ou não podemos ter este retorno com esta, esta estratégia de projeto de lei. E um exemplo disso é imaginar que precisamos devolver uma nota de $5 ou $5 e temos apenas 78 duplos. Neste caso, não podemos devolver cinco porque só temos 78. Então é por isso que isso sempre será valor máximo e não podemos retornar o valor, então nós apenas retornamos menos um. Então essa é a implementação. Acho que é bem simples depois de toda a explicação que fizemos aqui e passamos por ela. E isso é tudo para este vídeo. Vejo-te no próximo. 9. Implementação de JavaScript mínima: Ok, então neste vídeo vamos implementar nossa função ou o pseudocódigo que criamos anteriormente usando JavaScript. Então, sem mais delongas, vamos direto ao assunto. A primeira coisa que eu vou fazer é criar o nome da função na mudança mínima. E, neste caso, levará e contas como parâmetros. Vamos abrir. E neste caso, o que vamos fazer é criar uma matriz em JavaScript. Podemos fazer isso. Vamos dar um nome a ele. Vamos dar um nome a ele. Na verdade, a quantia. E o que não queremos fazer é pegar essa quantia. E é claro que vamos passar por tudo isso daqui a pouco. Mas por enquanto, o que vamos fazer é criá-lo como uma matriz de um mais 1. E nós vamos preenchê-lo com infinito. Então é isso, basicamente isso, como podemos criar uma matriz em JavaScript. Agora o que vamos fazer é atualizar esse valor para o primeiro deve ser igual a 0. Então, se voltarmos a este, podemos ver que este montante deve ser igual a 0. Na verdade, vamos nomear números mínimos, já que fizemos isso aqui, número mínimo. Então nós vamos apenas, eu ouviria o número mínimo. A mesma coisa se aplica aqui. Agora o que vamos fazer é criar o nosso loop for. Então a primeira coisa que vamos criar é o loop for para os sinos. Então o que vamos fazer é criar, construir e sinos, sinos, e depois abri-la. Agora, o segundo será para o número mínimo real. E nós vamos denotar esses índices por quantidade, como dissemos aqui. Então vamos criá-lo aqui para o laboratório. Quantidade igual a 0, então a quantidade deve ser menor do que o número, número mínimo que o comprimento. E então, claro, vamos incrementar o valor. Agora vamos abri-lo e agora podemos começar com o nosso código real. Vamos simplesmente escrever o pseudocódigo que escrevemos anteriormente. Então diz que se o valor for maior ou igual à conta, precisamos fazer alguma coisa. Neste caso, o que vamos fazer é atualizar o número mínimo, que será igual, deve ser igual ao mínimo entre duas coisas. Então vamos usar homens de método. E este mínimo será o número de número mínimo de quantidade e o número mínimo de valor menos a conta. Agora o que vamos fazer, é claro que aqui precisamos adicionar um. Então é o número mínimo de quantidade menos p mais 1. E neste caso, estamos realmente feitos com esta função. É assim que podemos implementá-lo usando JavaScript com este pseudocódigo que criamos anteriormente, com apenas usando o importante significava tomar o mínimo entre essas duas coisas. E, claro, vamos preenchê-lo com infinito. E não se esqueça de preencher o primeiro com 0, uma vez que é como o caso base aqui. Agora o que vamos fazer é simplesmente devolver estes aqui. Portanto, tenha em mente que se esta função funcionar corretamente, ela deve atualizar a última. No entanto, às vezes podemos ter o infinito no final. E neste caso, se você tem infinito, isso significa que não resolvemos o problema, não há solução adequada. Então deixe-me dar um exemplo para tal coisa que suponha que temos os cinco dólares para representar e temos 678 também. Neste caso, não há solução adequada e este último infinito não será atualizado, uma vez que $5 não pode ser representado com 67 ou $8 notas. Então o que vamos fazer é verificar se este último é igual ao infinito, vamos retornar menos 1. Caso contrário, vamos devolver o número mínimo real que temos. Então agora, se nós realmente devolvermos isso, deixe-me apenas devolvê-lo aqui para que o número mínimo de retorno em, e o que nós fizemos para obter um simplesmente o último na lista. Então esta é a lista que vamos obter 0, 1, 2, 1, 1, 2, 2, 2. E vamos conseguir o número mínimo. Agora, para deixar mais claro, eu vou devolver a lista inteira no início e depois vamos discutir isso. Então a variável n será igual a realmente os dados reais aqui, que é sete. E o último seria 1, 3, 4, assim e igual a sete. E a lista será igual à lista 134. E neste caso, o que vamos fazer é chamar essa função mínima de mudança com um e contas. E é claro que vamos fazer login. Então console.log e sorte esta função. Agora, se voltarmos aqui. E vamos para JavaScript, programação dinâmica. E o que vamos fazer é simplesmente usar homens de nó, mudar esse JS e vamos obter 0, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, que é exatamente a mesma coisa que geramos anteriormente manualmente. Fazer agora é retornar o último usando o número mínimo em. E agora, se voltarmos e grandiosos novamente, teremos duas como o número mínimo de mudanças que precisamos para apresentar um número específico. No entanto, se por exemplo, não temos isso. Suponha que temos cinco. Neste caso. Suponha que temos 678 como cintos. O que vamos conseguir é, na verdade, infinito e esta não é uma resposta correta. Precisamos retornar menos um. Neste caso, simplesmente precisamos verificar se o número mínimo em n é igual ao infinito. Este é o caso. Vamos atualizá-lo para menos 1. Então, há várias maneiras. Então, por exemplo, uma maneira de fazer como se esse número mínimo fosse igual ao infinito, mas não fazemos é simplesmente retornar ou atualizar. Então, se for igual ao infinito, vamos, desculpe, precisamos adicionar os colchetes para que o número mínimo em n seja igual ao infinito. Vamos atualizá-lo para menos 1. Agora, se voltarmos e apertarmos a atualização, vamos ter menos 17 f infinito. Outra maneira de fazer isso é simplesmente verificar ao lado da declaração de retorno. Então, para fazer isso, simplesmente verificamos se esse número mínimo é igual ao infinito. Se for esse o caso, precisamos fazer alguma coisa. E para fazer isso, nós simplesmente escrevemos este ponto de interrogação e então temos duas opções. Portanto, esta afirmação está satisfeita. A primeira opção será, então parece algo assim. Então, se esta equação for satisfeita, se ela retornar true, nós vamos obter essa opção. Caso contrário, vamos pegar o segundo. Então, se isso é verdade, mas vamos fazer é retornar menos1. Caso contrário, devolveremos o número mínimo na Penn. E vamos verificar de novo. Se voltarmos e corrermos de novo, teremos menos 1 como antes. Agora, por exemplo, se tivermos isto aqui como bronzeado, e vamos voltar, executá-lo novamente. E, claro, não deveria ser, deve ser múltiplo de seis, por exemplo. Agora, se voltarmos e corrermos, teremos duas como o número mínimo de mudanças que podemos ter usando este 12 e essas notas como o valor. Então é isso basicamente para esta implementação. É assim que podemos implementá-lo em JavaScript. Dito isto, este é o fim deste vídeo. Vejo-te no próximo. 10. Implementação de números mínimos: Ok, então neste vídeo, nós vamos fazer é criar a função Python para o nosso pseudocódigo que nós criamos anteriormente. Então deixe-me apenas adicionar algumas coisas aqui porque o deletado. Então o que vamos fazer é determinar a função mínima deste aqui. Então deixe-me fazer maior. Então temos $7 e as mudanças ou mais profundas que temos são 1, 3 e 4. Então, para fazer isso, Vamos começar com a definição de nossos parâmetros imediatamente em Python. Então n igual a sete. E nós temos essa lista que é 134. E estes representarão dels de sabão das pessoas igual a 1, 3, 4. Agora podemos começar com a nossa função. Então o que vamos fazer é no início, precisamos criar essa lista de números mínimos e ela deve ser inicializada para o infinito. E depois disso, o que vamos fazer é adicionar ou modificar cada vez que passarmos por cada um desses elementos. Então, o que vamos fazer no início é criar a lista real simplesmente adicionando ou nomeando número mínimo. E será igual a um menos do que neste caso, o que vamos fazer é preenchê-lo com ele. E como podemos fazer isso, podemos simplesmente passar por um loop for na faixa de n mais um e depois preenchê-lo, preencher o número mínimo que vamos anexar a ele. Flutuar, indicando que isto é um infinito. Então agora um livre ir em frente e imprimi-lo. Nós vamos ver isso. Então, se eu ir em frente e imprimir este fora, nós vamos obter este infinito como os elementos nesta lista. Agora, para começar, vamos voltar aqui e ver nossa função, nosso pseudocódigo. Agora lembre-se que precisamos deste, que é o primeiro que será igual a 0. Então, antes de fazer qualquer coisa, vamos apenas torná-lo igual a 0. Então número mínimo em 0 para ser igual a 0. Agora podemos passar pelo nosso código, então deixe-me executá-lo de novo aqui. E como você pode ver, o primeiro é 0 e todos os outros são infinitos. Então o que vamos fazer agora é passar por 24 loops aninhados de rede. E enquanto fazemos isso, vamos passar por todos estes e, em seguida, atualizar todos estes. Então deixe-me apenas criar para Bell e cintos, vamos começar com aqueles e então vamos para o número mínimo. Então, para fazer isso, podemos simplesmente criar um segundo para loop usando um intervalo do comprimento deste número. Então é para a quantidade e intervalo do comprimento desta lista real que criamos. É o número mínimo. E o que vamos fazer no início é verificar se o valor é maior ou igual à conta. Nesse caso, se esse for o caso, precisamos atualizá-lo. E é uma das duas coisas de acordo com nossas fórmulas. É o mínimo entre a quantidade número mínimo real e ou um mais o número mínimo na quantidade menos derramamento. Então deixe-me apenas implementado aqui. Como é que fazemos isso? Então é o número mínimo na quantidade deve ser igual a duas coisas. O mínimo entre o número mínimo e número mínimo 1 mais o número mínimo no valor menos o, é isso. Basicamente, é assim que podemos implementá-lo. Agora, se voltarmos e vamos clicar em atualizar e executar este código novamente. Como podem ver, temos 0, 1, 2, 1, 1, 2, 2, 2. E se olharmos aqui, temos 0, 1, 2, 1, 1, 2, 2, 2. Então é exatamente o mesmo resultado. Agora tenha em mente que isso não é o que realmente precisamos. A solução real deste problema é obter o último bem aqui. Então vamos devolver o último daqui. Agora, uma coisa que precisamos prestar atenção é que talvez alguns, não há tal combinação que nos permita obter o número específico. Então vamos supor que temos os $5 e todo o denominador, tudo o melhor que temos, o nosso 678. Então, neste caso, podemos representar cinco usando qualquer uma dessas notas. Então a resposta permanecerá infinita. Neste caso, se a resposta for infinito, não retornamos o infinito, apenas retornamos menos um, indicando que não há solução para esse problema. Neste caso, precisamos prestar atenção e ter certeza de que obtemos esse caso de borda. Então, como é que fazemos isso? Podemos simplesmente criar uma declaração if se o número de moedas. Então, se o número mínimo é a quantidade, ou talvez se o número mínimo no último, que é n, é igual ao infinito. O que vamos fazer é deixar-me tentar fluir aqui. E se isso for igual a esse número, o que vamos fazer é retornar menos 1, menos 1. Caso contrário, vamos imprimir o número exato, número mínimo em. E então é isso. Basicamente, é assim que podemos fazê-lo. Agora, se voltarmos, pressione atualizar, e executar este código novamente, acho que temos um recuo não corresponde ao outro. Tudo bem, então vamos consertar isso rapidinho. Nós vamos fazer é fazer isso assim. E agora acho que estamos bem se voltarmos, executarmos de novo. E a resposta seria dois. Agora, neste caso, se tivermos o exemplo que dissemos anteriormente, temos 6, 7 e 8. Se voltarmos e atualizarmos, teremos menos um, indicando que não há maneira de obter esse valor usando esses três tipos de contas porque eles são maiores que cinco. Então é isso basicamente para este problema, é assim que podemos ser encontrados com Python. Dito isto, este é o fim deste vídeo. Vejo-te no próximo. 11. Número de maneiras para devolver uma quantidade: Tudo bem, então neste exemplo, vamos passar por outro problema, que é o número de maneiras que temos de fazer uma mudança para uma quantia específica. Então suponha que temos uma quantia de $5 que está bem aqui. E o que vamos fazer é calcular o número de maneiras que podemos representar esses cinco dólares se tivermos essas notas bem aqui. Então, se você tem 1.2.34 conta, e neste caso, o que vamos fazer é usar a programação dinâmica para ter a solução mais ideal ou o número exato de maneiras que podemos calcular usando essas contas para ter esse valor de US $5. Então, para fazer isso, vamos começar com a criação da lista que vamos precisar. E como dissemos antes, esses cinco dólares, vamos criar uma lista que pode fazer até $5. Então, para fazer isso, vamos ter o tamanho desta lista como cinco mais um, que é seis. E este caso, deixe-me apenas criar esta lista aqui. Então, temos 123456 elementos nesta lista. Assim, os índices são os seguintes, 012, dia 4 e 5. Então, esses índices representam a quantidade. Então deixe-me escrevê-lo aqui. Eu sinto muito. Então aqui temos a quantidade. E o que vamos ter aqui é o número de maneiras. Então eu vou apenas denotar isso como um número de maneiras. Então o que vamos fazer é passar por toda a base que temos um por um e então verificar o número de maneiras que podemos representar esses cinco dólares usando esses Belk aqui. Então, primeiro de tudo, o que vamos fazer é inicializar todos estes para 0. Então, 00000. No entanto, o primeiro seria o caso base. E é seguro dizer que este deve ser inicializado como um só. Já que se pensarmos nisso, se não tivermos oh, temos um $1 ou $2 ou três ou $4 notas e precisamos apresentar a quantidade de zeros. Há apenas uma maneira de representar esse valor simplesmente não tendo ou não usando nenhum desses valores. Portanto, é seguro dizer que podemos usar o número de maneiras como um para a quantidade 0. Certo? Agora, se olharmos para ele, vamos começar com este aqui. Então deixe-me mudar a cor. Então agora estamos trabalhando com esta nota de $1. Então, de quantas maneiras podemos representar a quantidade de um usando uma nota de $1? E é bem simples. Podemos representá-lo de uma maneira. Então, em vez de ter 0 aqui, vamos ter um. Agora, vamos passar para o valor de $2. De quantas maneiras podemos representar esse valor de $2 usando esta nota de $1? E é claro que é a mesma coisa. Só temos uma maneira que é usar 2 notas de $1. A mesma coisa aqui. Então vamos ter 111. Então o que estamos dizendo é que podemos representar este valor de 34 ou $5 usando $1 nota de uma e única maneira. E isso é usar, por exemplo, aqui se temos $3 quantia, então como podemos, como podemos obter essa quantia de $3? Podemos usar 3 $1 melhor a partir daqui. E é a mesma coisa por 4 $5. Agora vamos passar para o segundo. Ou seja, temos este $2, mas agora o que vamos fazer é simplesmente pular 01 quantidade desde que podemos apresentar esses valores usando uma nota de $2, porque dois é maior do que 01. Então vamos até esse valor de $2. Agora, vamos pensar sobre isso. O que é que nós temos? Temos essa quantia de $2, certo? E isso também temos essas notas de 2 dólares. Então, podemos representar estes $2 quantidade usando 1 $2 conta a partir daqui. E, claro, não queremos esquecer que podemos representá-lo de uma forma usando essas notas de $1. Então o que vamos fazer é remover isso e adicionar dois aqui porque podemos representá-lo agora de duas maneiras. E vamos descobrir a fórmula daqui a pouco, mas vamos resolver isso agora. Então, por exemplo, agora temos esse valor de $3. Então o que vamos fazer é também representado de duas maneiras, certo? Então deixe-me escrever aqui também, e vamos pensar sobre como podemos representar este valor três. Então, se tivermos $3, podemos usar duas, uh, três notas de $1. Então 3 vezes 1 ou 2, ou 1 para notas de dólar e 1 nota de $1, certo? Então, 12. Notas e 1 nota de $1. E nós vamos obter o valor que é três como antes. Agora, se voltarmos para aqui e vamos descobrir por quantas maneiras podemos representar esse valor. Então, se temos $4 e vamos precisar de de $1 ou de notas de dois dólares, ou 1 $2 mais 2 notas de $1. Então, se isso faz sentido, tudo bem se não fizer, vamos pensar sobre isso que temos aqui para notas de $1. E aqui temos, ou temos que fazer, para notas de dólar, ou temos 1 notas de $2 e 1 nota de $1. Então, tudo isso será o mesmo que você pode ver aqui. Se eu desenhar. Nós vamos ter aqui também, e aqui, a mesma coisa e nós temos para notas de $1. Então é basicamente isso. Agora, vamos pensar sobre a fórmula. Como podemos conseguir isso? Temos três maneiras aqui. Então temos três possibilidades de representar este número quatro. E em vez de ter um aqui, vamos removê-lo e adicionar três. Então, se pensarmos sobre isso, podemos ver que se tivermos essa nota de US$2,2 aqui, o que realmente fizemos foi que adicionamos um ao número de maneiras que tínhamos. Então, para deixar claro, deixe-me apenas escrever a fórmula aqui. Então o que estamos dizendo é que precisamos atualizar esse número, que é o número de maneiras em um índice específico. Suponha que é anúncio I. Será igual a um mais o número de maneiras. E deixe-me apagar tudo isso. E é o número de maneiras nesta quantidade específica, que é quatro menos o que obtemos daqui. E vamos nomear esta lista como notas e designar cada uma delas como a conta. Então é a quantidade menos cinto. Então, neste caso, se vamos olhar para este exemplo, estamos na montanha antes e na construção número dois. Então o que nós realmente fizemos foi que nós adicionamos este aqui. Então aqui não é um, é o número de maneiras. Então é mais 0 igual. E deixa-me apagar isto. Então é realmente igual a este número de maneiras em I, igual ao número de maneiras em I. Então o que já temos, o número real de maneiras mais o número de maneiras. Vamos ouvir este número de maneiras na quantidade menos contas. Então esta é a fórmula que vamos usar agora se você usá-lo aqui, vamos pensar sobre isso. Já temos um aqui. Então, o número de maneiras em, eu escrevo aqui, será igual ao um mais número de maneiras em 4 menos 2, que é igual a 2. Então, se voltarmos para o índice para ver que já temos dois aqui. Então vamos ter 1 mais 2, que é igual a 3. E isso é o que obtivemos usando o pensamento ou usando o exemplo que fizemos antes. Então descobrimos que temos três maneiras de representar esses quatro. Temos 1 notas de $2. Agora, vamos passar para o último que é cinco. E usando essa fórmula, podemos calcular que se tivermos o valor de US$5 e tivermos isso, essas tuplas, podemos ter uma maneira mais o número de maneiras em cinco menos dois, que é o número de maneiras neste índice aqui, três. Então são dois, então 1 mais 2 será 3. Agora, se fizermos exatamente a mesma coisa para os 34 que podemos conseguir. Então deixe-me mudar a cor. Deixe-me só tornar a tinta azul mais fácil. Então o que vamos fazer é cortar estes daqui e colá-los aqui. Vamos apagar isso e vamos continuar. Então o que estamos dizendo é que agora estamos no três. Então, como dissemos, podemos pular 012 porque eles são menores que três. Nós vamos até o três. E agora o que vamos fazer é dizer que podemos representar este Amar três usando duas maneiras mais o número de maneiras em três menos três. Então este valor menos este três aqui, que é o cinto. E se formos para o número de maneiras, três meses hoje é em 0, então nós temos um. Então, em vez de ter três aqui, vamos ter 2 mais 1, que é 3. Agora vamos fazer exatamente a mesma coisa para este. Então é 3 mais o número de maneiras em quantidade menos mil, que é quatro menos três, que é na verdade um. Então vamos mudar isso em 3 mais 1, que é 4. Agora vamos acabar com este arquivo, que é que temos 3 mais o número de maneiras em quantidade que é 5 menos o número de palavras, número de sinos, ou o cinto real, o que é ótimo. Então 5 menos 3 nos dará 2. E nós vamos olhar para ter aqui o número de maneiras, que é duas. Então vamos atualizar isso em três mais dois a cinco. Então, espero que isso faça sentido. Vamos continuar com este último, que é quatro. Agora nós temos o valor de quatro contas para jantar apenas computado para estes dois porque não faz sentido ter este quatro em 0123 uma vez que eles são menores. Então o que vamos fazer é levar este 4. Nós temos este quatro, que é o número de maneiras em I mais o número de maneiras em quantidade menos 12. Então, 4. Este é o valor menos antes do Bill. Então vamos obter o número de maneiras em 0. Então podemos ver que é quatro mais um é cinco. Então vamos levar estes cinco aqui. Além do número de maneiras em quantidade menos bem, que também é em um, porque o número de maneiras de 5 menos 4 que é igual a um. Então número de maneiras em um, indo para verificar se ele é igual a um. Então vamos atualizar isso para cinco mais um. Vamos acabar com seis. Então é isso. Basicamente é assim que podemos obter o número de maneiras usando o método de programação dinâmica usando esta quantidade específica. Agora o que vamos fazer é que pareceria, se isso for o exato, este é o número correto de maneiras. Então, se você tem essa quantia de $5 e nós temos esses quatro tipos de Bill, o que nós vamos fazer é representar este arquivo usando estes manualmente. Então vamos pensar sobre isso. Podemos ter quatro ou 5 notas de $1, ou podemos ter 2122 duplos mais 1 nota de $1. Ou também podemos ter duas ou 1 notas de $2 e 3 notas de $1. Ou também podemos ter 32. Então 1 nota de $3 e 23 notas de dólar e 12 dólares lado de negócios. Ou também podemos ter e 1, assim 1, 4 notas de dólar e 1 $1 nota. Então estes cinco ou nós também podemos ter o 311, então notas de 13 dólares e notas de US $1. E isto se os contarmos, 123456. Então vamos acabar com seis maneiras de representar essa quantia de US$5 usando esses quatro tipos de pessoas. Então, espero que isso faça sentido. No próximo vídeo, vamos simplesmente escrever o pseudocódigo disso e então vamos implementá-lo em nossas línguas. Então, vejo você então. 12. Número de maneiras: Tudo bem, então neste vídeo que vamos fazer é resumir nossos pensamentos e realmente escrever um pseudocódigo que vamos usar quando implementarmos essa magnitude, este algoritmo agora código. Então deixe-me deletar tudo isso. E, claro, tudo isso também. Então agora podemos continuar. Agora vamos pensar sobre isso por um segundo. Então o que nós realmente fizemos é que cada vez que vamos usar um trabalho com um cinto. Então deixe-me escrever as pílulas aqui rápido. Então, cada vez que vamos trabalhar com uma conta daqui, vamos adicionar ou atualizar esse número de maneiras. Então o que vamos dizer é que se a quantidade for menor que este sino real, não vamos fazer nada. Nós vamos simplesmente pular. Então o pseudocódigo deve ser assim. Então a primeira coisa que vamos fazer é verificar se a quantidade é maior que o cinto. Mas este é o caso. Vamos continuar. Assim, o valor é maior ou igual ao projeto de lei que temos. Vamos fazer alguma coisa. Neste caso, o que vamos fazer é atualizar o número de maneiras neste cinto real, certo? Então o que vamos fazer eu sinto muito, neste valor real. Então o que vamos fazer é atualizar o número de maneiras. E neste caso, será no valor real. Nós vamos atualizá-lo para. Será igual a duas coisas somadas para ser igual ao número real de maneiras que realmente temos agora. Por isso, será igual ao número de maneiras em quantidade. Podemos adicionar algo novo, que é o número de maneiras em quantidade menos um. Então, será igual ao número de maneiras em quantidade menos o sino que temos. Agora, se você quiser ter certeza de que este algoritmo realmente funciona, vamos apenas fazer isso, por exemplo, às quatro e permite que você use o último aqui, que também é o sino para. Então o que vamos fazer é supor que temos aqui. Então estamos agora na fase em que temos o número de maneiras, que é quatro e vamos atualizá-lo. Então vamos olhar se o valor é maior ou igual à conta. E neste caso a quantidade é quatro, que é igual a quatro. Então isso realmente funciona. O que vamos fazer agora é atualizar o número de maneiras na quantidade específica. Então número de maneiras em quatro seria igual ao número de maneiras em quatro, que é quatro mais o número de maneiras em quantidade menos derramamento. Então o número de maneiras em quantidade meu feitiço, que é 4 menos 4, para ser igual a 0. Nós vamos para o número de maneiras. Pegue este adicionado ao 4 nos dará 5. Então agora podemos, sabemos que nossa fórmula real aqui que geramos é realmente verdadeira e funciona exatamente bem. Então é isso. Basicamente, isso é profundo para o tribunal. E, na verdade, isso é muito simples. Uma vez que você conhece o método, você pode criar este pseudocódigo. Então eu encorajo fortemente cada vez que você resolver o problema de programação dinâmica para escrever, escrevê-lo assim, e tentar chegar a uma solução. E tente criar o método real ou a fórmula real que é TB usado neste problema. Então, como a primeira parte do problema, não sabíamos que a fórmula iria apenas com o fluxo. Então, por exemplo, aqui, nós apenas dissemos que no valor 0, nós não podemos representar de qualquer maneira diferente uma e única maneira que é não usar qualquer quantia de dinheiro. Agora, na quantidade número um, podemos representá-lo se tivermos este $1, mas podemos representá-lo por um. E aqui o mesmo para os outros. E então não foi até essa quantidade número três que conhecíamos a fórmula. Eu sinto muito. Não foi até a soma do número quatro que conhecíamos essa fórmula. E calculamos usando este exemplo aqui. Então sempre comece com um exemplo e tente chegar a uma fórmula mais tarde. Então é isso. Basicamente, isto é para o pseudocódigo. No próximo vídeo vamos implementá-lo e nosso código real. Para te ver, então. 13. Número de maneiras Java: Tudo bem, então neste vídeo nós vamos implementar nossa função, função que nós criamos anteriormente. E eu já instanciado este método público número int estático de maneiras. E temos dois parâmetros. O primeiro é a quantidade real indicada por N, e o segundo é os sinos reais. Então esta é uma matriz dessas bem aqui. Então o que vamos fazer é que vamos criar uma nova matriz como antes, como dissemos antes, que é implementar ou adicionar o número de maneiras para cada quantidade. Então deixe-me apenas instanciado como maneiras que será igual a 0 e mais um, como dissemos. Agora o que vamos fazer é denotar ou adicionar ao primeiro, como dissemos aqui é o primeiro deve ser igual a um. Então desperdício em 0 para ser igual a um. E o outro será igual a 0, que são o número padrão ou a maneira padrão de ser instanciado em um array. Então, como dissemos, já temos um aqui. O que vamos fazer é passar por todos estes aqui é de meio que passar por todos os que eu construí. E então, é claro, vamos atualizar o número de maneiras aqui. Então, vamos voltar. Agora, se pensarmos sobre isso, o que vamos fazer é pagar o loop para, começando com 0 todo o caminho para as contas que comprimento e atualizado. E o segundo, vamos ter também 0. Todo o caminho até, sinto muito, aqui podemos realmente dizer que é um. E os dois serão todo o caminho para os caminhos. Esse tamanho tamanho do ponto, desculpe, eu e J plus, plus. Agora o que vamos fazer no início é verificar se esse valor é maior ou igual à conta. E como dissemos, esta quantidade é na verdade no segundo para loop denotado como j. Nós podemos realmente mudar este j em quantidade de que vai nos fazer, torná-lo mais fácil. Então deixe-me mudar isso rapidinho. E então temos quantidade também. Agora o que vamos fazer é verificar se esse valor é maior ou igual à conta real. E o que dissemos? Nós dissemos que este será notado como contas. E a largura de banda da conta real será na melhor das hipóteses em I, que é 0, 1, 2, 3 e 4, assim por diante, assim por diante. E neste caso, o que vamos fazer é verificar se o valor é maior ou igual ao que será igual a contas em. Eu sei que este é o caso. Precisamos atualizar o número de maneiras. Então, as maneiras que eu, ou as maneiras que quantidade algum site será atualizado de duas maneiras em quantidade mais maneiras em, como dissemos, vamos usar a fórmula, quantidade menos isso aqui. Então, como conseguimos essa conta? Serão os sinos em I. Então, neste caso, o que dissemos que podemos calcular isso usando sinos em i. Então eu vou simplesmente escrevê-lo aqui em I e nós atualizamos com sucesso. Agora o que vamos fazer é apenas retornar o número de maneiras na última que temos. Então, se voltarmos aqui, só precisamos deste dele. Então este é o número de seis. Lembre-se que o propósito deste problema é que, se tivermos uma quantia de $5, quantas maneiras podemos representar esses cinco dólares? E nós realmente fizemos tudo isso para chegar com a solução final, que é um seis. Então, como podemos lidar com isso? Podemos simplesmente pedir o número de maneiras em nosso valor inicial, que é cinco. E será igual a seis maneiras. Então é isso, basicamente, agora, isto é o que devemos devolver aqui. Então, depois de terminar a partir destes dois para loops aninhados para loops, vamos representar as maneiras em. Então é isso. Basicamente isto é para este problema. Agora, se vamos testá-lo, podemos simplesmente usar uma função principal. Então eu vou simplesmente criar um critério de função principal. E o que vamos fazer é chamar o número de ondas com n e contas. E antes disso vamos inicializar isso aqui mesmo. Então n será igual à amostra real, que é cinco. E as contas finais serão iguais a este real, que é 12341. Bom. Agora, se quisermos imprimi-lo, deixe-me apenas desculpar-me. Sistema solar ponto para fora, ponto, impressão aqui. E vamos executá-lo. E como podemos ver aqui sobre esse problema, eu vou pegar seis, que é o último. Agora, se quisermos devolver tudo isso por enquanto, veja que é o último aqui. Então o que vamos fazer é devolver uma lista. E se rodarmos de novo, vamos conseguir, sinto muito, não podemos fazer isso. Claro, só precisamos criar um loop for aqui. Então, para eu igual a 0, eu é menor que o fim e eu passo. Então eu acho que nós temos, nós podemos imprimir o que temos. Então deixe-me criar este lugar aqui para ser igual ao número de maneiras. Então acho que estamos bem. Podemos apagar isto daqui. E é claro que podemos imprimir maneiras em cada um deles. Então, com ADD, eu simplesmente imprimi-lo. E vamos imprimi-lo. Então, em algum espaço poderia continuar. Agora, se executarmos, vamos pegar de 11 a 35. Se formos até aqui, podemos ver que temos 1, 1 a 5. Claro, esquecemos o último, esquecemos que é e mais um. Agora, se rodarmos de novo, vamos pegar um, 1, 2, 3, 5, 6. E é exatamente o mesmo menor, o array exato que nós criamos usando este exemplo aqui manualmente. Então isso é basicamente para a implementação. É assim que podemos implementá-lo. E, claro, você não precisa de tudo isso. Isso é para fins de visualização. Só precisamos do último índice ou do último elemento no número de maneiras menos. Isso é para representar a quantidade cinco usando quantas maneiras de usar este aqui mesmo. Então é isso basicamente para este exemplo, vejo você no próximo vídeo. 14. Implementação de maneiras: Tudo bem, então neste vídeo, quem pode implementar nossa função usando um JavaScript. Então, como dissemos anteriormente, vamos implementá-lo usando esse número de maneiras como um array. E podemos ter duas coisas. A quantidade real, que é de US $5, e o número de camas, ou os tipos de sinos e uma matriz ou uma lista. Então o que vamos fazer é simplesmente começar com a criação da função. Assim, a função será uma série de maneiras e o que não fazemos e qual é a quantidade. E então também temos denotado por animais de estimação bem aqui. E podemos começar com a criação do array e nomeá-lo de duas maneiras para ser igual a um novo array. E como dissemos, precisamos de n mais um como tamanho. E vamos preenchê-lo com zeros. Agora, como dissemos antes. Mas temos que fazer é sentir essa quantidade em 0 por número de maneiras, que é um. Então, para fazer isso, vamos simplesmente escrever maneiras em 0 para ser igual a um. E agora podemos começar com a criação de nossos dois aninhados para loops. Voltando a este exemplo, podemos ver que vamos começar com um loop for, que será para os sinos. E então vamos atualizar o número de maneiras cada vez que passamos por um novo projeto de lei. Então o primeiro será para o nascimento. Para nós temos uma quantidade variável ou o primeiro será menos o mesmo, na verdade, e será igual a 0 no início. E então o que vamos fazer é atualizá-lo. Claro que será até e mais um. E depois vamos construir. Então é basicamente isso. E agora o que vamos fazer, sinto muito, não até o n mais um. É culpado e a lista real. E neste caso, o que vamos escrever é o comprimento do ponto de Bills. Então é isso para o primeiro loop para. O outro seria aninhado, será quantidade variável, que será igual a 1. E neste caso vamos olhar todo o caminho para a quantidade que será igual a menos que e mais um. Agora o que vamos fazer é atualizar esse valor cada vez que passarmos por isso. Agora, podemos começar com a função real. Então o que vamos dizer é que vamos olhar, olhar para este específico aqui. Então, se a quantidade é maior ou igual à cama, e como você disse, Bill não é um índice como inicializamos anteriormente, é na verdade o melhor neste índice real. Então, por exemplo, aqui em 0 nós vamos obter um, este nós vamos obter 2 e assim por diante e assim por diante. Então para implementado, mas temos que fazer é verificar se a quantidade é que ou igual. Este sinos neste índice que será construído. Agora, para torná-lo mais fácil, o que eu vou fazer é simplesmente remover tudo isso e usar outro método para loop que será construído de contas. Então o que vou dizer é que vamos deixar o Bill, as contas. E agora podemos usar sino e em vez disso neste índice. Então esta é outra função. Então o que estamos simplesmente dizendo aqui é que o cinto de nascimento é realmente não fazer substituir contas, 0 de contas em um e assim por diante e assim por diante. Então não precisamos mais disso. Podemos usá-lo como. Agora o que vamos fazer é atualizar o número de maneiras na quantidade específica simplesmente adicionando esse número de maneiras na quantidade específica para uma coisa nova. Esse é o número de maneiras no valor menos o projeto de lei real. Então esta é a fórmula que criamos bem aqui. E já dissemos que esta lei foi construída em i. Então, estamos bem. Esta é a fórmula real que continuará. E agora nós simplesmente precisamos retornar o número de maneiras no último índice. Então este é o seis. Nós só precisamos retornar o número de maneiras no valor que é cinco. Neste caso, nós o temos tão denotado como n. Então vamos simplesmente retornar caminhos. E agora estamos bem. Acho que podemos trabalhar com isso. Esta é a nossa fórmula real. Agora, se quisermos usá-lo ou testado, podemos realmente fazê-lo aqui mesmo. Então vamos denotar, vamos n igual a cinco e levar a uma área de 12345. Agora, o que vamos fazer é imprimir o número de maneiras que podemos criar com esse valor e é preenchido. Então agora, se nós realmente testamos, tudo bem, então aqui temos consultado ramo tonsilar. E neste caso o que eu vou passar para CMD e o que eu vou usar para executar o JavaScript. Eu vou usar o servidor NodeJS. Se você ainda não o instalou. Você pode ir em frente e instalá-lo agora mesmo. Pode simplesmente passar para a nota. E como dissemos, pode baixá-lo a partir daqui. Então vá em frente e faça o download. Então o que você faz é ir para a sua dinâmica ou para o seu diretório. Neste caso, vou chamá-lo de programação dinâmica JavaScript. E nesta programação dinâmica, eu vou ter esse número de maneiras quantidade que eu criei anteriormente. E você pode simplesmente executá-lo a partir dele. Então eu vou usar esses nós e simplesmente escrever número de maneiras, quantidade ponto js. E eu vou conseguir seis como o número de maneiras. Agora, lembre-se que nós só queríamos ter este último. Agora, se quisermos visualizar esse número de maneiras, menos. Então, em outras palavras, queremos visualizar essa lista como 1, 2, 3, 1, 1, 2, 3, 5, 6. Tenha em mente que devemos devolver outra coisa. Então, aqui estamos retornando maneiras que podemos competir formas escritas. Agora, se rodarmos de novo, vamos conseguir isto menos do que, isto é 112357. Agora tenha em mente que nós só precisamos do último que é representar para representar esta quantia de US $5 com estes quatro tipos de cinto. Então, temos seis maneiras de fazer isso. Então é isso, basicamente, é isso para este problema. Vejo você no próximo vídeo. 15. Implementação de python: Tudo bem, então neste vídeo vamos continuar ou função incremental usando Python. Então, como dissemos anteriormente, temos o número de maneiras que é uma lista que vamos armazenar. O número de maneiras para cada quantidade específica até o valor final ou o valor que queremos. Então faça isso, vamos começar com a criação de uma lista em Python. Então vamos para o nosso Visual Studio. E neste caso, eu vou fazer é criar uma lista. Vou dar um nome a ele. E será simplesmente lista, como este ou eu posso apenas torná-lo colchetes. E neste caso o que vou fazer é preencher esta lista até o fim, bem aqui. Então, primeiro de tudo, vamos definir nossos dois parâmetros. Então o primeiro é e será igual a cinco. E o segundo será construído, que também é uma lista. E será igual a 1, 2, 3 e 4. E neste caso, o que eu vou fazer é criar esta lista L ou Sobrenome. Na verdade pesa, já que vamos usá-lo como lixo. E claro que vou preenchê-lo com zeros. Então, para eu na faixa de talvez n mais um, vamos fazer é anexar a este 0. Desperdício que acrescenta. E eu vou acrescentar 0 aqui mesmo. E, claro, se nós imprimi-lo, nós vamos ter a nossa lista preenchê-los com zeros. Então, se formos para aqui e para a direita, pelo número de maneiras que vamos conseguir 000, 000, 000, e isso está deixando a lista vazia. Então temos 012345 elementos ou cinco índices, que são seis desde que começamos com 0. Agora o que vamos fazer é para o terceiro, o primeiro foi um com um. Então o que eu vou fazer é simplesmente dizer que em 0, eu vou preenchê-lo com um. Vou rodar de novo. Vamos conseguir um bem aqui. Então agora podemos começar com a nossa função. Temos tudo pronto para nós. Podemos resolver os nossos loops para. Uma vez que temos essa função, o que vamos fazer é percorrer todos os elementos ou todo o fim dos números bem aqui nos sinos, e então fazer a mesma coisa para o número de maneiras e atualizado. Então eu vou excluir marca e eu vou continuar com a criação de uma compilação a partir das contas. Então, agora que podemos continuar, podemos criar a quantidade agora para essas formas específicas. Então o que vamos fazer é que vamos começar de um todo o caminho até o n mais 1. E como podemos fazer isso, podemos usar o alcance de um todo o caminho até o fim mais um. E então, claro, vamos abrir esse olhar. E vamos verificar, como dissemos antes, se o valor é maior que a conta, vamos atualizar o número de maneiras. Então, como você faz isso? Simplesmente verificamos se a quantidade é maior ou igual aos sinos ou se a tensão é criada. Se for esse o caso, precisaremos atualizar o número de maneiras. Assim, um número de maneiras em quantidade será igual, como dissemos, usando a fórmula que geramos no pseudocódigo, número de maneiras igual ao número de maneiras mais o número de maneiras em quantidade menos 1. Então, neste caso, número de maneiras em quantidade igual a duas maneiras em quantidade mais maneiras em quantidade menos o cinto. Agora tenha em mente que este projeto de lei é, na verdade, estamos usando construídos e construídos. E isso nos dará sinos em 0, sinos em I e assim por diante e assim por diante. Então esta é apenas talvez uma solução de atalho para o for-loop em vez de tê-lo no alcance de e acesso e sinos em i para índices específicos que podemos usar Bill e sinos. Então é isso. Basicamente, é assim que podemos atualizá-lo. Agora o que vamos fazer é simplesmente imprimir aqui. Então, se formos imprimir maneiras, e agora vamos voltar aqui. E como você pode ver, obtivemos o mesmo resultado exato que esperávamos um, 1, 2, 3, 5 e 6. Então aqui este, 1, 2, 3, 5 e 6. Então sabemos que o nosso programa funciona. Agora, o que pretendemos fazer ou qual era o nosso objetivo, gerar o número de maneiras que podemos especificar ou podemos criar $5 em troca $5 com a suposição de que temos apenas esses quatro tipos de contas. Então, como é que fazemos isso? Nós simplesmente retornar o último porque o último elemento na lista indica que é para a quantidade de 5. Então é isso. Basicamente, nós apenas retornamos os caminhos em. E agora, se voltarmos e executá-lo novamente, vamos obter seis indicando que temos seis maneiras de implementar ou para MD sim, para implementar esta função ou para ter US $5 desses quatro tipos de contas. Então isso é basicamente para a implementação Python. Dito isto, este é o fim deste vídeo. Vejo-te no próximo. 16. Problema com Knapsack: Tudo bem, então neste vídeo, o que vamos fazer é rever um dos problemas mais famosos na programação dinâmica. E é conhecido como o problema da mochila. E este problema tem, na verdade, duas versões dele. A primeira é a versão fracionada e a outra é a discreta. Agora o que vamos fazer é passar por um exemplo. E vamos discutir essas duas versões e vamos aprender sobre uma delas. E é realmente resolvido usando programação dinâmica. Então, para passar por cima, Vamos começar com o exemplo. A idéia deste problema é que você tem alguns itens ou produtos, e cada um desses itens tem um peso e um valor. Então vamos supor que temos quatro itens. O primeiro, então eu simplesmente escrevo aqui. Então o primeiro será um peso cinco. O segundo será de peso para o terceiro será aguardado três, e o último será de peso também. Então, aqui estamos nós. Temos quatro produtos com todas essas maneiras. Agora precisamos adicionar a quantidade ou o valor desses produtos. Então o primeiro será um valor 28. Então $28, o segundo será um valor 20. O terceiro será aos 18, e o último aos 11. Então, 18 e 11. Agora, o problema real é que você vai receber esses itens ao lado de um peso específico que você pode segurar. Então, por exemplo, vamos supor que você tenha uma bolsa. E neste saco você só pode segurar até 10 de peso. Então você precisa obter todos esses produtos e adicionar até 10. Então vamos supor que você tem aqui saco. E neste saco você só pode segurar dez. Então agora a versão fracionada deste problema pode realmente ser resolvida usando algoritmos gananciosos. E neste caso, vamos ver aqui. Então o que vamos fazer é que podemos pegar uma fração desses itens em peso. Então, em vez de pegar o item inteiro, então nós temos aqui o peso para nós podemos realmente tomar frações deste. Então, por exemplo, se quisermos ter isso daqui, então temos 10, o que vamos fazer é dividir essas quantidades sobre os valores e tomar o máximo dos quais. Por exemplo, se você tem 28 sobre cinco, vamos conseguir algo como 5,6. Deixe-me escrever aqui. O segundo será cinco. O terceiro será 18 por três, que serão seis. E o final será, na verdade, 5,5. Agora, podemos sempre resolvê-lo usando a quantidade máxima. Então, para preencher esse peso de 10, o que vamos fazer é pegar todos esses três daqui. Então nós vamos tomar este três, uma vez que eles têm o maior valor em relação à quantidade acima do peso. E neste caso, vamos levar todos estes, então somam até $18. Agora, vamos continuar pegando este que é cinco. Então, se voltarmos aqui e adicionarmos estes cinco, que serão cerca de 28 dólares. E porque tem o valor mais alto. Agora lembre-se de que o objetivo deste problema é resolvê-lo ou ter um peso de dez com uma quantidade máxima de dinheiro. Agora, neste caso, temos 18 mais 28. E finalmente, o que vamos fazer é pegar este 5.5. Então, se você se lembra aqui nós temos 532. Agora, se tomarmos 11, vamos acabar com algo como 11 ou 18 mais 28 mais 11. Então, este é, o peso é três mais cinco mais dois, e é igual a 10. Agora, vamos supor que não temos um peso de dez. Então, em vez de ter um peso de 10, vamos ter um peso de nove neste caso. E se vamos resolver este problema com um peso de nove, vamos acabar com a mesma coisa de antes. No entanto, não quero ter aqui dois faz dois mais três mais cinco é nove. Neste caso. Quando chegarmos a esta posição, o que vamos fazer é tomar uma fração destes dois. Em vez de tomar Net como um todo, podemos tomar uma fração dele. Então vamos pegar uma fração de dois. Então nós não vamos pegar toda a ferramenta vai tomar uma fração, que é você pode pegar uma. E neste caso, o valor será 5.5. Então é 11 sobre 2, que é 525. Agora, a quantidade total ou todo o peso é 3 mais 5 mais 1, que é. Na verdade, igual a nove. E neste caso, podemos usar um algoritmo ganancioso que procura algo ou o valor, o maior valor que temos. Então, por exemplo, aqui temos seis, Good Take todos esses. Então vamos verificar se ainda temos um lugar. Claro que vamos ter um lugar, já que só adicionamos o peso de três. Então nove menos três, ainda temos seis sobrando. Vamos levar tudo isso. Então só nos resta um. Vamos procurar entre 55.55,5 é maior e vamos tomá-lo como o maior. E é claro que podemos pegar uma fração dele, não a quantidade total. Então esta é a idéia de uma mochila fracionada. E isso é, na verdade, isso não funciona se tivermos um discreto. Imagine que temos uma mochila discreta. E neste caso, podemos trabalhar com ele porque uma vez que chegamos a este estágio aqui, e nós temos 35, então ainda temos um sobrando. E neste caso não podemos dividir este aqui. Então, a solução ideal na verdade neblina para usar quatro mais cinco e esperar. E é claro que vamos acabar com 48 em vez de 18 mais 28. Neste caso. Como podemos ver, a versão discreta deste problema precisará ser usada para ter programação dinâmica como solução para ele. E isso disse basicamente para a mochila fracionada, você sempre pode usar o algoritmo ganancioso com ele, mas nós não tratamos o traço agora nós realmente queremos apenas trabalhar com a versão discreta onde temos a programação dinâmica. Então deixe-me deletar tudo isso daqui. Agora, para a versão discreta, também temos duas versões aqui. Temos a quantidade ilimitada e a limitada. Então aqui quando é conhecido como sem repetição. Agora, vamos falar sobre isso por um segundo. Para a quantidade ilimitada, eles significam que temos uma quantidade ilimitada deste item, este item, este item e este item. No entanto, até quantidade limitada, que é sem repetição, temos apenas um deste item, E1, produto deste item, um destes e um destes. Então não podemos usar este mais de uma vez. Agora, o que vamos fazer é que vamos ter um exemplo e passar pela quantidade ilimitada ao lado do limitado ou sem repetição. Então vamos pensar sobre isso por um segundo. Se temos este exemplo aqui, deixa-me ensinar-te. E deixe-me pegar tudo isso e torná-los menores e vir aqui. E eu vou fazer exatamente a mesma coisa para isso também. E eu os coloquei aqui. Agora, podemos continuar o nosso trabalho. Agora vamos imaginar que temos ilimitado ou o sem a petição, um que se sentou com o, sem a repetição. Então, sem repetição, o que vamos fazer. Então aqui temos Sem, vamos tomar este três, que é o mais alto. Então, de novo, pegue este três. Agora lembre-se que precisamos de um peso de dez. Então nós temos este três mais este, mais este um de cinco. Agora, se quisermos adicionar todos estes, então aqui temos 18.11.28. Neste caso, vamos acabar com $57 como valor final. E será o mais alto para o sem a repetição LFO. E basta calcular este 13 mais dois mais cinco, que é igual a 10. Então estamos bem agora com quantidade ilimitada, mas podemos fazer é, então deixe-me mudar a cor aqui. Então aqui temos o ilimitado. Vamos dar uma olhada. Então imagine que temos mais de 13, então temos 3 mais. Também pode usar outros três, que somarão até seis. E também podemos usar dois dois neste caso. Então, agora, se calcularmos, então aqui temos três mais três, modo que três são $18. Aqui também 18, temos 11 e 11. Então, como você pode ver, isso se transformará em $58, que será melhor que o antigo se tivermos quantidade ilimitada. E assumindo que temos o mesmo número ou os mesmos pesos e as mesmas quantidades. Então, neste caso, como você pode ver, é melhor usar a quantidade ilimitada ou a repetição de largura aqui. Então estas são as duas versões que temos na versão discreta do problema da mochila. E vamos concentrar-nos neles. E também podemos resolvê-los usando programação dinâmica e os próximos vídeos. Então, vejo você então. 17. Knapsack com repetição: Tudo bem, então neste vídeo vamos nos concentrar no discreto com quantidade ilimitada de versão do problema da mochila. Então, para fazer isso, deixe-me deletar tudo isso daqui. E ele também é um indicador. E deixe-me pegar tudo isso e torná-los menores e colocá-los aqui mesmo. E eu faço exatamente a mesma coisa. Este tipo deixa-me levá-los e colocá-los aqui. Então agora podemos começar com o nosso problema de mochila com repetição com quantidade ilimitada ou itens. Então, neste caso, se quisermos olhar, olhar para ele, dessa forma, vamos acabar com algo que é igual. Então aqui temos 58 dólares no total. Portanto, tenha esse número em mente para os dados. Agora o que vamos fazer é que vamos usar um array ou uma lista para tentar resolver esse problema e chegar a uma solução adequada usando programação dinâmica. Então o que vamos fazer é pegar a quantidade ou o peso máximo que temos, que é 10, e criar uma lista, dez mais um como um tamanho. Então deixe-me criar, e esta é a nossa lista. E o que nós vamos fazer é que nós vamos atualizar todos estes, cada vez que vamos passar por eles. Agora vamos pensar nisso. O que pretendemos fazer é que possamos, precisamos ter a quantidade máxima de dinheiro usando estes, assumindo que temos 10 como peso. Então vamos usar tudo isso. Temos uma quantidade limitada e vamos usar quantidade ilimitada e precisamos encontrar a quantidade máxima de dinheiro. Vamos começar com 01. Tão alto quanto podemos ver, não temos nada e não estamos usando frações, então podemos dividir isso. Então o que vamos fazer é simplesmente escrever 00 aqui. Deixe-me mudar a cor. Agora temos dois e, como podemos ver, podemos usar, e o custo será de US $11. Agora lembre-se que precisamos maximizar discutido por enquanto, não podemos usar nada além deste 11 para os dois. Agora, se formos até às 2, 3, e vamos dar uma olhada nos três. Temos 18 dólares que é maior do que 11, então podemos trabalhar com 18 aqui. Com licença, deixe-me escrever melhor. Então temos três, que será um total de 18. Agora, se formos para a frente, como podemos ver para o, para um, temos aqui o valor de 20. Agora, neste caso, 20 anos maiores que 11 e 18. Então vamos escrever 20 aqui. Agora, se formos para os cinco, temos mais de uma opção. Neste caso, vamos dar uma olhada. Ou podemos ter dois e adicionar um três, que será 11 mais 18, que será na verdade 29. Ou, eu sinto muito, ou se nós temos três e nós adicionamos a ele, dois também vai obter o resultado de 29. Então o que vamos fazer é simplesmente escrever aqui 29. Então tenha em mente que o que fizemos é realmente usar 2 mais 3 ou 3 mais 2. E vamos conseguir 29. Agora como o sexo, o valor total ou o valor máximo que podemos chegar a 3600. Explique em um minuto. Mile, pense assim. Você também pode ter todas essas informações aqui. Então vamos pensar sobre estes cinco e estes cinco. Tenha em mente que este arquivo é a solução ideal para a quantidade máxima, que é 29. Agora pense nisso como se tivéssemos um cinco e vamos adicionar um a ele para fazer um peso de seis. E neste caso, não há nada que possamos acrescentar para fazer desta forma mais do que 29. E neste caso vamos olhar para quatro. Então vamos olhar para quatro. Se temos 20 aqui, o que podemos adicionar daqui para torná-lo maior que 29? Neste caso, se olharmos para ele, podemos adicionar dois a partir daqui, que tem o valor de 11. Então 20 mais 11, será igual a 31 nazistas. Agora vamos pensar nesta viagem. Então temos três. O que podemos adicionar a três? Fazer sexo como uma quantidade era ou como um peso. Neste caso, o que podemos adicionar mais três, que também totalizará US $18. Então 18 mais 18 para 36, que é maior que 31. Então vamos deletar isso e você vai usar 36. Agora também vamos voltar a isto. Então vamos nos fazer a mesma pergunta. O que podemos acrescentar, a , para torná-lo seis? E felizmente temos este quatro aqui, que é o valor de 20. Então, se quisermos usá-lo, podemos adicionar o valor de dois, que é 11 mais 20, para nos dar também 31, que não é o valor ideal, já temos um valor ótimo que é 36. Então é assim que podemos calcular isso. Agora, passando para o sétimo, e como podemos ver, temos 36, mas não podemos adicionar nada a ele. Então, se quisermos usá-lo aqui, podemos. Então deixe-me tentar isso por agora, 36. Agora, se voltarmos a este arquivo, se tivermos 29 e adicionarmos este dois a ele, então cinco mais dois para nos dar sete. Então 2029 mais 11, ele vai nos dar na verdade 40, que é maior do que 36. Então vamos usá-lo. E, claro, podemos voltar para o 4, 3 e 2, mas esta é a solução ideal e você pode tentar sozinho. Agora vamos passar para a ajuda. Esta ajuda, a solução ideal será 47 e será na verdade 36 mais este dos dois que é 11, então 36 mais 11 é 47. Então teremos a solução ideal para o peso de nove, que é 454. E finalmente 58 para o último, que na verdade está usando esta borda daqui, a solução ideal de oito mais adicionando a ele estes dois daqui, que tem um valor de 11, então 47 mais 11, que nos dará 58. E como podem ver, temos o mesmo resultado de antes. Então é isso. É assim que podemos obter a quantidade máxima usando o método de programação dinâmica. Eu sei que se você está indo para resolver o problema da mochila, e se ele tem um pequeno problema, pode resolvê-lo apenas pela cabeça. Você realmente não precisa dessa. Mas o que acontece se você tiver talvez 10 ou 15 produtos ou itens aqui? Você não pode realmente pensar sobre isso e chegar a uma solução adequada. Então esta é a maneira correta. É assim que podemos computá-lo usando a solução ideal que podemos obter. Então é isso basicamente para este vídeo. E no próximo vamos escrever pseudocódigo. E nós estamos realmente indo para cima com uma fórmula que nós usamos aqui. Dito isto, este é o fim deste vídeo. Vejo você na próxima. 18. Knapsack com código de repetição: Tudo bem, então agora que temos uma idéia sobre o problema da mochila com a repetição, Vamos tomar sobre ou chegar uma fórmula real ou solução para este problema em uma forma de pseudocódigo. Agora, neste caso, o que vamos fazer é primeiro definir nossos parâmetros. Então, o que vamos obter na verdade são três ou quatro parâmetros. Vou falar sobre eles. Então o primeiro será realmente o peso que vamos precisar. Então o que vamos fazer é digitar aqui w. Então este é o primeiro parâmetro. O segundo será os valores reais como 54, sinto muito, como 282809, 11. Então este será um array. Então, neste caso, eu vou apenas indicá-los por Val. Então é uma lista ou um array. Agora, este terceiro vai ser o peso real. Então eu vou apenas tentar e largura. E é claro que vai ser outro array de lista. E, claro, o final seria o tamanho do comprimento deste arquivo e pesos. Então eu só vou denotado por n. Tudo bem, então o que isso significa? Então Val e ondas devem ser iguais. Por exemplo, val em 0. Temos, neste exemplo específico, teremos o valor 28 e espera em 0. Teremos o valor de cinco. Então é assim que podemos acessá-los, já que eles têm o mesmo índice. Então 28, 524, 18, 3, 11 e 2. Então isso é um, basicamente isso é o que vamos conseguir agora, vamos pensar sobre isso de uma forma dinâmica de programação. Então a primeira coisa que vamos fazer é criar esta matriz, certo? E o semi na verdade é do tamanho w mais um, como dissemos. Então eu simplesmente denotado como um denotando que é a capacidade máxima que podemos obter. Então nossa matriz será MA, e é claro que seu tamanho deve ser. Então esta é a matriz ou a lista e de tamanho Tune ser este peso mais 1. Então w mais um. Agora lembre-se que quando tivemos o selo como peso, criamos este conjunto de comprimento dez mais um. Então este é o comprimento 11, todo o caminho desde o índice um, índice 0, sinto muito, até o final do índice 10. Agora, esta é a nossa matriz chamada MA. Agora podemos começar a formular ou passar por dois loops aninhados e atualizar esses valores aqui. Então deixe-me listar alguns desses. Apague isso. Vou pegar tudo isso e torná-los menores. Acho que não precisamos deles por enquanto. Vou simplesmente adicioná-los aqui. Agora o segundo será este. Então esta é a primeira coisa que vamos fazer e o nosso código. Agora lembre-se que o que pretendemos fazer é criar uma lista ou uma matriz que contém os valores ideais para cada peso específico. Por exemplo, o valor ideal aqui para este peso de 0 é 0. A taxa ideal de um é 0. O peso ideal de 2 é 11, e assim por diante e assim por diante. Então, é claro, quando chegarmos a este ponto, e esse é o seis. E usamos a tela daqui, usamos 18 mais 3, que é 36. Sabíamos que esta é a melhor maneira que podemos obter para este valor de três. E, claro, isso é muito importante porque os valores dependem uns dos outros. Então, por exemplo, se esta não é a maneira ideal para este valor de três, e nós o usamos em sexo então, este seis não é o caminho ideal também. Então isso diz, esta é a idéia por trás disso. Nós apenas pretendemos fazer o caminho ideal para cada peso todo o caminho até o final. E é claro que vamos acabar com uma maneira ideal também. Então o que vamos fazer agora é começar com nossos loops para. O primeiro, vamos de 0 até o fim deste peso. Então será de 0 até W. Agora, é claro que este é o W maiúsculo e então o que vamos fazer é ir e outro para loop. E esta fórmula será um valor j. Agora este j vai de 0 até o fim. Então vou falar sobre isso em um segundo. Agora, se você pensar sobre isso, o que estamos fazendo basicamente é que estamos fazendo loop através. Todos um por um. E cada vez, por exemplo, se você for um dois, o que vamos fazer é olhar através de todos esses aqui. Então vamos olhar através de 5, 4, 3 e 2. Então esses pesos devem, devemos acessá-los. E também podemos acessar esses valores usando o válido que falamos anteriormente. Então é isso. Basicamente, temos nosso Val e resíduos e podemos acessá-los dentro desses dois para loops. E o que vamos fazer é verificar se este peso em um índice específico de J, certo? Então membro, lembre-se que estamos loping, looping através deste com j. Então desta forma, em um índice específico é menor ou igual aos pesos reais que estamos passando, então podemos fazer algo. Caso contrário, nós, realmente não importa e não faz sentido mudar. Então, por exemplo, vamos passar por um dos exemplos. Vamos supor que estamos em um aqui. O que vamos fazer é percorrer tudo isto. Agora o que vamos dizer é que se este cinco é menor ou igual a um, então nós vamos fazer alguma coisa. Agora. Lembre-se que cinco não é maior do que e não menos de um. Então o que vamos fazer é simplesmente ignorá-lo, já que podemos representar o dissuade S1 usando estes cinco. Agora o que você vai fazer é passar por tudo isso até agora, 432. E nós vamos ver que eles não são menos do que um. Então, é claro que vamos ignorá-lo, então os 0 descansam como estão. Agora o que vamos fazer é passar por outro exemplo. Agora, estamos em I igual a 2 neste caso, este é i. Então vamos nos perguntar se este dois é menor que cinco, desculpe, se este dois é maior que cinco, então não vai fazer nada. Estes dois são maiores que quatro ou três. Não. Então é este dois é maior do que ou igual a 2. Sim. Então podemos usar isso aqui. Então nós adicionamos o valor que temos aqui, que foi 0 realmente adicionado a este valor a partir daqui. Então é isso. Basicamente, é assim que podemos fazê-lo. Agora, vamos tentar com o último exemplo. Então, por exemplo, vamos supor que estamos em quatro. Vamos nos perguntar para que seja 4 maior que 5? Não, não podemos usá-lo. É para maior que quatro, maior ou igual. Na verdade, sim, é. Então o que vamos fazer é pegar este 4 e acessá-lo. Claro, usando o, então, por exemplo, estamos aqui para o que vamos fazer é escrever, deixe-me escrever a fórmula. Então, o que vamos conseguir na verdade é que vamos atualizar esse valor em quatro em outra coisa. Esse é o MA, com o peso que tínhamos. Então esta é a maneira com que estamos trabalhando menos o peso que vamos tomar. E neste caso é antes. Claro, esta fórmula não é definida. Vamos precisar adicionar a ele este valor aqui a partir do padrão que obtemos. Então é mais 20, eu sou um f em 0, na verdade. Então este é 0 MA em 0. Vamos olhar para ele e é 0. Então 0 mais 20, vamos conseguir 20. Agora, vamos pensar sobre isso por um segundo. O que fizemos aqui? Bem, se você realmente fez, é que estamos no peso por agora, lembre-se que você precisa de um peso de quatro. E, claro, se você vai pegar o peso de quatro daqui, você realmente precisa ter 0 pesos e adicionar a ele este quatro para ser um 284, certo? Então, por exemplo, se você vai adicionar o peso de três, você vai precisar ter um peso de um, em seguida, adicionar a ele três, nós temos este peso de quatro, certo? Então é isso. Basicamente, é assim que você pode computá-lo. Você só pensa nisso que se você vai adicionar este peso de quatro, onde você prefere se transportar antes de chegar a esta posição bem aqui? E, na verdade, a solução real é bastante simples. Você deve estar no índice 0. Adicione a ele este quatro. Daqui, vamos chegar até ele. Então é por isso que estamos adicionando esse valor daqui para o daqui. E então nós vamos tê-lo em 20, bem aqui. Então essa é a idéia por trás disso, é como podemos nos reunir. Agora vamos pensar em outro, outro loop. Então, agora vamos supor que estamos no três. Vamos nos perguntar se quatro é maior ou igual a três. Sim, é. O que vamos fazer é tomar MA às quatro. Vamos atualizá-lo. Claro que não vamos, se for menos do que estes 20 reais daqui. Claro que sim. Então temos aqui os nossos 20. Agora, deixe-me mostrar aqui. Então aqui temos, já tivemos 0, certo? Agora, nós pensamos sobre isso como ele é 20 maior que 0. Sim, devemos atualizá-lo. Então aqui temos 20. Agora, se estamos nesta árvore, o que você vai fazer é perguntar a nós mesmos, é maior que quatro? Sinto muito, é ótimo para maior ou igual a três. Sim, é. Podemos atualizá-lo. Agora precisamos verificar o valor. Se for maior que 20, então podemos atualizar este. Se não for, então não faz sentido atualizar. Agora vamos dar uma olhada. O que vamos fazer? Então dizemos que MA em quatro deve ser igual a MA neste quatro menos três mais o valor que obtemos daqui, que é 18. Agora o valor em M, um quatro menos três, que é um 01, desculpe, também é 0. Então vamos adicionar 0 mais 8, que é igual a A1. Agora vamos verificar se 20, menos de 18. Não, não é. Então vamos manter o suor 20 e ignorar este. E é claro que vamos continuar. Então ainda temos este. E, claro, vamos dizer que MA em, para talvez igual a MA em 4 menos 2 mais o valor que tivemos um que é 11. Certo, então é esse o caso? Então eu sou um em dois, na verdade são 11. Então nós vamos obter 11 mais 11, que é na verdade 22, que também é maior do que este 20. Então podemos atualizá-lo aqui mesmo. Então é isso. Basicamente, esta é a idéia toda sobre isso. Esta é a ideia geral sobre este problema da mochila. Agora o que vamos fazer é simplesmente fazer com que pareça um código melhor e absoluto. Então nós já temos esta fórmula aqui, mas feliz, apenas deletado e escrevê-lo novamente. E uma maneira agradável. Então o que vamos dizer é que estamos percorrendo todos os pesos. Então vamos percorrer todos os resíduos daqui para cada maneira que temos em nossa matriz. E vamos verificar se o peso daqui neste índice específico. Então pesos e j que ou igual à maneira que temos aqui, que é eu na verdade. Se for esse o caso, então vamos atualizar algo. Mas nós vamos atualizar é realmente a maneira que temos MDMA para criá-lo. Então MA e este índice específico, que é eu, deve ser igual ao máximo entre duas coisas. Então ele deve ser igual ao máximo entre o primeiro que é MA em i. Então é o máximo entre si ou o MA em I menos os pesos em j. Claro, depois de terminar com isso, vamos chegar a adicionar o valor que está no array val a partir daqui. Então nós vamos adicionar um valor em j. Agora vamos pensar sobre isso por um segundo. Neste caso, o que vamos dizer é que estamos, se estamos nisto, por exemplo, e estamos aqui neste quatro. Então quatro é maior ou igual a quatro. É isso com um J, que é como acessamos a pontuação, é 4. Este é maior ou igual aos pesos em j. Sim, vamos atualizá-los a quatro. Neste caso, o MA em quatro, deve ser igual ao valor real e o MA em quatro, ou o MA em quatro menos quatro, que é 0, mais o valor neste índice específico, que é 20. Então é isso. Basicamente, esta é a fórmula. E, claro, você deve sempre começar pensando sobre o array que você projetou antes, em seguida, encontrar uma solução real. Tentei pensar sobre como usamos os valores de antes e nossos índices reais aqui. E, na verdade, você realmente precisa passar por todos os exemplos para ver o padrão real dessa fórmula. Dito isto, este é o fim deste vídeo. Vejo-te. 19. Knapsack com implementação de Repetição Java: Oh, ok, então neste vídeo nós vamos resolver o problema da mochila com repetição. Então a primeira coisa que vou fazer é criar uma função. Então será público, estático. E vou dar o nome de mochila. Então vamos obter os parâmetros para o primeiro deve ser o peso, como dissemos, o segundo deve ser o comprimento dos valores e dos itens. Então temos o valor, os valores, e depois temos o peso. Agora, vamos abrir. E agora o que vamos fazer é criar nossa lista real. Esse é o, MA. Vamos defini-la como uma matriz. Neste caso, um íntimo. E para ter sinais de W mais um, nós dissemos. E, claro, por padrão, em Java, todos esses devem ser zeros. Então nós realmente não nos importamos em definir o primeiro como 0 e assim por diante e assim por diante. Então podemos pular isso e começar diretamente com o nosso loop for. Para o primeiro será em I igual a 0 e todo o caminho até o final e incrementado. Então o segundo para loop deve ser metade j. e neste caso, vamos até o fim dos valores e pesos. Então vamos atualizá-lo. E, claro, o que vamos fazer agora é verificar se esses pesos são menores ou iguais às formas que estamos passando. Então vamos atualizar o valor dentro desta fórmula, dentro desta lista. Então é isso. Só vamos usar este que usamos antes. Então deixe-me voltar e escrever aqui. Então, se pesos em j é menor ou igual ao peso ou ao olho. Agora lembre-se que eu representa o peso, o peso real. Então, se estamos em I igual a quatro, isso significa que temos, que é, esta é a maneira que representa. Finalmente, vamos acabar com a última maneira que precisamos, que é dez. E isso é o que realmente estamos buscando. Então, se esperar, sinto muito, temos um erro de digitação. Então, se pesos em j é menor ou igual a, I, pode atualizar PMAs para prefeito empate deve ser igual ao máximo entre dois. Então o que vamos fazer é usar o Mad Max. E é claro que vamos usá-lo. Ou eu sou um em i ou outra coisa que está em i. Como dissemos, cinco, nós apenas subtraímos os pesos em j. e, claro, vamos adicionar o valor dos valores em j. Então é isso. Basicamente, é assim que podemos atualizá-lo. E aqui temos um erro de digitação. Deixa-me limpá-lo. Eles disseram que basicamente esta é a nossa fórmula, é assim que podemos atualizá-la, basta usar esta fórmula daqui. Agora o que vamos fazer é simplesmente devolver os últimos da lista. Então devolva um a no peso real que queremos. Agora vamos usá-lo aqui. Então, em simplesmente criar uma função principal, eu vou apenas definir alguns parâmetros. Então vamos supor, vamos usar o mesmo problema exato ou os mesmos parâmetros exatos daqui. Então temos o peso igual a 10, então temos os valores que são 5, 4, 3 e 2. Portanto, é um menor um array. Os valores devem ser 5, 4, 3 e 2. Então vamos subir para os pesos reais, que são também eu posso copiar isso daqui, 28201811, então 2828 e 11. Então vamos acabar com os valores desse comprimento. E claro, isso é, claro, o que vamos fazer agora é chamar a função real. Então deixe-me imprimir aqui. Então ponto do sistema, ponto de impressão para imprimir, na verdade, é a mochila. Então eu vou chamar esta função aqui com, juntamente com os seguintes parâmetros, assim w valores. E agora o que estamos dizendo, bem, nós temos um problema aqui. Deixa-me só verificar. Método. Não é um livro de jogadas. Está bem. Tudo bem. Então, esquecemos deles. Devemos adicionar este desolado Basicamente agora se formos em frente e executar este. Então nós temos 0, deixe-me verificar valores e pesos fora. Ok? Então eu, ok, então aqui temos pesos e você terá valores. É só trocar feito por engano. Agora, se rodarmos de novo, teremos 58, que é exatamente o mesmo resultado que tivemos aqui e aqui. Então vimos isso usando três maneiras. O primeiro é usar nossos pensamentos e pensar em pensar nisso. Então usamos este e temos 58. E finalmente usámo-lo em nosso código. Então, provavelmente, esta é a maneira correta. Agora, o que vamos fazer é visualizá-lo uma última vez. Vamos visualizar toda a matriz. Então, em vez de retornar, basta chamar um, eu vou retornar um array. E claro, eu vou criar um loop for, certo? - Sim. Desculpe. Então, por muito tempo para fazer é iterar através de tudo isso. Então eu vou nomeá-lo também aqui, MHC2, e eu sou uma mochila de W e valores e pesos. Agora vá todo o caminho para ser um comprimento. E é claro que vamos imprimi-los. Então eu vou simplesmente imprimir e com o subespaço de sua execução novamente, nós vamos obter exatamente a mesma coisa que nós temos a partir daqui. Então temos quarenta setecentos e cinquenta e quatro e cinquenta e oito. Então eles disseram basicamente, isso é para o problema da mochila usando Java. 20. Knapsack com implementação de Reptition JavaScript: Ok, então neste vídeo nós vamos resolver a mochila com problema de manipulação usando JavaScript. Então a primeira coisa que vou fazer é criar a nossa função. Então, a função e o nome de Knapsack. Vou pegar os parâmetros, então temos que esperar o tamanho dos itens. Você tem valores e E. Agora vamos abrir. Agora, nós vamos fazer, é realmente criar este método ou este menos elástico e a. Então deixe-me voltar e deixá-lo uma nova matriz de tamanho n. Nós dissemos que o tamanho deve ser o peso que temos mais 1. Agora o que vamos fazer é preenchê-lo com zeros. Então vamos começar com nossos dois aninhados para loops. Então deixe eu igual a 0, eu é menor ou igual ao peso. E eu mais. Então não estamos fazendo nada, mas esse B é discutido aqui, então estamos pegando esses dois para loops. O primeiro de 0 a w, o segundo é dois. E assim que N1, temos j igual a 0 todo o caminho até o final e j mais, mais. Então vamos verificar se os pesos com os quais estamos lidando são realmente menores ou iguais ao desperdício que estamos nesta lista. E este é o caso, então precisamos atualizá-lo com estão apenas vindo para fazer isso em JavaScript. Então, se o peso no específico e isso é menor ou igual ao índice, eu suavizo. Vamos atualizar o MBA em I deve ser igual ao máximo entre duas coisas. Deve ser igual ao máximo entre si. Ou estou em I menos ondas P. Como dissemos antes. E, claro, vamos adicionar o valor da lista de valores em i j também. Então, há uma, basicamente esta é a nossa função real. Agora o que você vai fazer é, depois de terminar estes dois para loops, retornar o MA na WWW. Agora, se vamos apenas experimentá-lo, vamos executá-lo. Vamos definir, na verdade. Então vamos igual a 10, vamos tomar o mesmo exemplo exato dele. Então w igual a 10, vamos ter valores que são iguais a. O valor real é 28, 2018 e 11. Então valores iguais a 2828 e 11. Então temos os pesos. Pesos iguais a ele é igual a realmente 5, 4, 3 e 2. Então nós vamos ter n, que é valores de comprimento de ponto. Então o que vamos fazer é realmente chamar a função ao lado desses parâmetros. Então W e valores e pesos. E é claro que vamos explicar. Então, o registro do console. E temos depois que vamos fazer é realmente apenas para cima e para baixo prompt de comando. E então eu vou para o meu diretório dentro desta área de trabalho tarefa, eu tenho JavaScript bem aqui. Eu estou meio que copiando isso e vou para ele. E então eu vou executar esse problema usando nó. Então nodo mochila com repetições, o ab.js e temos um a e como resultado, indicando que isso não é um número. Então deixe-me checar. Tudo parece bom para o cabelo e máximo. Então o problema é, ok, então o problema está bem aqui. Então temos, precisamos fechá-lo como um plus. Só assim esta é a fórmula real. Agora, se voltarmos e a Annette vai conseguir 58 como o número máximo que podemos obter desta fórmula. Agora o que vamos fazer é imprimir tudo isso. Então, em vez de ter apenas o último, eu vou apenas para o bem deste problema. Então, como podemos ver atenções 000 011, 1822. E se voltarmos aqui, podemos ver 000 011, 1822. E, claro, é todo o caminho até 2936404912, que é exatamente um 293640 quarenta e cinquenta e quatro cinquenta e oito. Então, com isso, podemos ter certeza de que nosso problema funciona e obtivemos o mesmo resultado que o que realizamos manualmente aqui nesta lista. Então é isso, basicamente isso é para implementar a mochila com sua petição usando script java. 21. Knapsack com implementação de repetição: Ok, então neste vídeo vamos resolver a mochila com problema de repetição usando Python. Então a primeira coisa que vou fazer é criar a definição ou a função. Vou dar o nome de mochila. E ao lado dos parâmetros que vamos usar. Então wn valores e pesos. Agora vamos abrir. A primeira coisa dentro desta função, nós vamos visualizar a matriz de lista real que tem MA, organismo ele, MA, e que não pode tê-lo no alcance de. Então será de zeros e será para eu na faixa de w mais um. Então é assim que podemos criar esta lista usando uma linha de código em Python. Então o que vamos fazer é começar com nossos dois laços aninhados. Então, para eu na faixa de W, cisne, vamos criar outro para loop, que é para j na faixa de AMP. Então vamos começar com a condição. Então, não fizemos nada por enquanto. Acabamos de criar estes dois para loops. Agora vamos verificar se os pesos em j é menor ou igual a I. Então, se os pesos em j é menor ou igual a i, nós vamos atualizar o AMA em I. Então eu posso acrescentar, eu deveria ser igual a uma de duas coisas. É o máximo entre o valor real que temos, ou o máximo ou o outro, que é MA em Pi menos pesos em j mais o valor de j. Agora vamos voltar e anotar. Então max em MA em ou no segundo, que é MA em pesos em j. Então, claro, vamos adicionar a ele os valores em j. Então é isso basicamente. Agora o que vamos fazer é simplesmente devolver o MA no último, que é no W já que vamos precisar deste aqui. Então vamos devolvê-lo como está agora para experimentá-lo, deixe-me apenas criar suas coisas. Vamos usar o mesmo exemplo que usamos aqui. Então w igual a 10, os pesos são 5432. Então peso igual a uma lista de 5432. Então temos os valores que são 28201811. Então, finalmente, temos o comprimento desses valores de peso. Agora o que vamos fazer é chamar esta função e imprimi-la. Então você pode simplesmente imprimir esta mochila ao lado desses valores e pesos W. Agora, se formos aqui e executá-lo, então eu vou digitar Python ao lado de mochila com repetições e executá-lo. E nós vamos obter 58 como o número máximo permitido para este exemplo específico. Agora, para visualizar a lista real que criamos aqui, deixe-me apenas imprimir em vez de MA e então eu retorno e um, toda a lista em vez de devolver o último item. Agora, se voltarmos e atualizarmos e rodando novamente, teremos 0011182258. E se você compará-los, eles são exatamente os mesmos que o exemplo que fizemos antes. Então 01118, vinte e dois vinte e nove trinta e seis quarenta, então quarenta e sete, cinquenta e quatro e cinquenta e oito. Então isso disse basicamente, é assim que podemos usar Python para criar esta função, a mochila sem repetição. Vejo vocês no próximo vídeo. 22. Knapsack sem repetição: Tudo bem, então neste vídeo vamos discutir a mochila sem problemas de repetição. Agora, esse problema específico não funcionará com esse método que criamos aqui para a quantidade ilimitada ou a quantidade ilimitada de itens que temos. Então vamos usar uma matriz 2D e vamos falar sobre isso em um segundo. Mas antes vamos usar exatamente o mesmo problema ou exercer este exemplo. Então lembre-se que com o, sem versão, temos 57 como a resposta final. Vamos usar exatamente o mesmo exemplo. E vamos ver se vamos conseguir isso e 57 como resultado. Então, para fazer isso, deixe-me apenas excluir todos estes e excluí-los também ao lado disso. Agora podemos começar, o que vamos fazer é criar uma matriz 2D. Então deixe-me criá-lo e vê-lo daqui a pouco. Como sabemos, esta é a lista ou o array que vamos criar e pode pensar sobre estes como o peso. Uma vez que precisamos de um peso de 10, o que vamos fazer na verdade é puxar esses lugares vazios por alguns valores. Em relação, são, considerando que temos, por exemplo, este tubo. Então há dois SD esperar, deixe-me escrevê-los aqui. Como dissemos antes. Já temos, por exemplo, estes dois. E tem o valor ou a quantidade de 11. Temos três com 18, temos quatro com 20, e cinco com 28. Então deixe-me experimentá-los aqui bem rápido. Então aqui temos a quantidade. Temos 11, 18, 20 e 28. Então, o que vamos fazer aqui, então deixe-me apenas, tudo bem. Então a primeira coisa que vamos pensar neste problema é que vamos preencher esses lugares vazios assumindo que só temos este item para preencher. Então, por exemplo aqui, se quisermos preencher o peso de 0 com este item, não podemos, então vamos deixá-lo vazio com 0. Agora, novamente, se tivermos um peso de um e só tivermos este item. Agora podemos olhar para o peso deste item que é dois, que é maior que um, então não podemos fazer com realmente. Agora perguntamos a nós mesmos, se temos um peso de dois, você tem um item que tem um peso de dois. Podemos auditar? E nós armazenamos aqui? Sim, podemos. Então, apenas indo para armazenar seu valor, que é 11. Tudo bem, então deixe-me mudar a cor para verde e deixe-me apagar tudo isso, escrevê-los novamente com o verde. Então, como dissemos, aqui temos 0, 0, e aqui podemos caber isso também. Então vamos encaixá-lo. É 11. Agora, como podem ver, vamos nos perguntar se temos um peso de três e só temos um item de largura dois, podemos armazená-lo? Sim, podemos. Então loja orgânica 11 aqui. E é o mesmo para todos esses, vamos nos fazer a mesma pergunta. Então, se você tem um peso de 10, por exemplo, e nós só temos um item que tem um peso de dois. Podemos guardá-lo? Sim, cancelamos. Vamos guardar o seu valor. Então vamos seguir em frente a isto. Agora aqui não estamos apenas procurando este peso de três, procurando os dois 32. Então o que vamos fazer é escrever mil. E aqui não vamos armazenar zeros. Porque lembre-se que vamos ter esses dois itens juntos. Então, ou podemos armazenar dois ou três ou ambos ao mesmo tempo. Agora, uma vez que só temos isso como um peso de dois, vamos armazenar este item que é 11. Então o que vamos fazer é ir para o três. Agora vamos nos perguntar, podemos guardar isso aqui? Sim, porque é igual a a. Então o que vamos fazer vai todo o caminho de volta três vezes aqui. Então nós somos o 11, nós vamos para 1, 2, e 3 vamos para este que é 0. E aqui temos 18. Então vamos verificar com 18 mais 0 é maior que este. Então vamos adicioná-lo. Neste caso, é. Então eu vou adicionar 18 ele. Então pense assim. Então você pode armazenar ou você pode armazenar três. Neste caso, se você quiser começar, você pode simplesmente armazená-lo com um valor de 11. Então vamos adicionar aqui 11. No entanto, se você não fizer isso, você precisa armazenar o valor de 18. Agora lembre-se que sempre que estamos trabalhando com esta matriz 2D, se queremos ter respostas ou se queremos ter certeza de que temos um peso de três esquerda aqui, precisamos voltar três vezes como fizemos na matriz 1D no exemplo do problema de repetição de largura. Então, neste caso, o que vamos fazer é ir até o fim e vamos verificar três vezes antes. E neste caso, se você está neste ponto aqui, podemos sempre adicionar uma largura de três e acabar com esta linha bem aqui. Então estamos bem. Estamos aqui. Vamos obter 0 mais 80 e vamos ter 18 como resposta. Agora vamos passar para isso por enquanto, vamos nos perguntar. Tudo bem, então quem tem 11 ou nós temos 18 mais este quatro menos um. Então vamos obter 4 menos 3, que é 1. Vamos chegar a este ponto que é 0. Então vamos para a loja 18. Ok? Então 0 mais 18 igual a 18 é maior que 11. Vamos guardá-lo. Então vamos passar para este arquivo. Agora, vamos nos perguntar, cinco é maior que três? Sim, é. Então podemos começar três. O que vamos fazer é ir para a esquerda, vamos pensar sobre isso no início e r hat. Então, se tivermos um peso de cinco, podemos certamente armazenar ambos os itens com os quais são 23. Tudo bem, então nós vamos adicionar isso a eles, 11 mais 18, vai ser 29. Agora vamos pensar nisso. A maneira como estamos lidando com esse problema é que se estivermos em cinco, vamos apenas subtrair três dele, então é 2. Nós vamos até dois, vamos olhar para o valor aqui, e é 11. Então nós vamos armazenar este 11, apenas vamos adicioná-lo aqui, ou vamos pegar 11 mais 80, que é 29, e 11 mais 80 metros 29, que é maior. Então vamos começar aos 29. Agora vamos fazer exatamente a mesma coisa para este. Então é 11 mais 18 ou 11, então certamente escolheria 29. Então, 29, todo o caminho até o fim. Agora vamos fazer exatamente a mesma coisa aqui. Vamos nos perguntar, aqui podemos armazenar qualquer coisa. No entanto, já que já temos 11 aqui, vamos adicioná-lo. E vamos chegar a este ponto em que temos quatro. Vamos verificar se é este 20 mais o 4 menos 4. Vamos voltar todo o caminho para 0. Então 0 mais 20 é maior que 18. Sim, é. Então nós vamos para a loja 20, então nós vamos para a 20. Nós também vamos verificar se é 20 mais 5 menos 4, que é em um. Então aqui temos este 0 é 20 mais 0. Não há. Então, eu só vou para a loja 29 em vez disso. Então o que estamos dizendo aqui é que não precisamos disso se quisermos. Se você tem apenas uma largura de cinco, podemos armazenar 32 e eles nos darão uma resposta melhor de 29 em vez de ter apenas este outono com uma resposta de 20. Agora, se pensarmos sobre este seis, podemos realmente resolver 24 com um valor de 31. Vamos pensar nisso com a fórmula. Então nós estamos aderindo em seis, indo para tomar seis menos quatro, que é dois, você vai olhar para 211 mais 20, 31 maior que 9029. Então nós vamos armazená-lo aqui todo o caminho agora, nós vamos pensar sobre isso com o sete. Então, às sete, podemos armazenar 20 mais o 7 menos 4, que é 3. Temos 18, então 20 mais 1838. Então podemos armazenar 38 ou o valor acima, que é 29, indo para escolher 38. E nós realmente usamos todos eles todo o caminho. Aqui onde temos nove. Agora vamos pensar nisso. Se tivermos 20 mais nove menos quatro, que na verdade é cinco. Então vamos pegar 29 mais 20, que é 49. Então, podemos escolher 49 ou 29 mostrará que você escolher 2049, que é picker. E finalmente, para os 10, vamos ter exatamente o mesmo 49 de antes. Agora, quanto a este, vamos ter os mesmos valores exatos até o arquivo. Agora vamos verificar se é 28 maior que 29? Não, não faz. Então vamos simplesmente armazenar 2009. Agora, quando eu disse que se é 28 é maior que 29, você pode, você precisa fazer 28 mais isso. Cinco menos cinco, vou até o 0. Vamos olhar para o acima, que está aqui 0. Então 0 mais 28 é maior que 29. Não, então vamos para a loja 29. Agora, neste caso, às seis, nós também vamos armazenar apenas 31 já que não há nada aqui também em 0. Sinto muito, aqui mesmo. Então vamos olhar para o sete. Então aqui temos 38 e o valor deste que é Check it out. Temos 28 mais sete menos cinco, que é dois. Então 28 mais 11, é na verdade 39, que é maior que 38. Então vamos com 39. Finalmente, vamos fazer, para estes últimos, estamos em 8. Vamos pegar 38 ou 28 mais 8 menos 5, que é 29. Então 28 mais 29 vai nos dar 46. Vamos escolhê-lo então 9 menos 5, que é 4. Então temos no outono 20 ou 20 mais 28 ou 49. Então temos 48 ou 49, vamos com 49, que é maior. Então, finalmente, para o último, vamos verificar se vamos tomar 49 ou vamos tomar 8 mais 10 menos 5, que é em cinco também. Então temos 29 mais 28, que na verdade é 57. E este é o maior ou o maior sensor que podemos ter. E como podemos ver, obtivemos exatamente o mesmo resultado que fizemos usando nossos 1000. E neste caso o que fizemos, na verdade, usamos cinco mais dois mais três. E se quisermos ter certeza neste exemplo, podemos sempre fazer isso simplesmente dizendo que você está aqui neste 57. Como você conseguiu isso? Você acabou de adicionar 28, que é o peso cinco no dez menos cinco, que estava aqui, Este 29. Tudo bem? E este 29 significa que você não adicionou 4, você apenas adiciona o acima que está em três, certo? Então aqui temos cinco até agora. E agora vamos verificar se 29 e 11 são iguais? Não, Isso significa que você adicionou 32 também. Então isso é basicamente para o exemplo passo a passo deste problema. O próximo vídeo vamos discutir ou trabalhar com o pseudocódigo que vamos usar e a implementação do código. Então vejo-te. 23. Knapsack sem Repetição Pseudo-código: Tudo bem, então o que vamos fazer agora é que vamos passar pelo pseudocódigo deste problema. Agora que implementamos ou trabalhamos com uma solução e trabalhamos para este problema através de um exemplo, podemos realmente chegar às fórmulas que vamos usar para escrever o pseudocódigo. Então a primeira coisa que vamos fazer é criar nossa matriz ou nossa matriz 2D. Neste caso, vamos supor que no início temos uma lista vazia. Então o que vamos dizer é que o primeiro seria esvaziado. O segundo será ter este item. O terceiro, que está aqui, terá este item ao lado deste item também, a quarta linha seria ter esses três itens e a última seria ter todos esses itens. E quando eu digo que eles estariam tendo esses itens, quero dizer que eles podem escolher onde quiserem desses itens. Então é isso. Basicamente começamos com uma matriz vazia. Claro que vamos preenchê-lo com zeros. E, claro, o primeiro aqui será todos zeros também. Então é basicamente isso. Agora o que vamos fazer é criar nossa matriz 2D real, que é uma e, em seguida, uma imagem, MA. Agora o que vamos fazer é especificar os tamanhos. Lembre-se que precisamos de um vazio aqui. Então o que vamos fazer é adicionar um a ele. Então, em vez de ter o comprimento de quatro, por exemplo, vamos supor este exemplo. Temos 2345. Então temos o comprimento de quatro que vamos fazer é criar esta matriz 2D como um comprimento ou um tamanho de cinco em vez de quatro, já que precisamos adicionar este vazio aqui. Então o que vamos fazer é dizer que os tamanhos devem ser n mais um para as linhas e W mais um para a coluna, indicando que precisamos de 11 colunas aqui, todo o caminho até a dança que precisamos extrair. Agora o que vamos fazer é começar com os nossos dois para loops. O primeiro será a partir de, então eu vou ser de 0 todo o caminho até o fim. E isso é inclusivo. Então vamos criar outro loop para. Vou dar um nome a ele. W vai ser de 0 todo o caminho até o grande W. E também este é inclusivo. Agora o que vamos fazer é verificar se estamos em uma posição específica onde temos I igual a 0. Então, se o rho I é igual a 0 ou a coluna é igual a 0. Então eu poderia ser 0 ou w igual a 0. O que vamos fazer é definir isto como 0. Como dissemos, temos esses valores, zeros bem aqui, e estes serão usados mais tarde. Então, sempre que quisermos voltar para a posição anterior. Então imagine que estamos neste 1112 e estamos pedindo a posição anterior disso e ela não existe. Assim, precisamos ter algo antes de um pedido para que não tenhamos um erro enquanto estou escrevendo nosso código. Então é por isso que assumimos este vazio no início, que será apenas zeros. Então, se eu for para 0 ou w igual a 0, o que vamos fazer é dizer que eu estou em I e w deve ser igual a 0. Então esta é a primeira condição. Agora, a segunda condição, se os pesos que temos ao passar por esses pesos são menores ou iguais à maneira real que poderia passar por ele. Agora, neste caso, o que vamos fazer é atualizar o MA ou esta matriz 2D. Então vamos pensar sobre isso por um segundo. Vamos supor que estamos nesta posição quatro, e estamos aqui. Temos três temporários. Então ainda não sabemos esse valor. Então, vamos verificar. A primeira coisa que vamos verificar é que ao passar por isso, então se este três é menor ou igual a quatro, agora este é o caso, é verdade, então podemos atualizá-lo. Como podemos atualizá-lo? Podemos ir por 4 menos 3, que será um, e adicionar a ele esse valor de três, que será 18 mais 0. Ou vamos levar o valor acima dele, que é 11. Portanto, é por isso que precisamos verificar se os pesos são realmente menores ou iguais a esta forma. E, claro, se esse não for o caso, o que vamos fazer é pegar o valor de cima. E, claro, um dos exemplos disso pode ser que estamos neste peso três. Vou verificar se este peso é menor ou igual a dois e não é menor ou igual a dois. O que vamos fazer é simplesmente pegar o valor de cima. Então vamos acessar o mesmo “A” com o mesmo peso. No entanto, vamos acessá-lo com um índice menos1 para ter o valor do acima. Então é isso, basicamente, deixe-me pegar tudo isso e torná-los um pouco menores. E vou escrevê-las aqui. Então vamos continuar com o nosso código. Então nós dissemos que se f igual a 0 ou w igual a 0, nós vamos fazer isso. Agora. A segunda condição é verificar se os pesos no peso específico é menor ou igual ao peso que temos aqui. E se for esse o caso, precisamos atualizar a matriz 2D real. Então o que vamos fazer é verificar se este peso, então peso em um índice específico, eu vou deixá-lo vazio por enquanto, é menor ou igual a w se esta condição for satisfeita. Mas nós vamos fazer é atualizar este eu específico para ser igual a qualquer um, então o máximo entre duas coisas. Então, ou é o K i, então vou escrevê-lo aqui. Então é em I menos 1 w. Então, ou é o valor acima ou o valor da lista. Então estamos nesta matriz 2D, vamos, como dissemos, vamos reverter por um. E quanto às colunas, vamos a partir de w. Então, vamos supor que estamos neste valor quatro e estamos neste peso três. E eu faço quatro menos três, que é igual a um. Então vamos fazer w, que é quatro menos os pesos em um índice específico com que estamos lidando. E então o que vamos fazer é adicionar esse valor a partir de valores. Então vamos adicionar o valor do nosso novo peso. Isto é, por exemplo, este, 18 ou 20, ou 28 ou assim por diante. Então é o máximo entre o acima ou o daqui. Então isso é basicamente esta é a fórmula que vamos usar. Agora temos, ainda temos a última condição. Então, se essas duas condições forem satisfeitas, a última é apenas pegar o valor de cima. E como dissemos, isso não é maior. Desculpe, não é menor ou igual ao nosso peso. Vamos apenas copiar o valor de cima. Então, o que vamos fazer é especificar que o índice em i, w, desculpe, o valor de a deve ser igual ao valor em I menos 1 w. Então é isso basicamente para o nosso pseudocódigo para este problema. Nos próximos vídeos, vamos implementá-los em nosso código ou em nossos idiomas. Então vejo-te. 24. Knapsack sem a implementação de Repetição Java: Tudo bem, então neste vídeo vamos implementar nossa função usando Java. Então a primeira coisa que vou fazer é inicializar nossa função que é uma estática pública. E assim posso retornar o número inteiro? Vou mochila de capacitação. E vai levar alguns parâmetros, como a espera. E eu pego uma matriz de peso, então nós vamos tomar valores profundos como uma matriz também. E finalmente, você, eu vou pegar a capacidade ou o comprimento desses valores e pesos. Agora o que nós vamos fazer é, no início e ela mente e w. Então nós vamos construir nossa matriz 2D, que vai ser chamada de um a. E ele vai ter n mais um e W mais um como o tamanho do comprimento n. Então lembre-se que dissemos que precisamos n mais um porque criamos uma matriz vazia ou lista vazia aqui. E cada vez que vamos passar por, por exemplo, se você está neste e em seguida, ele vai ter uma lista vazia mais esta. Ou se você está no, hey, nós vamos ter este mais este, e assim por diante e assim por diante. Então é por isso que adicionamos n mais 1 aqui indicando que temos e mais um cresce. Ok, então agora o que vamos fazer é começar com o nosso loop for. Então, o primeiro que dissemos que vai ser chamado de “I” todo o caminho. E o segundo será J, assim por diante. Desculpe, W. Então w é igual a 0, então w menor ou igual a, criar um w. Então w é menor ou igual a W maiúsculo e W mais botão. Então podemos verificar se i o w é igual a 0. Vamos simplesmente ignorar, mas armazenando em I e w o valor de 0. Agora o segundo caso é que se o peso em i menos1, e vamos ver por que é I menos 1 é menor ou igual a w. Se este for o caso, então vamos atualizar este e fazer o máximo entre duas coisas. Ou seja, o primeiro deve ser o valor real que temos. Então eu sou um em w e este valor p acima dele. Ou o que vamos fazer é ir para cima. E quanto ao W, vamos adicionar w menos os pesos em I menos 1. Então é isso. Basicamente, é assim que podemos fazê-lo. Claro, precisamos adicionar um, algo que é o valor ou o valor dos itens que temos. E vamos vê-lo daqui a pouco. Mas, por enquanto, eu simplesmente adicionarei valores em I menos 1. Então vamos pensar sobre isso por um minuto. O que estamos dizendo aqui? Então estamos dizendo que se os pesos em I menos 1 é menor ou igual a w. Agora, vamos nos referir a isso por menos um. Por que estamos usando I minus1 conjunto de AI? Agora, lembre-se que nós adicionamos aqui uma lista vazia. Então, se um valor, por exemplo, se estamos lidando com este, ele terá um índice de um. No entanto, na lista que vamos conseguir, vamos tê-los como 2345. Então vamos supor que eles são assim. Então 2345 e seus valores ou quantidades são os seguintes. Um 11182028. Então estes são os índices. Então temos o índice 0, 1, 2 e 3. Então, se você quiser acessá-los daqui, aqui temos os pesos e aqui temos os valores. E, claro, se quisermos armazená-los na lista, vamos precisar classificar. Por exemplo, vamos supor que estamos aqui em I. Se quisermos acessar este, estamos agora no índice um. No entanto, esse índice está em 0 e essa lista de pesos, porque adicionamos essa lista vazia, que ocupou um lugar. Então, se quisermos acessar esses pesos e valores usando I e w, precisamos lembrar ou lembrar esta lista vazia. Então é por isso que vamos acessá-los usando o por menos um. Então é isso. Basicamente é por isso que usamos I menos1 aqui, aqui, e também aqui quando acessamos os valores em I menos 1. Então é assim que podemos mudá-lo. E ainda temos a última condição, que é se estas duas condições não estão satisfeitos com apenas feito um retorno são. Coloque o mesmo valor acima nele. E é isso basicamente. Agora, sempre que terminarmos este loop while, vamos apenas retornar o valor em e, e W. maiúsculo Então é isso basicamente para este problema. Agora vamos em frente e experimentá-lo aqui mesmo. Então o que eu vou fazer é criar uma função principal onde eu vou ter um valor. Então vamos supor que alocamos valores como uma lista. Vou ter um 2345 dividido. Então eu vou ter pesos. Desculpe, eu só subi. Então aqui temos os pesos. E os valores devem ser os seguintes, 11182028. E, claro, vamos precisar do W, que é dez. E então nós vamos ter n, que é valores de comprimento de ponto. Então é isso, basicamente, agora ainda temos que chamar a mochila. Então eu vou retorná-lo em resultados de problemas de mochila com, juntamente com estes, todos estes. Agora o que eu vou fazer é simplesmente imprimi-lo aqui mesmo. Então eu vou imprimir o resultado. Agora, se eu ir em frente e executá-lo aqui, e eu vou obter como o valor 57, que é na verdade o mesmo valor que nós obtivemos deste aqui. É aqui mesmo, 57 usando este exemplo e usando nossa educação com onde temos 57 também usando três mais dois mais cinco. Então é isso basicamente para este problema. Se você quiser ver esses dois, o array, você pode simplesmente criá-lo ou devolvê-lo ali mesmo, eu sinto muito. Então, podemos simplesmente devolvê-lo aqui em uma matriz 2D. E em vez de retornar este específico, um, pode apenas remover este e retornar aqui este array 2D como seguido. E, claro, na verdade, o que vamos fazer é armazená-los em um resultado. Então podemos entrar em um loop for começando com o resultado, esse comprimento. E nós vamos adicionar resultado em pelo comprimento. Então vamos simplesmente imprimi-los. Então resultado. E, em seguida, adicione j mais algum espaço e, em seguida, imprima alguma linha r1. E nós vamos obter esta matriz 2D. E, claro, se verificarmos este que construímos aqui, parece exatamente o mesmo. Então temos 000 até 11, então temos 001111, e então 929, 000, 011, 820, 29, 31, e então trinta e oito, trinta e oito, quarenta e nove. Quarenta e nove. Então, está correto. E o final com 46, 4957, e nós os temos aqui. Então esta é a matriz 2D exata que temos manualmente. Portanto, nossa solução está correta, e esta é a maneira correta de implementar esse problema usando Java. Venda a mochila problemática sem repetição. Então é isso basicamente para este vídeo. Vejo-te no próximo. 25. Knapsack sem a implementação de repetição JavaScript: Ok, Então neste vídeo vamos implementar nossa função para o problema da mochila sem repetição usando JavaScript. Então a primeira coisa que vou fazer é criar nossa função, que é mochila. E vai tomar os seguintes parâmetros. Então o W, o peso, os valores reais de peso. E depois podemos abri-la. Agora o que vamos fazer é definir os dois índices que vamos usar. Então vamos criar nossa matriz funcional ou 2D. E neste caso, será um array e mais um, como dissemos. Então podemos começar com o nosso loop for. Então eu vou ser igual a 0, como dissemos, ele vai até o fim. E então eu vou namorar, então nós vamos ter p w. Neste caso, w é igual a 0, então todo o caminho até o W maiúsculo e atualizado. Agora cada vez que entramos neste loop, mas vamos fazer é criar uma nova matriz em um índice específico de I. Então, será uma nova matriz de comprimento w mais um para preenchê-lo. E agora neste caso, vamos verificar se eu é igual a 0 ou w é igual a 0. O que você vai fazer é simplesmente adicionar a isso e eu W um valor de 0. Agora, a segunda condição é se os pesos em um índice específico e eu vou denotado por I menos 1. Vamos falar sobre isso na cama, é menor ou igual a w. Este é o caso. Então precisamos atualizar este W em uma de duas coisas. Então, o máximo entre o valor acima dele. Então é, estou menos 1 w? Ou a segunda coisa que é, como dissemos, vamos para cima e, em seguida, ir para a esquerda usando w menos os pesos no índice específico, por isso é em I menos 1. E, claro, o que vamos fazer é adicionar valor a ele. Então os valores em I menos um. E então é com isso que vamos acabar. A última condição é que essas duas condições não estão satisfeitas, mas vamos fazer é simplesmente dar esta posição específica, o valor acima dela. Então eu menos 1 w. Então é isso basicamente. Agora vamos falar sobre por que usamos o I menos 1 em vez de I neste caso. E a resposta é que, lembre-se que usamos uma matriz vazia aqui. Então, um critério de lista vazia. E o que nós realmente fizemos é que nós temos o índice de 0 para isso, então nós temos o índice de um para isso, um, índice de dois para isso, e assim por diante e assim por diante. No entanto, quando obtivermos as entradas, vamos obtê-las da seguinte forma. Então para 11 tem o valor do índice de 0. E se você olhar para este caso, nós o temos como um índice de um e a matriz 2D. Então o que vamos fazer se quisermos acessá-lo, vamos usar I menos 1, que é 1 menos 1. Vamos ter 0 e podemos adicionar definido corretamente. A mesma coisa se aplica a todos eles. Então, se estamos no índice 2 aqui, como podemos acessá-lo usando dois menos um, que é índice um. Então é isso Basicamente é por isso que usamos por menos 1 aqui, aqui e ali. Então é isso basicamente para este problema, a última coisa que vamos fazer é simplesmente retornar o último aqui, que é em e, e o w. grande agora vamos experimentá-lo. Então vou criar valores de 2345, sinto muito. Os pesos. Então eu vou ter os valores de 11182028. Então eu vou ter o peso de dez. E finalmente, no final desse comprimento, então valoriza esse comprimento. E agora vamos chamar a mochila. Então vou fazer login na mochila. E ao lado destes, então w pesos, em seguida, valores, e, em seguida , ok, então agora vamos gastar este problema ou programa. Então o que nós vamos fazer é navegar para este diretório e nós vamos chamar, deixe-me apenas chamá-lo aqui. Então nó mochila sem repetição, ab.js vai executá-lo e eu vou obter 57 como valor de definição, que é o mesmo que temos aqui. E, claro, aqui. Então é isso, é assim que podemos resolvê-lo. Agora, a última coisa que vou fazer é visualizar toda a matriz 2D. Então, em vez de retornar um inteiro específico, eu vou retornar a matriz inteira. Agora, se eu rodar novamente e eu vou obter é um array e nós temos o primeiro golpe, segundo, terceiro, quarto, e 550. Agora o que vamos fazer é apenas compará-los. Então, para AVC, na verdade todos os zeros, que é basicamente o que esperávamos aqui. Então temos 000 e, em seguida, todos eles são 11. Ei, nós temos o resto são 29, então vamos corrigir. Então temos 3849 gráfico aqui. E finalmente temos 46, 4957. E aqui estão eles. Então isso é basicamente para este problema. É assim que podemos ter certeza de que ele está correto e nossa implementação do nosso código está realmente correta. Então é isso para a Knapsack sem repetição usando JavaScript. Dito isto, este é o fim deste vídeo. Vejo você na próxima. 26. Knapsack sem Repetição Python: Ok, então neste vídeo, vamos resolver a mochila sem problema de permutação usando Python. Então o primeiro passo que eu vou dar é criar uma função e simplesmente pode nomeá-la mochila. E era grande gongo pegar alguns parâmetros como o peso, os valores de peso e n. Então vamos abri-lo. E a primeira coisa que vamos fazer é criar nossa matriz 2D. E esta matriz deve ter dois parâmetros. Agora, como podemos construí-lo usando uma linha de código? Nós simplesmente queremos especificar isso para a linha. Então, para x na faixa de W mais um. E então, quanto às colunas, eu sinto muito, isso é para as colunas e quanto para a linha, eu vou fazer isso para intervalo e plus1, como dissemos. Agora, podemos começar com o nosso loop for. Assim, o primeiro para loop deve começar em 0 e terminar com n mais 1. Então, para I no intervalo e mais um, então o segundo para loop deve começar um intervalo de 0 a W mais um. Desculpe, temos W. maiúsculo e vamos começar com o nosso código. Então a primeira coisa que vamos fazer é verificar se eu é igual a 0 ou w é igual a 0. Este é o caso. Então vamos simplesmente querer atualização ou vai simplesmente adicionar 0 a este valor. Então é isso basicamente agora. Então o que vamos fazer é verificar se os pesos em I menos 1. Vamos falar sobre eu menos 1 pedaço do Líbano. Mas, por enquanto, vamos pensar nisso assim. Então, se for menor ou igual a w, o que vamos fazer é atualizar o olho, a matriz 2D nos índices específicos para o máximo entre duas coisas. O primeiro é o valor real que temos acima dele. Então eu menos 1 como é, I indicando a estrada e w ou outra coisa, que é o MA em I menos um. E quanto à coluna, dissemos que precisamos subtrair de W, o desperdício que vamos obter. Então este Pi menos um neste caso. E é claro que vamos adicionar o valor disso, que é em I menos um também. E, finalmente, este não é o caso. Além disso, vamos fazer outra coisa. Isso é apenas pegar o valor acima dele e adicioná-lo a este aqui mesmo. Então eu estou em I menos um que está acima dele. Então isso é basicamente agora adicionar pontuação este I menos1 no, espere. Por que a usamos? Porque se voltarmos ao nosso pseudocódigo, como podemos ver, dissemos que temos uma matriz vazia aqui. E se pensarmos sobre nossos pesos e valores, temos pesos, valores e seus índices são os seguintes, 0123. No entanto, em nossa matriz 2D, se você quiser acessar este, ele não está no índice 0, index1. Aqui temos o índice 0, 1, 2, 3, 4 e 5. Então, se você quiser acessar isso, ele está no índice 2 aqui. No entanto, está no índice um e nossa entrada. Então é por isso que se quisermos acessar este, simplesmente subtraímos de um. Então, se estamos no índice 3, que supostamente temos 0, 1 , 2 e 3, estamos aqui. Então, no índice 3, como acessar isso por usar nossa empatia. Então nós fazemos índice 3 menos 1, que é 2. Agora podemos acessá-lo usando pesos e valores no índice dois. Então esta é toda a idéia sobre o i1 x1 e como usá-los. E, claro, se você estiver confuso com isso, podemos simplesmente adicionar 0 aqui e aqui. Então isso começará em 0, e isso começará em 1, 2, 3. Mas por não ser complexo ou não, torná-lo complicado, eu simplesmente adicionei i menos um em vez de I. Então isso é agora o que vamos fazer é simplesmente retornar o MA no E real, e w. Então esta é a última entrada. Agora vamos experimentá-lo. Então os valores aqui são, na verdade, como dissemos, temos 11182028. Então temos os pesos que são 2, 3, e 4, e 5. Então temos o W, o peso que vamos precisar para igual a 10, e apenas o comprimento dos valores. Agora, vamos tentar. Então vou imprimir a mochila. Neste caso, eu vou ter w pesos, em seguida, valores, então. E agora, se formos em frente para o nosso CMD, o que vamos fazer é executar mochila Python sem repetição. Eu dirijo. E aqui temos, então, índice válido. Você tem um estreito dizendo que 0 para x e ganhos de 0. Ok, então aqui temos, nós não temos noivos, é só ter noivos. Agora vamos tentar de novo. Isto é um erro de digitação. Temos um comprimento, esquecemos de adicionar o n aqui igual a agora eu acho que estamos bem. Agora magnético novamente, vamos obter este resultado de 57, como você pode ver aqui. Então isso indica que atingimos nosso objetivo. Agora o que vamos fazer é visualizar toda a matriz 2D. Então, em vez de retornar este último valor, eu só vou retornar todo o array. Agora, se eu tentar de novo, vou conseguir isso como dissemos. Então teremos a primeira linha, segunda coluna. E, claro, se você quiser ter certeza de que isso está correto, o que nós não fazemos é simplesmente compará-los com eles. Então, a primeira linha, como dissemos, deve ser todos zeros. A segunda linha é 0, 0, todo o caminho até 11. E o terceiro seria 000 011, 1818, e então todos eles, 29, então nós temos 000 011, 1820, 29. Então vamos acabar com 49 e 49. E a última fila acabará com quarenta e seis, quarenta e nove e cinquenta e sete. Se olharmos para ele, temos 46 4957. Então isso indica que nossa solução está correta. Então é isso basicamente para este vídeo. Vejo-te no próximo. 27. Número de subconjuntos que compõem um número específico: Olá e bem-vindo de volta. Neste vídeo, vamos discutir o problema de encontrar o número de subconjuntos que podem somar um número específico. Agora, neste exemplo, temos um conjunto de quatro números, 1345, e temos o número nove, que vamos usar agora. Então o que vamos fazer é verificar se temos um subconjunto ou mais de um subconjunto que pode somar até nove. E neste exemplo, temos dois subconjuntos. O primeiro é 135, e o segundo é para N5. E ambos somam 90. Se você somar todos os índices de elementos dentro do subconjunto, e você obterá nove como um valor finito. Agora, vamos pensar sobre isso por um segundo. A primeira abordagem que podemos fazer é ter tudo resolvido usando recursão. E a razão pela qual estou dizendo isso é porque se você quiser pensar sobre isso ou nós resolvemos usando um pedaço de papel. Então, por exemplo, vamos pensar sobre isso. Se tivermos um conjunto vazio aqui. Então deixe-me desenhá-lo aqui. O que vamos fazer é passar por cada elemento e incluí-lo uma vez e nos livrar dele o outro. Então, por exemplo, No início temos um conjunto vazio. Vamos verificar se isto é igual a 9. Não é. O que você vai fazer é adicionar este aqui. Então deixe-me mudar a cor. Vamos adicionar este número 5200 de uma só vez. E nós vamos apenas mantê-lo como está pela segunda vez. Agora o que vamos fazer é verificar também ter isso é igual a 9. Não é. O que vamos fazer é ir para o outro número, que é quatro. Vamos adicioná-lo uma vez. E fique com cinco, no outro termo. E aqui vamos adicioná-lo e mantê-lo vazio. Agora, podemos passar para o terceiro número, que é o 3. E o trabalho que vamos fazer é exatamente a mesma coisa. Então aqui temos 5, 4, 3, e aqui temos eu sinto muito. - Sim. Tudo bem. Então 54. E é claro que vamos ter aqui 53 e vamos mantê-lo cinco, bem aqui, e assim por diante e assim por diante até obter todas as combinações possíveis que podemos obter. E, claro, vamos verificar a cada vez que construímos uma tela, vamos verificar se isso é igual a quatro. 29 por exemplo, ou isso é igual a nove. Então temos 54 é igual a nove. Então eu incremento o contador. Então talvez você tenha um contador variável ou algo assim, e isso será incrementado. Então, temos nove por enquanto. Então vamos verificar, por exemplo, a outra solução que é 1, 3 e 5, que inclui cinco, está aqui, cinco, 53. E nós vamos ter um 531, o que também vai ser verdade. E vamos incluir ou incrementar o contador. E como podemos ver para construir este q, precisamos usar recursão ou é a maneira mais lógica de fazê-lo. Agora o que vamos fazer é escrever o pseudocódigo para este método recursivo. Então vamos tentar otimizá-lo usando programação dinâmica ou memorização. Então vamos em frente e fazê-lo aqui mesmo. Tudo bem, então uma função terá três parâmetros. A primeira é a lista que vamos ter. Então eu só o nome da lista. Então vamos tirar um total. Vou explicar em um segundo. E então, finalmente, um índice I. Então vamos pensar sobre isso por um segundo. O que vamos fazer? No início, vamos construir esta matriz que está vazia ou menos, que está vazia. E então vamos adicionar 52 ao mesmo tempo e vamos mantê-lo como é para isso. E como vamos fazer isso? Deixe-me colocar aqui. Então deixe-me apagar isso e vamos continuar. Então o que vamos ter é um índice que está apontando para este número cinco. A primeira vez que começamos, então o que vamos fazer é adicionar este arquivo, por exemplo, à lista. Depois disso, o que vamos fazer, vamos recuar um por um até percorrer todos os elementos. E vamos supor que adicionamos este elemento, que é quatro. Então deixe-me apenas denotado em vermelho. Então vamos supor que aqui o que vamos fazer é verificar se podemos construir uma lista ou construir este número nove usando esta lista, apenas os elementos que incluem quatro e antes. Então o que vamos fazer é verificar ou criar uma função que nos dê esse número exato, quantos conjuntos podemos fazer e que você pode ter dois para que possamos obter esse número nove usando apenas esses elementos. Então, se o índice é adicionar estes três aqui, nós temos a lista de 13 apenas. Então queremos incluir 45. Então é isso que queremos dizer por eu ir decrementá-lo. E... Verifique quantas listas podemos ter um pedido para ter este número nove. Agora, em relação ao total, mas não queremos fazer é decrementado cada vez pelo número no índice específico. E você pode entender em um segundo uma vez que nos sentamos com a escrita do código. E o que pretendemos fazer é finalmente obter o número do possível de tal forma que possamos ter uma ordem para obter este número nove. Então deixe-me deletar isso. E vamos começar com o nosso código passo a passo. E nós vamos conversar e explicar isso enquanto passamos por isso. Então a primeira coisa que vou fazer é, então esta é a nossa função. Então deixe-me apenas denotar esses parâmetros como este. E o que vamos fazer é verificar uma vez que alcançamos um total de 0, isso significa que consumimos todo esse número. Temos um total de 0, então está tudo bem. Podemos devolver um. Já que isto é como um caso básico. Por exemplo, aqui, se chegarmos ao total de 0, que é cinco mais quatro, é igual a nove, então o total deste permanecerá ou será 0 neste caso, já que vamos diminuir nove por cinco, então decrementado por quatro, vamos obter um total aqui, que é igual a 0. O que vamos fazer é parar aqui e incrementar nossa função. Então deixe-me chamá-lo de recursão. Então, o nome repete. E neste caso, se o total for igual a 0, isso significa que fomos capazes de chegar a um subconjunto que somam nove. E neste caso, o que vamos fazer para simplesmente devolver um. Agora, vamos pensar se o total é menor que 0 neste caso, como este exemplo, ou talvez este aqui. Certo, então não tratamos nenhum ponto onde o total é menor que 0 além deste. Então talvez nós vamos apenas pegar este 5 mais 4, que é igual a nove mais três, que é igual a 12. E neste caso, se o total for menor que 0, então o que vamos fazer é simplesmente retornar 0. Então, se o total for menor que 0, não podemos retornar 0. Agora tenha em mente, nós queremos, realmente chegar a este ponto. Podemos chegar a um ponto em que o total é menor que 0 e outros casos 54 não são subconjuntos de um possível subconjunto. Então, por exemplo, talvez tenhamos outro, talvez sexo aqui e temos 6 mais 5. Mais 6 mais 5 é na verdade 11 e isso é maior que quatro, maior que nove, sinto muito. Então, neste caso, vamos retornar 0. Então é isso. Isto é para o segundo caso base. Agora vamos passar para o terceiro caso base, que é se chegamos a um ponto onde chegamos ao índice mínimo em ter o índice é menor que 0, I menor que 0. O que vamos fazer é simplesmente também retorna 0, indicando que chegamos ao mais à esquerda da nossa matriz. E, neste caso, não encontramos nenhum subconjunto que possa somar até nove. Então, se eu for menor que 0, basta retornar 0. Então é isso para os casos básicos. Agora podemos começar com a nossa função de recursão. Então o que eu vou fazer é colocá-los aqui. E este também, eu vou colocá-los como seu herdeiro. E agora vamos para a segunda ou a parte divertida aqui. Essa é a recursão, na verdade. Então agora o que vamos fazer é verificar como eu vou, total é menor que um número específico. Então, por exemplo, se estamos neste número quatro, tudo bem, então o que vamos fazer é verificar se o total que nos resta, que é nove menos cinco, que é quatro, é menor que este número. Agora, se este é o caso, então não podemos adicionar quatro. No entanto, quatro não é inferior a quatro, é realmente igual. Assim, podemos incluir uma tendência aqui. Então, temos dois casos. O primeiro é se esse número for menor que quatro, então n é menor que o número que temos no total. Então deixe-me escrever e explicar mais. Então, se o número total que nos resta é menor que o número real dentro desta lista, então é menor que a lista em um índice específico I. E este é o caso. Isto significa que podemos somar o nosso, podemos adicionar este número 4 à nossa lista ou ao nosso subconjunto. Então o que vamos fazer é simplesmente mover a seta para os outros elementos. Como é que se faz isso? Nós simplesmente retornamos a mesma função. Então. Recursão na lista. O mesmo total desde que não usamos esse total e eu menos1 indicando que não precisamos disso para mais. Agora, se este não for o caso, o que vamos fazer é devolver duas coisas. A primeira coisa é que nós adicionamos isso para o segundo é que nós não adicionamos como nós dissemos aqui. Então, por exemplo, se você está neste momento específico onde temos cinco e, em seguida, chegamos ao índice que está neste elemento para o que vamos fazer é no primeiro adicionado e, em seguida, apenas manter a lista como ela é. E o que vamos fazer é obter os subconjuntos possíveis desta parte da árvore e todos os subconjuntos possíveis deste k positivo. E, em seguida, adicioná-los, adicioná-los e obter todos os subconjuntos possíveis. Neste caso, temos aqui um. Então temos um aqui e um aqui. O que vamos fazer é adicionar um mais um e isso vai levar dois. E então nós vamos voltar para como o possível valor final de qualidade que temos. Então, como é que fazemos isso? Vamos levar para funções de recursão e adicioná-las juntas. A primeira é que incluímos estes quatro e a segunda é apenas darmos a lista como ela é. Então o que vamos fazer é eu sinto muito, podemos apenas dizer outra coisa. Mas vamos fazer é devolver duas coisas. Essa é a recursão nesta lista. A primeira vez que vamos incluí-lo, vamos apenas decrementado do total. Então vamos decrementar a lista em i e também diminuir o nosso contador. Então o que você vai fazer é incluí-lo e, em seguida, ir para este três aqui mesmo. E nós vamos fazer exatamente a mesma coisa para todos os elementos aqui. Então este é o primeiro e vamos adicioná-lo à mesma recursão. No entanto, desta vez vamos manter a lista adicionar é, como faríamos isso? Nós simplesmente retornar total em vez de decrementado por este elemento. Então nós vamos dar cinco, que é nove menos um, total vai ficar para, e neste caso, nós também vamos decrementado. Então isso é basicamente esta é a nossa fórmula. Agora, se pensarem bem, o que estamos a dizer é que vamos passar por toda esta lista da direita para a esquerda. E então vamos verificar se algum dos casos base se aplica. Se for esse o caso, vamos retornar apropriado de acordo com o número. Então, se o total for igual a 0, como este caso, o que vamos retornar é um. Caso contrário, você não pode retornar 0. Agora para a recursão, recursão parte, mas nós vamos fazer é verificar se o nosso total é menor que o total aqui, o elemento bem aqui. Então suponha que temos um total de três e temos o número quatro. Então não há nenhuma maneira que possamos adicionar qualquer coisa a formar que possa fazer até este total de três porque três é menor que quatro. Então o que vamos fazer é simplesmente mover este índice ou esta seta para o anterior. Então foi isso que fizemos aqui. E se este não for o caso, se pudermos colocar isto para o nosso set. Mas vamos fazer é adicionar duas coisas e um ao outro. O primeiro que está fazendo realmente incluído em nosso conjunto, e o segundo é realmente apenas manter o conjunto como ele é. E então vamos ver os números reais daqui e aqui e adicioná-los. Nós vamos obter o número final usando este método recursão. Então é isso basicamente para este problema. Agora o que vamos fazer no próximo vídeo é tentar otimizá-lo usando programação dinâmica e memorização. Então, vejo você então. 28. Número melhorado de solução de subconjuntos: Tudo bem, então neste vídeo vamos tentar otimizar nossa solução para isso. Encontrar o número de subconjuntos que podem se adaptar a um problema de número específico. Então a principal desvantagem da nossa solução recursiva é que vamos chamar a mesma função recursiva e recursiva repetidamente. E por que isso? Porque pense nisso. Se estamos no número específico, por exemplo, aqui em apenas cinco, o que vamos fazer é chamá-lo mais uma vez para 54, então chamá-lo mais uma vez, 45403. Então o que estamos basicamente fazendo é que vamos adicionar este quatro aqui. Então vamos adicioná-lo aqui. E então, claro, vamos adicioná-lo cada vez que passarmos por este, por exemplo, este três, vamos ser chamados aqui, aqui. E depois temos estes à esquerda do Dr. Chris. E neste caso vai ser chamado uma e outra vez. Então o que vamos fazer é armazenar esses valores dentro de uma lista, um dicionário hashmap, qualquer coisa com que possamos resolvê-lo. E o que vamos fazer é em cada vez que vamos executar esta função ou chamá-la, vamos verificar se este parâmetro específico ou esses parâmetros específicos estão realmente incluídos na lista. Então, se esse for o caso, então já os incluímos e já calculamos o número de subconjuntos. E, neste caso, não precisamos rever isso de novo. Então, uma maneira de fazer isso é, então, por exemplo, se estamos aqui e adicionamos cinco, então adicionamos para os três invasores. Neste caso, quando adicionamos estes três aqui, o que vamos fazer é adicioná-lo à lista, por exemplo. E então cada vez que chamamos este 3, por exemplo, aqui mesmo, se este é realmente o três estava na lista, então nós já calculamos É o número de subconjuntos, então nós realmente não precisamos computá-lo novamente. E isso nos permitirá economizar muito tempo. Porque, por exemplo, se estamos adicionando, por exemplo, se você está aqui e estamos prontos, descobrimos que já fizemos este. O que vamos fazer é simplesmente ignorar o resto da árvore que está aqui. Então, para começar com ele, primeiro de tudo, precisamos definir um novo parâmetro dentro de nossa função, que é o HashMap real ou a lista que vamos usar. Neste caso, vou simplesmente nomeá-lo aqui e nomeá-lo como memorização. Então eu o chamo de memorando. Então o que vamos fazer é criar uma chave e um valor e armazená-los dentro deste memorando. Portanto, será um dicionário ou um HashMap que inclui uma chave e um valor. Então o que vamos fazer é armazenar a chave como o total e o subtotal do índice. E vamos descobrir uma maneira de classificá-los na chave? E o valor deve ser o número de subconjuntos que podemos ter um determinado número específico. Então vamos supor que nós adicionamos neste. O que vamos fazer é guardar uma chave para isto. E é claro que vamos armazenar no valor, por exemplo, que é 0 para isso porque nós realmente não obtemos isso e nove do subconjunto. Então, para fazer isso, o que vamos começar é construir nosso memorando no ponto específico. Então, se chamarmos essa função, vamos fazer é construir a chave no início. E a chave, o que eu vou usar como uma corda. Então eu vou usar uma corda. Além disso, vou guardar a vírgula total, o olho, que é o índice. Então, no esquema deve ser como o, então, por exemplo, o que vamos ter dentro desta chave é a. Suponha que estamos neste ponto que é aqui, o que vamos obter é nove menos cinco, então o total é quatro. Então nós vamos armazenar quatro, vir para cima eo índice é 0, 1 para o índice é dois. Então esta é a nossa chave. E nosso valor deve ser na verdade o número de subconjuntos que podemos fazer dizer este dado ponto. E como podemos calcular? E ele vai voltar todo o caminho para este número, número específico um. E então é assim que a recursão funciona. Então o que vamos fazer é verificar no início, se esta chave está realmente dentro do nosso memorando, então nós já calculamos. Então nós realmente não precisamos rever isso, então nós simplesmente devolvemos. Então, para fazer isso, nós vamos simplesmente adicionar aqui se a chave, então deixe-me apenas fazer isso um pouco menor. E o que vamos fazer é verificar se a chave é um memorando. Mas vamos fazer é simplesmente retornar o valor dentro do esquema, dentro do memorando. Então retorne memorando na chave específica que criamos. Agora, se este não for o caso, então continuaremos, vamos continuar nossa função recursiva. No entanto, o que vamos fazer aqui é em vez de devolvê-los imediatamente, vamos apenas armazená-los em um valor e eu vou nomeá-lo para retornar. Então nós vamos armazená-los em um retorno de dois, que é uma variável simples. E antes de devolvê-los, vamos guardá-los dentro do memorando. Então, como fazemos isso? Continuamos escrevendo o código aqui. Então vamos guardar neste memorando, na chave. Vamos guardar o que temos, por isso vamos guardá-lo para voltar. E depois disso, podemos simplesmente voltar. Então volte para voltar. Então isso é basicamente agora o que realmente fizemos é construir uma chave. Em seguida, verificamos se o nosso valor ou o que pretendemos fazer já está no memorando. Se este for o caso, então simplesmente devolvemos. Que este não é o caso, vamos computá-lo. E depois, claro, adicionado ao nosso memorando que antes de devolvê-lo novamente. Então é isso. Basicamente, isso é o que você precisa fazer. E isso vai nos poupar muito mais tempo e vai diminuir muito a complexidade porque nós não, nós realmente não estamos chamando a mesma função uma e outra vez. Agora, quanto ao tempo de execução real para este problema, vamos pensar sobre isso. Então, para todos esses casos base, o tempo de execução real é O de um. Então não nos importamos com eles. Quanto a este específico, aqui temos as funções que estávamos chamando um aqui e estamos vindo para escrevê-lo. Então é este ou dois. Agora vamos assumir que vamos encontrar Stan. Então o que vamos fazer é verificar quantas ligações estamos fazendo? E a solução real? Ou a resposta é bem simples porque estamos usando este memorando, então não ligamos muito. Então vamos pensar sobre isso. Mas nós realmente chamando é que cada vez que nós decrementamos por lista eu, eu sinto muito, cada vez que nós estamos decrementando por I menos um. E neste caso, vamos chamar-lhe o número. Diz o total de vezes o número real de itens nesta lista. Então, por que fizemos isso? Então vamos pensar assim. O número de causas potenciais que chegamos a fazer está relacionado com o total e n. Porque lembre-se que temos uma lista em vez de tempos opostos. Este é o índice 0 e todo o caminho até 0123. Então o que vamos fazer é ter a chave e o valor de acordo com isso. Então a chave é realmente o que fizemos aqui, que é o total mais o olho. Então, é justo supor que temos n vezes para o olho porque Anual Grande, Eu iria variar de 0 a três. Então nós temos quatro e o total será, na verdade, se, vamos supor que temos nove, será na verdade nove vezes quatro possibilidades que podemos obter este par de valores-chave. E neste caso, este é o total de vezes n. E vamos assumir o pior caso em que vamos chamá-lo duas vezes. Então vamos multiplicá-lo por dois. E este é o nosso tempo de execução que é quatro. Agora, nós sempre podemos remover esta constante e nós vamos ter 0 do total de vezes. E isso é basicamente para esse problema. Agora, nos próximos vídeos vamos implementá-los foram nas línguas que temos que ver vocês. 29. Implementação de subconjuntos Java: Tudo bem, então neste vídeo vamos implementar nossa função usando Java. Então a primeira coisa que vou fazer é criar uma função com os quatro parâmetros que falamos. Então, vou dar o nome como dissemos. Ou, neste caso, talvez você possa transformá-lo em memorandos. Tudo bem, então vou ficar com ele por enquanto. Tão público, estático. E isso deve retornar um inteiro e ele será repetido. E os parâmetros do Parlamento são a lista que temos, o total, o olho e o memorando. E, claro, nossa lista deve estar em uma ArrayList ou menos. Eu vou com, sinto muito, ou uma lista de array ou um array. Eu vou com uma lista de matriz. Então lista de matriz. E será do tipo inteiro neste caso. Depois há a nossa lista. O total deve ser um número, o fim, também um número para um inteiro. E finalmente aqui temos o mapa de hash neste caso. E será preciso uma chave e um valor. Então alceno será uma string e o valor real será um inteiro. Então é isso, basicamente, agora podemos começar com o nosso código. O que vamos fazer no início é verificar, como dissemos, vamos construir a chave e verificar se essas memórias reais e nossa demonstração A menos que seja chamada. Então, como você faz isso? Simplesmente não podemos construir a chave no início. Então deixa-me livrar-me disto. Retorna 0. E nós temos, o que você vai fazer é construir os principais pontos fortes da força k igual a string do total mais a vírgula mais o número real I, que tem o índice. Agora, esta chave está na verdade dentro do nosso memorando. Vamos devolvê-lo sempre escrito o valor do nosso memorando. E como verificamos isso? Vamos usar o memorando que contém o método chave. E neste caso, se for verdade, vamos simplesmente devolver o memorando na chave específica. E sinto muito, precisamos memo isso. Pegue o portão específico. Agora, este não é o caso. O que vamos fazer é verificar se o total é igual a 0. E neste caso, o que vamos fazer é simplesmente retornar 0. Então vamos verificar se o total é igual a 0. Desculpe, precisamos retornar um indicando que encontramos uma lista ou um subconjunto que pode se adaptar ao número específico. Agora, se o total é menor que 0, mas não temos que fazer é simplesmente retornar 0, indicando que não encontramos qualquer quantidade ou menos que possa somar até nove. É maior que nove. Agora, o índice I é menor que 0 também retornará 0. E finalmente, podemos começar com nossas funções de recursão ou causa de recursão. E o primeiro é verificar se o total é menor que esta lista em um índice específico que é i. Se este é o caso, então não podemos incluí-lo. Vamos simplesmente saltar por um índice. E como fazemos isso? Vamos armazená-lo em uma variável. Então deixe-me começar criando esta variável aqui. Portanto, é um inteiro para retornar e ele será inicializado para zeros primeiro. Agora o que vamos fazer é atribuir, para retornar a esta função recursiva. E levará os seguintes parâmetros. O primeiro é o total da lista, e depois eu menos 10, e depois memorando. E finalmente, uma vez que vamos fazer é verificar ou é a última condição. Portanto, não precisamos realmente verificar quais são adicionados ao retorno. Então volte, deve ser uma de duas coisas. Ou é a lista com o número específico na lista sem ele. Assim, com o total I menos1 memo mais lista de recursão com total menos o menos no olho específico. E então vamos fazer o mesmo I menos 1 e memorando. Agora, antes de devolver isto para voltar daqui ou daqui, o que vamos fazer é guardá-lo dentro do nosso memorando. Então, como você faz isso? Vamos escrever memorandos. E então vamos colocar dentro deste memorando, esta chave, e o valor é realmente retornar. Agora, finalmente, podemos simplesmente retornar nosso inteiro de retorno, que é o número de subconjuntos, mas você pode usar. Então é isso basicamente para esta função. Agora o que vamos fazer é construir o frio, a principal função para onde vamos chamar, chamada esta e obter o nosso resultado. Então, como fazemos isso? Vou simplesmente criar uma função principal. Eu sinto muito. Então vamos criar novamente. E dentro de nossa função principal, o que vamos fazer é criar um HashMap. E ele vai levar uma string e um inteiro, e este será o nosso memorando para ser igual a novo HashMap. Agora o que vamos fazer é criar nossa lista que inclui o exemplo que fizemos. Então eu vou escrever lista de matriz, e isso será adicionar um inteiro. E então vamos nomear listas, que é igual a uma nova lista de arrays. E vou acrescentar algumas coisas. Então liste isso. Eu vou adicionar os mesmos números exatos aqui para verificar se temos o mesmo resultado exato. Então 1345. Então eu vou simplesmente adicionar 1345. Então o que vamos fazer é ter o nosso total. Então, para ser um inteiro chamado total, para ser igual ao total que precisamos escolher que basicamente nove. E finalmente o que nós, finalmente, quando eu tiver como o índice que vamos começar com, que é i, será igual à lista, esse tamanho menos um. Então isso é basicamente para nossos parâmetros agora podemos chamar nossa função recursiva e imprimi-la. Então, e simplesmente imprima diretamente. Então, repita em uma lista específica, total I e memorando. E depois disso vamos rodar o nosso código. E vamos ver o que vamos conseguir por um alcalóide. E nós vamos obter dois como o valor final ou o número final de subconjuntos que podemos usar para o número específico que é 9. Então isso é basicamente para a memoização, que é na verdade recursão sem repetição. Como podemos ver, usamos exatamente a mesma lógica de recursão. No entanto, nós realmente não precisamos calcular cada um e cada vez que precisamos de um valor específico, podemos armazená-los dentro de um array e, em seguida, é claro, voltar a eles mais tarde quando precisarmos usá-los. E isso economizará, economizará muito tempo e diminuirá muito a complexidade. Então é isso basicamente para este chamado passo a passo. Vejo você no próximo vídeo. 30. Implementação de subconjuntos: Tudo bem, então neste vídeo vamos implementar uma função usando JavaScript. Então vamos começar com a definição da nossa função. Então eu vou nomeá-lo recorrente, como dissemos. Ele vai pegar uma lista e então você tem o total, nós temos o índice e o mamífero que vamos usar. Agora vamos abrir. E a primeira coisa que vou fazer é criar a nossa chave. E isso será uma corda. Então eu vou simplesmente adicionar perda total, esta vírgula mais eu. Agora o que vamos fazer é verificar se esta chave está dentro do nosso memorando. Então, como você faria isso? Podemos simplesmente usar a função. Se este memorando tem a chave específica, este é o caso, então o que vamos fazer é simplesmente retornar o memorando neste caso específico. Então, como fazemos isso? Vamos pegar um memorando que chegar na chave específica. E então vamos fazer é simplesmente continuar com o nosso código. Então, como temos a função recursiva, dentro desta, temos o total que é igual a 0. Então, se o total é igual a 0, então simplesmente não podemos ignorá-lo e simplesmente retornar um como o valor de retorno. Porque isso significa que chegamos a um ponto onde descobrimos que temos um subconjunto que retorna um total de 0, que alcançou nosso objetivo em primeiro lugar. Então, neste caso, vamos retornar 0. contrário, se o total for menor que 0, isso significa que dentro de uma forma ele retornará 0. E então o que vamos fazer é verificar se eu é menor que 0, então ele também retorna 0. Agora podemos começar com nossas funções recursivas. Então, se o total é menor do que esta lista em um índice específico I. Neste caso, o que vamos fazer é simplesmente retornar a função repetir como dissemos, e desconsiderar, teremos total I menos1 e memorando. E não há uma razão para eu menos 1 é, como dissemos antes, vamos simplesmente saltar. Porque se, por exemplo, temos a lista em i que é igual a 4, e temos o total que é igual a dois. E neste caso, o total é menor do que este valor aqui. Então, podemos realmente colocar esse valor no subconjunto. Então vamos ignorá-lo. Então esta é a razão agora o que nós vamos fazer é simplesmente retornar um estágio definidor, repetir em menos total I menos 1 memo mais a recursão adicionar menos total menos B. Lista em i minus1 lâmpadas estão em I. E então nós estamos indo para decrementá-lo I menos1 e mamífero. Agora, o que, o que não é que nós fizemos isso aqui é porque nós vamos voltar as duas últimas vezes. O primeiro é incluir o 5. Por exemplo, se você tiver cinco anos, se incluirmos o quatro e o segundo, se não o incluirmos. Então é isso que vamos fazer. Vamos simplesmente devolver o total perigoso. Isso significa que não incluímos os quatro, e isso significa que incluímos os quatro aqui. Então é isso, basicamente, agora o que vamos fazer é transformar isso em uma variável. Então, em vez de digitar para retornar, eu vou nomear uma variável aqui para retornar e será igual a 0. Então, neste caso, retornar deve ser igual a esta função. E é claro que vamos fazer exatamente a mesma coisa aqui. Deve ser igual a isso. E finalmente, antes de retornar a esta variável, eu vou armazená-la em Zion dentro deste memorando, indo para usar memorando que dizia, e eu vou configurá-lo para este garoto vai definir a variável de retorno e então eu vou apenas Devolva de volta. Então, basicamente para esta função agora o que vamos fazer é simplesmente experimentá-lo. Então eu vou ter uma lista de 1345 e nós temos um total de nove. E nós temos o I, que é igual a três neste caso. E depois temos o nosso memorando com jazz e novo mapa. Então, mapa de memória, e estamos bem. Então essas são todas variáveis, então deixe-me colocar apenas uma barra. E estamos bem. Esta é variável também. Agora o que vamos fazer é chamar esta função. Vou ter o resultado variável. Observe que para mim, chame essa função com esses parâmetros, então o total e a memória. E finalmente, eu vou apenas desconectá-lo. Então console registrar os resultados que temos. Agora, se formos aqui e tipo nó número de maneiras que JS, que posso chegar a como definido pelo número de maneiras que podemos ter, a fim de alcançar este nove ou o valor específico que temos. Então isso é para a implementação do número de maneiras usando memoização e JavaScript. Vejo você no próximo vídeo. 31. Implementação de o Python: Tudo bem, então neste vídeo vamos implementar nossa função usando Python. Então a primeira coisa que vou fazer é criar nossa função e nomeá-la. Prepare-se. Como dissemos, tomaremos os seguintes parâmetros. O primeiro é a lista. Então vamos ter o índice profundo total real e o memorando que será o HashMap que usamos ou o dicionário neste caso. Então a primeira coisa que vou fazer é realmente criar a chave que vamos usar. Esse é o índice total de vírgulas. Então, como fazemos isso? Vou simplesmente dar um nome de chave. E eu vou simplesmente escrever STR do total mais se tornar um índice mais I. Então STR acti. E então o que vamos fazer é verificar se isso está no dicionário. Se isto é um memorando, então tecla F e memorando, esse caso. Então o que vamos fazer é simplesmente retornar o memorando no memorando de retorno iso específico, a chave específica e terminamos com isso. Este não é o caso. O que vamos fazer é simplesmente verificar os outros casos básicos. Então, o primeiro caso base, se realmente conseguimos e chegamos ao ponto em que o total é igual a 0, vamos retornar um porque escapamos onde temos um subconjunto que pode somar o número específico. Agora, se o total é menor que 0, então não chegamos a um ponto onde temos um subconjunto que somam 0, então vamos retornar 0. Caso contrário, também podemos, também precisamos verificar se há AI, é menor que 0. Então vamos retornar também 0, indicando então não encontramos um subconjunto neste ramo desta árvore que estamos construindo. Agora, podemos começar com nossa função recursiva. Funções. E o primeiro é verificar se o total é menor que o índice do valor que no final exceto nós adicionamos, se esse for o caso, então o que vamos fazer é retornar uma função recursiva sem o índice específico. Portanto, lembre-se que se estamos, por exemplo, em quatro e nosso total é dois, neste caso a pontuação é maior do que 2 diz que isso significa que não podemos adicionar esses quatro em nosso subconjunto, a fim de ter esse total que pretendemos ter. Neste caso, o que vamos fazer é simplesmente devolver este menos total I menos 1 com o nosso memorando. Então, como você faz isso? Simplesmente deixamos que eu crie uma variável aqui. E esta variável deve ser apenas inicializada por 0. E então nós vamos adicionar para retornar que será igual às funções recursivas que estamos usando lista filha I, minus1 e mamíferos. Então, se este não for o caso, então isso nos deixará com dois. Porque, claro, o primeiro é deixar a lista como está, basta diminuir o índice por um. E o outro é apenas pegar a lista e decrementar o total pela lista no específico. Me desculpe, eu esqueci ou t Agora eu menos 1 e mamíferos. Então o que estamos dizendo aqui na verdade é que vamos usar isso por uma vez e simplesmente ignorá-lo pela segunda vez. E isso é o que estamos realmente fazendo aqui, por exemplo, aqui vamos adicionar este quatro ao subconjunto. E ele não vai adicioná-lo simplesmente indo para retornar o subconjunto ou chamá-lo de volta sem antes. E vamos ver um. É comum mais tarde. Então isso é basicamente para a nossa função. Agora, finalmente, o que precisamos realmente fazer é apenas adicioná-lo ao nosso memorando. Então memorando neste medidor é igual a retornar. E então, finalmente, nosso retorno. Agora vamos tentar. O que eu vou fazer é criar nossa lista, que é exatamente a mesma coisa que construímos aqui, 1345. Então lista em 1345, então vamos ter um total de nove. E nós também vamos ter o índice que é um três. Vai começar no último elemento, que tem sido três extras. Então vamos ter o memorando, que é basicamente um dicionário. Agora podemos chamar nossa função, eu vou armazená-lo em um resultado e chamá-lo de resultado, que vai ser uma recursão menos total e mamífero, então você pode simplesmente imprimi-los. Então, agora, se formos em frente e vamos para o CMD, vá para o desktop. E depois por programação dinâmica. E então eu vou simplesmente executar este código python número de maneiras que por eu estou indo para obter uma bagunça. Portanto, temos um erro de sintaxe inválido. E isso é, na verdade, porque nos esquecemos de adicionar a coluna aqui e de acabar com eles critérios. Então, agora, se voltarmos e retornarmos o número de maneiras, desculpe, então aqui temos anúncios. Então é isso. Agora podemos voltar a correr e temos dois como o número de maneiras que podemos ter subconjuntos também que podem somar-se ao número nove específico. Então isso é basicamente para esta implementação deste problema usando Python para vê-lo no próximo vídeo. 32. Subsequência comum mais longos: Olá e bem-vindo de volta. Neste vídeo vamos discutir o problema da subsequência comum mais longa na força S2. Então o que nós vamos ter realmente é força e nós apenas escrevê-las lá em baixo. Então nós vamos ter x, y, z, w. E então o outro será x, o a w. Agora, na resposta disso é na verdade o comprimento da subsequência comum mais longa. Neste caso, é igual a três. Como conseguimos isso? Temos x z w, x z, W. Então, como podemos ver, x, z e w é a subsequência comum mais longa dentro dessas duas cordas. E podemos ter algumas letras entre eles, mas a ordem é a mesma, então temos ax que Z e W. Então, como resolvemos esse problema? Na verdade, nosso primeiro pensamento que iríamos para a recursão já que precisamos encontrar os caminhos possíveis ou as combinações possíveis que poderíamos ter uma cada substring. E então vamos verificar se essa substring corresponde à outra extremidade, a segunda string. E se os jogos fossem encontrar o seu comprimento e, em seguida, apenas devolvê-lo como resultado. E, claro, vamos encontrar o comprimento máximo que podemos ter dentro dessas duas cordas. Então, como você resolve esse problema usando apenas o papel? O que vamos fazer é verificar se as duas últimas letras são iguais. Se este for o caso, como você pode ver, W é igual a W, mas vamos fazer é apenas removê-los de nossos pontos fortes e vamos incrementar nosso contador em um. Então aqui temos um. Tudo bem, então agora o que nos resta é na verdade x, y, e z, e a primeira corda e Ax e Ay e o outro. Agora, se você quiser comparar os dois últimos caracteres, podemos ver que eles não correspondem. O que vamos fazer é tentar de duas maneiras possíveis. A primeira maneira é remover essa tontura e continuar a nossa solução usando x, y e t em primeira mão e B x, z e a, por outro lado. E então vamos fazer a mesma coisa. No entanto, agora nós vamos nos livrar de a, então nós vamos ficar com x, y, z e z. Agora, se você seguir este caminho, como você pode ver, nós temos x, y, z, e a. E neste caso, nós vamos continuar com x e z e a, e a outra solução deve ser x, y, e x. Então, a primeira vez que vamos remover o y e o outro vamos remover a. Agora, lembre-se é que precisamos encontrar um título específico que está no final destes dois fios e um deve ser igual. Agora, neste caso, se continuarmos bem aqui, vamos acabar com x e x em uma extremidade. E este caso encontramos um que combina. Então o que vamos fazer é incrementar nosso contador aqui. E então, é claro, se continuarmos, Hey, nós também vamos acabar com x e x. Então agora temos 11. O que vamos fazer na verdade é verificar neste ponto, por exemplo. Então vamos supor que estamos aqui. O que vamos fazer é verificar o máximo entre as subárvores esquerda e direita. E neste caso eles são iguais, então nós vamos apenas devolver um 1. Agora, vamos fazer exatamente a mesma coisa nesta posição. No entanto, ainda não terminamos este ramo. Então deixe-me terminar. Vamos continuar aqui. Temos x, y, z e z. Eles são iguais. O que vamos fazer é simplesmente remover estas tonturas do feno e incrementar o contador por um. E é claro que vamos acabar com x, y e x no primeiro, e nós vamos ter x e x. E , por outro lado, sinto muito, deixe-me apenas excluí-los. Então vamos ter uma vez, x e x na segunda vez, do que ter XY e nada. E sempre que não temos nada ou uma string vazia, vamos apenas retornar 0 desde que acabamos entrar em um lugar que não há tal string ou caracteres restantes. E um dos pontos fortes, então vamos apenas retornar 0, indicando que não encontramos nada até termos X e X. Eles são iguais, então devemos caber em um. Então, se estamos nesta posição, x, y e x, vamos apenas tomar o máximo entre esses dois pontos fortes e é realmente igual a um. Então aqui temos um. E se estamos nesta fase, X, Y e Z, vamos retornar o máximo entre o abaixo dele, que é na verdade apenas x, y e adiciona, e nós vamos ter um. Então 1 mais 1 deve ser igual, deve ser igual a dois. E neste caso vamos devolver o máximo entre estes dois ramos. Então você terá um e aqui temos dois. Então nós vamos ter que, e claro, nós vamos acabar com 2 mais 1, que na verdade é igual a três. Então é isso. Basicamente, esta é a árvore que podemos construir. E o que estamos realmente dizendo é que sempre que temos dois pontos fortes, isso combina. Dois caracteres que são iguais um ao outro. Mas vamos fazer é simplesmente removê-los e continuar nosso trabalho. No entanto, temos dois passos para o fazer. Nós apenas removemos ocupado ou removemos o a. E nós vamos descobrir qual é a substring máxima ou sub-sequência que pode ser retornada usando x, y, z e a, ou X, Y, Z e X, Z e o outro caso. E eu vou apenas devolver o máximo. E, claro, sempre que tivermos duas cordas ou dois caracteres que correspondam, vamos incrementá-la em um. Então é isso basicamente para esta solução, solução recursiva. E o que vamos fazer agora é escrever um pseudocódigo que nos ajude. E a próxima fase em que vamos otimizá-lo. E nós vamos encontrar uma solução usando o programa dinâmico. Então, antes de fazer isso, deixe-me pensar sobre a complexidade do tempo aqui. Se pensarmos sobre as combinações possíveis em uma string e usando estatísticas, o que vamos descobrir é que se você tiver uma string de quatro letras, digamos X, Y, Z e W. Então vamos encontrar as combinações possíveis que Você pode tirar daqui. Podemos ter x, X, Y, XYZ, então temos y, y, z, y , w, e assim por diante e assim por diante. E neste caso, o que vamos ter é, na verdade, uma combinação de algumas coisas. Então, por exemplo, se você tiver uma combinação de apenas x, vamos ter uma combinação de um e c1. E então se você tem duas letras, X e Y vão ter e C2. E então NC3 todo o caminho até B e C. E nós vamos incluir todas as letras dentro da corda. Então, e isso é realmente igual a dois para o poder n. E como você pode ver, Exponencial. Agora, isso é apenas para calcular as combinações possíveis em uma string. Então temos dois pontos fortes. Precisamos multiplicá-lo por dois. E então nós vamos multiplicá-lo por n. E este n é porque nós temos que calcular a subsequência se ela é comum nas duas cordas. Então vamos descobrir se isso é comum, as duas vertentes. Então nós vamos ter de 0 todo o caminho para n. E neste caso, é na verdade para o poder n vezes n. que possamos nos livrar desses dois. Então a complexidade do tempo é e dois. E como você pode ver, e este bastante grande e tem duas cordas longas, podemos realmente trabalhar com ele e ter um tempo mínimo. Então o que você vai fazer agora é escrever o pseudocódigo e então nós vamos encontrar uma maneira de otimizar a solução. Então deixe-me apenas me livrar desses e eu vou deletar esses também. Agora o que vou fazer é começar com pseudocódigo. No entanto, deixe-me apenas pegar todos estes e menores, colocá-los aqui mesmo. Então agora podemos começar com pseudocódigo. O que vamos fazer na verdade é começar com os parâmetros. Então eu vou apenas nomear a função como mais longa subsequência comum. E neste caso, levará quatro parâmetros. O primeiro é o Pinguim, a segunda string 2, e então temos a posição ou os índices que adicionamos. Então, sempre que dizemos que vamos apagar isto ou vamos mudar para este. Vamos pegar um índice que apenas aponta que este ou este, ou qualquer caractere específico dentro dessas duas vertentes. Então para s1 vamos ter machado e para nós ter y. e a primeira coisa que vamos começar com é o nosso caso base. Então o caso base é na verdade onde nós vamos apenas desfazer e nossa função, e será realmente o que temos uma string vazia. Então, como você encontra se você tem uma string vazia? Como dissemos, se x ou y é igual a 0, como este caso em que temos X, Y, e aqui temos uma string vazia. Então, aquele que está indicando a posição que estamos em S2. Então estamos na posição 0 ou menos um neste caso. E se tivermos o, nós, se estivermos nesta posição, o que vamos fazer é simplesmente retornar 0. Então fx igual a 0 ou y igual a 0. Só vamos devolver 0. Agora, podemos começar com nossas chamadas recursivas. Portanto, temos duas coisas que devemos prestar atenção. Então f, o último caractere é igual. Então, se o último caractere S1 em x menos um e é igual a S2 em y menos 1. Este é o caso. Então vamos continuar o nosso trabalho. Claro, podemos incrementar nosso contador, que é a coisa que vamos devolver. Então isso deve ser realmente escrito de inteiro. Então vamos devolver um. Além disso, vamos chamar a função. No entanto, vamos apenas remover o óleo, diminuir os contadores por um. Então, se estamos nesta posição, w e w apenas indo para decrementar seria em z e a neste caso. Então, como fazemos isso? Vamos simplesmente retornar a mais longa subsequência comum em S1, S2. Como de costume, no entanto, temos x menos 1 e y menos 1. Agora, se este também não for o caso, temos duas coisas para escolher. Nós dissemos que precisamos calcular o máximo entre a árvore esquerda e a árvore direita. Então, como fazemos isso? Simplesmente indo para retornar o máximo entre duas coisas. Essa é a mais longa subsequência comum. Tão mais longo comum sub S1, S2 x menos 1 y. Então, o primeiro, vamos apenas remover o primeiro e último caractere e a primeira coisa. E o segundo, vamos remover o último personagem na segunda força, tão mais longa subsequência comum. E neste caso vamos retornar S1, S2 , e então temos x e y menos um. Então deixe-me escrevê-las aqui. Então temos S1, S2, e então temos x e y menos um neste caso. Então isso é basicamente para a nossa solução recursiva. E como podemos ver, vai demorar muito tempo, já que vamos calcular a mesma coisa uma e outra vez. Então, por exemplo, aqui vamos acabar com x e x, e x e x, x e x. E é claro que você vai continuar aqui. Nós também vamos acabar com x e x. Então nós vamos computá-lo pelo menos quatro vezes neste caso. E como podemos ver, vamos apenas calcular um monte de coisas várias vezes. Então, nossa segunda solução deve ser baseada em programação dinâmica, e nós podemos simplesmente nos livrar de computá-los uma e outra vez. Então isso é basicamente para este problema usando recursão. No próximo vídeo, vamos apenas otimizá-lo. Então vejo você então. 33. Pseudo-código mais longo: Ok, então agora neste vídeo vamos discutir nossa implementação dinâmica de programação do mais longo problema comum de subsequência. Então nós vamos realmente usar tabulação para esta solução. Então o que vamos fazer na verdade é armazenar nossos valores são nossos resultados em uma matriz 2D, e então usá-los cada vez que precisamos olhar para eles. Então deixe-me começar excluindo o pseudocódigo da função passada. E nós vamos realmente fazer é criar uma matriz 2D. E explicarei o porquê em um segundo. Mas esta matriz 2D realmente contém nossas duas cordas. Então, como dissemos, temos x, y, z e w, e então Z e W. Então aqui temos impulsos iria apenas assumir que temos uma string vazia. Então nós temos x, y, z, w. Então nós vamos ter string vazia x, z, a, e W. Então o que nós vamos fazer é começar assumindo que temos uma string vazia aqui e você tem uma string vazia aqui. E nós vamos apenas obter a mais longa subsequência comum. E neste caso, a subsequência comum mais longa é uma string vazia, que é comprimento 0. Agora, se passarmos para o segundo lugar aqui, temos uma cadeia vazia e atos que podemos ver. A subsequência comum mais longa que você pode ter é realmente de comprimento 0 também. E aqui temos, vamos continuar com y e strings vazias no final da string e W e string vazia. E nós vamos apenas preenchê-lo com zeros e apenas calcular a mesma coisa aqui, string vazia com todas essas letras. Então vamos acabar com zeros em ambos os lados. Agora vamos continuar, vamos chegar a este ponto onde temos machado e machado. E o que nós realmente vamos fazer é, se nós temos X e X, mas nós vamos fazer é remover este x daqui e daqui como fizemos com este w. Então, se você tem w e w, e nós realmente fizemos é remover o w's e, em seguida, verifique se há x, y, z e precisão. Então, a primeira vez que vamos ter isso, por exemplo. Então, se este é o caso em que temos X e X, então nós vamos apenas remover isso e verificar o que não contém o último caractere. Então, como fazemos isso? Vamos apenas verificar diagonalmente, porque se removermos X daqui e x daqui, vamos acabar com vazio e vazio, que está aqui. Então vamos adicionar um ao valor daqui, que é 0. Então vamos acabar com um aqui. Agora vamos continuar. Temos x agora e x, y neste caso. Então nós estamos neste aqui, nós vamos ter x, y, e x. Então a subsequência comum mais longa é na verdade, acordo com nossa regra que nós criamos antes, é se nós temos dois caracteres que não combinam, neste caso temos x, y e Ax. O que vamos fazer é verificar por um primeiro de tudo, x e x. e então nós temos, então ele terá x, y e x. A primeira vez que vamos remover o fio. E na segunda vez vamos remover o Imediato. Temos X e X e X, Y e string vazia. Então, como conseguimos essa informação? Nós vamos pegá-los de um antes. Então, se olharmos para o anterior, vamos descobrir que temos X e X. E se olharmos para cima, vamos descobrir que temos x, y, e uma string vazia. Então vamos calcular o máximo entre estes dois de acordo com a nossa regra. Então temos 10, o máximo é um, então vamos preenchê-lo com um. Vamos fazer exatamente a mesma coisa para XYZ e Ax, vamos ter um aqui e outro aqui. Então, se você quiser passar por cima deste x, y, z e w. E então se você tem x, y, z, e w e x, o que nós vamos obter na verdade, porque os últimos caracteres nessas duas strings não correspondem. Vamos continuar com X, Y, Z e X. E o outro deve ser x, y, z, w, e uma string vazia. E neste caso, como você olha para eles? Vamos olhar para a esquerda e vamos acabar com XYZ e agir como podemos ver, é isso. Então é 1. E nós também temos x, y, z, e w, e uma string vazia que é realmente 0. Então, o máximo entre eles é na verdade um. Então, apenas implementando nosso grupo e encontrando o que queremos de computações anteriores. Agora vamos continuar com xy e x. Neste caso, o que vamos fazer é olhar para a esquerda e logo acima do soviético 0 ou um, vamos continuar com uma mesma coisa aqui. Temos 1 e 1, 1, 1. E, claro, aqui temos x z e x, y, z, neste caso z e os fósforos. Então o que vamos fazer é adicionar um nele e olhar para o que é diagonal. Neste caso, temos um e vamos adicionar um. Então, um mais um, vamos guardar dois neste caso em vez de um. E se você olhar para ele, a maneira que nós estávamos lidando com isso antes, se você tem x, y e z. E então nós temos x, z, mas nós realmente fizemos é remover este z e z, nós vamos acabar com x, e X. Nós vamos acabar com também atos e mortes na fase final onde temos aqui um e aqui um, vamos acabar com dois como uma resposta finita. Então, como fazemos isso? Nós simplesmente olhamos para as computações anteriores sem computação x, y e x. Mais uma vez, vamos apenas pegar o valor que vimos a. Então é 2. E é claro que vamos acabar aqui com tudo SO2. Agora aqui temos 0 ou 1, que é 1, 1 ou 1, 2 também quer um ou dois vai acabar com 22 ou dois. Só vou acabar com também. Agora vamos até o fim. Agora, se olharmos para isto, temos x , z, a, w x, y, z e w. E neste caso, como podemos ver, w e w que o mesmo. Então nós só podemos adicionar 12, a diagonal, fazê-lo, que é dois. Então nós vamos acabar com três como um valor final neste caso. Então o que realmente fizemos é que usamos a solução recursiva. No entanto, nós apenas armazená-lo nosso trabalho, os resultados, neste caso matriz 2D, e nós apenas usá-los sempre que quiséssemos. Então, em vez de computá-lo, cada vez que queremos algo, vamos armazená-lo insiste array. E como podemos ver, podemos usá-lo aqui ou aqui, ou aqui. Então lembre-se que temos duas chamadas recursivas. Na solução anterior, temos o que se eles combinam, e neste caso é diagonal e temos o que se eles não coincidirem, vamos tomar o máximo entre este ou este. Então, no início, vamos remover um elemento desta matriz ou desta string. E então vamos remover um elemento desta string e vamos calcular o máximo e devolvê-lo para aqui. Então, basicamente para este problema agora, o que você vai fazer é implementado usando pseudo-código. E então, claro, vamos implementá-lo em nossas línguas. Então faça isso, deixe-me deletar isso e minimizar esse. E, claro, o que vou fazer é apagar isto. E eu vou pegar tudo isso e colocá-lo bem aqui. Agora podemos começar com pseudocódigo. A primeira coisa que vamos fazer é chamar uma função. Vou nomeá-lo mais longo. Subsequência comum, como de costume. Agora, vamos ter que ArrayList ou array ou uma lista. Então eu vou apenas calculá-los como apenas S1 é uma lista. Guarde isso e ficou como uma lista. E é claro que vamos ter os índices em que estamos. Neste caso, eu vou nomeá-lo x e y. Agora, a primeira coisa que vamos fazer é construir nossa matriz 2D matriz e apenas nomeou subsequência comum mais longa, LTS. E será 2D. E, claro, o que vamos fazer é assumir que temos em zeros e cordas vazias. Portanto, o comprimento deste deve ser de comprimento ou tamanho x mais 1. Então x mais um, y mais 1. Agora podemos começar com nossos loops para. Vamos preenchê-lo nesta matriz 2D. E então nós temos o primeiro a ir de 0 todo o caminho para x, ou o comprimento deste. Então será todo o caminho até x mais 1. E então nós temos I mais 1, I plus, plus, então eu de 0 a este. E então temos quatro j de 0 a y mais 1. Claro y mais 1, um não está incluído, ou nenhum é x mais 1. E então temos j plus. E agora podemos começar com a solução M. Então a primeira coisa que vamos fazer é se ou i ou j é igual a 0 vai apenas preenchê-los com zeros. I igual a 0 ou j é igual a 0. O que vamos fazer é preencher o LCS i, j com 0. Então vamos verificar se x em uma posição específica como igual. Neste caso, o que vamos fazer é voltar por um e então vamos armazenar a posição específica. Então, como você faz isso? Agora, lembre-se que temos S1 e S2 como um companheiro como uma lista. E neste caso o que vamos ter como S1 como este x, y, z, e w. S2 deve ser de x, z, a e w. Agora, como você pode ver aqui, temos o índice deste eixo é 0. No entanto, se você quiser computá-los nesta matriz 2D, ele está no índice um. Então aqui temos 0, 1, 2, 3, 4. Então, sempre que quisermos trabalhar com isso, devemos apenas decrementado por um. Então, para fazer isso, o que nós vamos fazer é realmente verificar se, deixe-me apenas fazer isso menor um pouco e apenas tirar isso também torná-lo menor. E agora podemos trabalhar. Então a primeira coisa que vamos fazer é verificar se há mais. Este caractere específico que somos, ADH é realmente igual ao caractere específico que tivemos e a segunda string. Então, se s1 em um x específico menos 1 é igual a S2 em um y específico menos 1. Este é o caso. O que vamos fazer é preencher no LCS x, y, desculpe, aqui temos I e J. Então eu e J. E claro que aqui temos I e J. Então, se eles são iguais, vamos fazer é pegar o um. Eles vão fazer isso. Então, como você faz isso? A I menos 1, j menos 1 e incrementado em um. E não há isso. Estamos assumindo que estamos tomando a condição em um cisne I menos 1. J menos 1 é porque na verdade nossas listas pensaram com o índice 0. No entanto, nossa matriz 2D estamos computando em primeiro lugar para a cadeia vazia. Então x aqui é em um e é em 0 aqui. Então, como fazemos isso? Nós simplesmente tomamos I menos1, que é se você está neste índice I, que é igual a um, e basta tomar isso, nós vamos tomar 0 menos 1, que é 1 menos 1. Vamos pegar 0 e podemos tirar este X da lista como um só. Então temos j menos y e dy menos um. Se este é o caso, então nós vamos apenas calculá-lo a partir da posição diagonal. Agora, se este não for o caso, vamos acabar com a última coisa que vamos fazer é calcular o máximo entre duas coisas. O primeiro é aquele na posição esquerda e o segundo é o acima. Então, como fazemos isso? Quem só vai levar e armazenado no LCS i e J. Então LCS, deixe-me escrever aqui. Só vou mudar isto para cá. E eu vou escrever que SES em I e J igual ao máximo entre duas coisas. Assim, o máximo entre o LCS em I menos 1 e j como é, ou o máximo, ou o segundo que é LCS em I e j menos 1. Então isso é basicamente para Deus, esta é a nossa solução de programação dinâmica. Acabamos de calcular todas as implementações possíveis usando apenas uma matriz 2D. Agora, se pensarmos sobre a complexidade do tempo, se tivermos m como, temos x e y como o comprimento de S1 e S2, e construímos nossa matriz 2D. Então, como podemos ver, temos x, y, uma complexidade de tempo do nosso código. E então nossa solução deve ser a última e nossa matriz 2D, que é três neste caso. Então é isso basicamente para este problema. E no próximo vídeo vamos implementá-lo usando nossas linguagens. Então, vejo você então. 34. Implementação de subsequência comum mais longa: Tudo bem, então neste vídeo vamos implementar nossa função usando Java. Então a primeira coisa que vou fazer é criar a função. Deve ser público, estático, inteiro. E eu vou nomeá-lo subsequência comum, e ele vai tomar os seguintes parâmetros. O primeiro é um array chamado S1. Então temos outro é ter os índices x ou x e y. Então agora o que vamos fazer é criar nossa matriz 2D e ele será de tamanho e nomeá-lo junto. E neste caso, o comprimento deve ser x mais 1 e y mais 1. Agora podemos começar com nossos loops para. Então, como dissemos, vamos fazer é passar por todos estes de 0 a x e de um 0 a y. Então, para um criar um loop for. E neste caso, para ir até o ato, sim, quem poderia ter usado o tamanho do conteúdo longo ou o comprimento? E o segundo seria realmente todo o caminho até y. Agora o que vamos fazer é verificar se eu é igual a 0 ou j igual a 0 suponho que simplesmente afirma que o Islã deve estar em I e j deve ser igual a 0. Neste caso, poderíamos ter ignorado porque sempre que criamos uma matriz 2D para a matriz ou uma matriz em Java, o valor padrão é realmente 0, então podemos simplesmente ignorar isso, mas vamos fazer como nosso pseudocódigo. Então, mantenha-o bem aqui. Agora, este não é o caso. Vamos verificar se o S1 em I menos 1 é igual a S1 adicionar j menos 1. Então senão, se S1 em I menos 1 é igual ao S2 em j menos um. Se este for o caso, o que vamos fazer é colocar anúncios longos I e j, o único diagonalmente para ele. Como você faz isso? I menos 1, j menos 1. E então nós vamos adicionar a ele um. E, claro, se este não for o caso, ainda tem a última condição, que é verificar o máximo entre o da esquerda e o acima. Então vamos começar a longo prazo I e j. o máximo em. Então, Math.max, o pulmão em I menos um j e a longo prazo em I j menos 1. Então é isso. Basicamente, este é o nosso código real. Agora o que vamos fazer é simplesmente retornar o último valor, que está no X e W. Então, depois de terminar deste dois para loops que simplesmente vão retornar o pulmão, o x e y. agora, para experimentá-lo, Eu vou fazer é criar uma função principal onde nós estamos indo para implementar ou assim nossas variáveis então nós vamos chamar a função. Então nós vamos ter S1 para ser basicamente igual a uma lista ou uma matriz de x. Então y, eu sinto muito, eu vou apenas colocá-los como caracteres, então x, y, e então nós temos z e w. Z e w. fechá-lo, e nós tem S2, que é também uma matriz de X, Z e W. Então x, z, e então temos um e w. agora estamos bem. Podemos continuar com o x real e y. Então estes são os índices que devem estar em. Então este é o comprimento que é quatro neste caso. Então, x e y iguais a 4. Agora eu esqueci de fazer é imprimir a função. Então eu vou armazenar o resultado, a função real, e então, claro, vou imprimi-lo. Então eu vou imprimir o resultado. Temos um erro de digitação, isto é w. Agora, se formos em frente e rodarmos este código, o que vamos fazer para obter um CI é três, indicando que este é o número de caracteres ou o comprimento de sua sub-sequência que temos. Agora, para visualizá-lo, o que você vai fazer é simplesmente imprimir cada vez que entrarmos neste loop. Então eu imprimi nossa posição. E é claro que vou ter espaço aqui e linha impressa aqui. Agora, se formos em frente e executarmos este código, obteremos o mesmo resultado exato que construímos aqui. Temos zeros, um, dois, e o último é na verdade três, indicando que este é o nosso resultado aqui. Então é isso para este exemplo. Esta é a implementação deste código usando Java. 35. Implementação de subsequência comum: Ok, então neste vídeo, podemos implementar nossa função usando JavaScript. Então a primeira coisa que vou fazer é criar a função. Vou emitir mais longa subsequência comum. E levará os seguintes parâmetros. Então temos S1, S2, estas são duas listas e matrizes. E nós também temos os índices e nomeá-los x e y. Agora podemos abrir esta função. E agora o que vamos fazer aqui, temos um erro de digitação. Então esta é a função. Agora o que vamos fazer é criar nossa matriz. Então eu vou dar um nome. Talvez. E, neste caso, pode ser uma nova matriz de tamanho x mais 1. E, claro, vamos ter uma nova matriz dentro de cada posição e fazê-lo. Farei isso em um segundo. Então nosso primeiro for loop deve ser começando em I igual a 0, em seguida, todo o caminho para x incluído e, em seguida, incrementado. Agora o segundo para loop deve ser, deve começar em j igual a 0. J é menor ou igual a y e incremento j. E, claro, cada vez que chegarmos a uma posição de I, vamos criar uma nova matriz, y mais 1. Agora o que vamos fazer é verificar se eu é igual a 0 ou x é, eu sinto muito, ou j é igual a 0. Então este é o caso. O que vamos fazer é simplesmente armazenar em I e j no valor de 0. Agora, se este não for o caso, o que vamos fazer é verificar se na posição S1 e S1, S2 J menos um. Se eles são iguais, então vamos fazer algum tensor como se disposição, que é S1 em I menos 1 é igual a S2 em J menos 1. Este é o caso. O que vamos fazer é incrementar i e j por um valor mais d, que está nesta posição, I menos 1, j menos 1, que é a posição diagonal do valor específico. Agora, como você vai fazer, se este não for o caso, nós vamos tomar o máximo entre duas coisas. O primeiro está na posição que está à esquerda, e o segundo que está na acima. Então o que vamos fazer é começar nesta posição específica, que é I j. O máximo entre o primeiro que é um longo prazo em I menos um e, e eu sinto muito j. e então o longo I e j menos 1, este caso. Este é o nosso código. Finalmente, depois de terminar esses dois para loops, o que você vai fazer é simplesmente retornar o último valor que temos, que é o longo, venha em x e y. Agora, se formos em frente e imprimi-lo, deixe-me basta começar criando listas de x, y. Então nós vamos ter z e w. Z. Z. Então nós temos w. E nós temos lista de, deixe-me apenas nomear as variáveis. Então temos variáveis. E neste caso, o segundo deve ser de x, y a, desculpe, x, z e a e W. Então x, z, a e W. E agora, finalmente, o que vamos fazer é ter os índices que estão em Posição 4 por enquanto. Então var x é igual a 4, y, que também é igual a quatro. Agora o que vamos fazer é simplesmente chamar a função e bloqueá-la. Então eu vou armazená-lo no resultado. Venha e nós vamos chamá-lo de S1, S2, x e y. e então, finalmente, eu vou fazer logout para que o conjunto. Agora o que vamos fazer é ir para o nosso CMD. E, claro, podemos adicionar nossa programação dinâmica de desktop e JavaScript. Isto é tão mau. E então, claro, vamos executar nosso código usando o nó C dot js. Se executarmos nosso código, vamos obter três como o valor final que obtivemos desta função. E esta é a subsequência comum mais longa que podemos ter. Isso é x, y, e w nada que vamos fazer é visualizar esta função ou esta matriz 2D que acabamos de criar aqui. Então, em vez de retornar o último valor, eu vou retornar toda a matriz 2D, matriz 2D. E se rodarmos de novo, obteremos o mesmo resultado exato que construímos à mão bem aqui. Como você pode ver, temos zeros, uns, e todo o caminho até o último, que é na verdade um três que disse, por exemplo, para este exemplo, esta é a implementação deste problema usando JavaScript. 36. Implementação de subsequência comum mais longo a sequência: Tudo bem, então neste vídeo, nós vamos fazer é realmente criar a função usando um Python. Então eu vou apenas criar este arquivo subsequência. E agora o que vamos fazer é começar com a nossa definição ou a função que vamos usar, apenas indo para a imagem do câncer de pulmão e tomar os seguintes parâmetros. Então temos S1, S2. Você também tem x e y como os parâmetros ou os índices que vamos usar. A primeira coisa que vou fazer é criar o submarino comum mais longo. E esta será a lista que vamos usar. E para realmente ser uma lista de listas. E o primeiro deve ser para I na faixa de x mais 1. E então, claro, a segunda unidade estará na faixa de y mais 1. Então é isso. Agora o que vamos fazer é começar com o nosso loop for. Então, para estar na faixa de 0 todo o caminho até x mais um, uma vez que x mais 1 não está incluído. Então este é o primeiro, como para o segundo seria enraizado de 0 todo o caminho até y mais 1. Agora o que vamos fazer é verificar se i ou j são iguais a 0. Se eu for igual a 0 ou j é igual a 0, este é o caso. O que vamos fazer é simplesmente implementar ou adicionar nesta posição, a posição específica em I e j tem um valor de 0. Agora, se este não for o caso, vamos verificar se em Aswan High menos 1 é igual a S2 menos S1. Então S1 I menos 1 igual a S2 em j menos um. Então, se esse for o caso, o que vamos fazer é simplesmente pegar o valor diagonal que temos e armazená-lo com incremento um por si só. Mais longa subsequência comum em I menos 1, j menos 1, e nós vamos adicionar um a ele, e é isso. Agora, a última condição que vamos ter é que se essas duas condições não se aplicam, vamos apenas armazenar o máximo entre duas coisas. O primeiro está à esquerda. Então, será o máximo entre a subsequência comum mais longa, I minus1 e j, que é a vertical, então está acima. E o segundo será em I e depois j menos 1. Então é isso basicamente agora, depois de terminar de cavar isso para a esquerda ou para a matriz, o que você vai fazer é simplesmente retornar os valores nos índices específicos. Agora para experimentá-lo quando você está indo para fazer é simplesmente criar a lista. Então temos x, y, então temos z e w. Então temos S2, que consiste em x. Temos z, então temos a, e então temos w. Isso é basicamente agora como para o machado igual a quatro, y igual a 4. Agora vamos imprimi-lo. Vamos imprimir s1, S2, x e y. Então agora vamos conferir. Eu vou para aqui e eu vou para por programação dinâmica. Cinco, desculpe, tão dinâmico, desculpe, temos quaisquer erros de digitação e vamos fazer é simplesmente executar o código. Então agora vamos executá-lo usando Python e Python. Tão mais longa subsequência comum dot py. Então aqui temos um erro. Então, sinto muito, aqui temos conjunto de usar LCF, temos LF e Python. Então LF, Python. Então também precisamos pagar e o que realmente fizemos isso, chamamos a função e imprimi-la. Por isso deixa-me guardá-lo, desculpa. E como resultado, então eu vou apenas colocá-lo e resultados de erro e, em seguida, apenas chamá-lo ou impresso depois que eu terminar de calcular o valor do sal. Agora, depois disso, o que vamos fazer é simplesmente ir aqui e arrastar de novo. E como podemos ver, temos três, o valor final, que é a subsequência comum mais longa que podemos obter. Agora, em vez de retornar esta lista inteira ou o último elemento na lista, eu vou retornar esta matriz 2D. Agora, se você voltar e atualizar, e como você pode ver, nós temos nossa função, nossa matriz 2D, e como podemos ver, é exatamente a mesma, a menos que nós apenas construímos à mão. Então é isso basicamente para este problema, o último valor é realmente o que estamos interessados. Então esta é a implementação desta função subsequência comum mais longa usando Python. Vejo vocês no próximo vídeo. 37. Subsequência mais longo de maior sequência: Olá e bem-vindo de volta. Neste vídeo vamos discutir o problema da maior subsequência crescente. Então, a idéia deste problema é que nos é dada uma lista de inteiros e vamos retornar o comprimento da sub-sequência crescente mais longa. Então, por exemplo, se temos esta lista aqui, temos 15, 7283, então o que vamos retornar é o número cinco, indicando a subseqüência crescente mais longa neste caso, que é O157 que oito e 10. Então esta é a subsequência comum mais longa e vamos retornar o comprimento dela. Agora, a primeira vez que tenho ao resolver este tipo de problema é geralmente recursão. Uma vez que precisamos encontrar a sub-sequência crescente mais longa, podemos pensar sobre a idéia de encontrar a subsequência crescente mais longa para cada índice. Então, por exemplo, se estamos aqui, a subseqüência crescente mais longa para este elemento específico é na verdade um. Agora, aqui, o que vamos conseguir são dois, porque temos 15. Então às sete, são três, depois dois. Voltei aos dois. Já que temos 12, podemos lidar com isso. Então aqui às oito vai ser quatro. E então, claro, às três e será 1, 2 e 3, que é 3, e às dez serão cinco. Então esta é basicamente a idéia sobre este problema. Agora o que vamos fazer é verificar como podemos implementá-lo usando recursão. Então a primeira coisa que vamos fazer é construir o informante que vamos ter. Então lembre-se que sempre que queremos resolver este problema, vamos supor que estamos na posição específica, que está no índice número 0, 1, 2, 3 e 4. Então estamos no índice quatro. Como podemos resolver isso para o clima específico? Como podemos saber que a subsequência comum mais longa para este elemento é na verdade quatro. Então a primeira coisa que vamos fazer é criar a condição ou a função para o índice. E o que vamos fazer na verdade é verificar o máximo entre todos estes antes deste índice específico e, em seguida, adicionar a ele um se ele é maior do que os números reais. Então, como fazemos isso? Vamos adicionar um ao máximo entre F3 e F2, F1 e 0. E, claro, todos eles devem ser menores ou iguais a esse elemento específico em um índice específico. Então isso é uma obrigação, e claro, esta é a função que vamos fazer agora lembre-se que isso é apenas para, uh, para, agora, se você quiser calcular f 0, F1, F2 e F3, vamos fazer exatamente a mesma coisa aqui. Então, por exemplo, temos isso e, em seguida, temos aqui terá que calcular para F1 e F2. E como você pode ver, estamos lentamente construindo uma árvore onde encontrar apenas para este elemento específico de quatro, vamos calcular tudo isso e depois computá-los novamente e novamente e novamente. E é claro que vamos fazer exatamente a mesma coisa para todos esses índices bem aqui na nossa lista. Então, como você pode ver, isso terá uma abordagem exponencial e o tempo de execução será exponencial. Deixa-me mostrar-te o pseudocódigo disto. O Jim. E, claro, vamos tentar otimizá-lo usando programação dinâmica. Então a primeira coisa que vamos fazer nesta abordagem recursiva é construir a função. Então eu vou simplesmente nomeá-lo mais longo aumento e ele vai tomar os seguintes parâmetros. Vou ter a matriz ou a lição. Vou dar o nome da lista. E eu vou ter o inteiro e indicando o comprimento desta lista. Agora o que não queremos fazer é verificar o caso base. Agora, lembre-se que devemos retornar o comprimento máximo. Então talvez eu possa criar uma variável global lá fora. Talvez eu lhe dê o nome de comprimento máximo. E neste caso, vou atualizá-lo dentro do nosso código aqui. Então o que vamos fazer é verificar se você está no caso base, que é n igual a 0 ou 1 neste caso, o que vamos assumir é que vamos começar com um. Então nós realmente não precisamos calcular 500. Vamos começar com F1, F2, e assim por diante. Então um ventilador igual a 1 é igual a um que vamos fazer é simplesmente retornar um, já que é o primeiro elemento na lista e devemos retornar seu comprimento, que é basicamente igual a um. E se este não for o caso, lembre-se que devemos calcular todos esses quatro. Índice específico. Então, se estamos no U4, precisamos computar F3, F2 e F1. Então, neste caso, precisamos de um loop for para fazer isso. E para cada um deles, vamos verificar o valor de retorno. E se for maior do que o máximo que já temos, devemos atualizar o nosso máximo. Então, como fazemos isso? Vamos simplesmente definir duas variáveis. Nosso resultado que vamos conseguir. E, claro, o máximo, que é o máximo atual. Então vou chamá-lo de “Current Max”. E agora o que vamos fazer é calcular isso. Então, como fazemos isso? Vamos chamar essa função para esses índices específicos. Então para, vamos começar com o olho todo o caminho de um até o valor de n. E, claro, podemos incrementá-lo à medida que passamos. Então o que você vai fazer é obter os resultados desta função. Então vamos armazenar no resultado a função de aumentar com nossa lista e os índices. Agora, eu sinto muito, o índice é, agora o que nós vamos fazer é verificar se esta lista no índice específico I menos 1 e n menos um. Se isso for menor que n menos um, então devemos atualizá-lo. Então, como fazemos isso? Deixe-me pegar isso e torná-lo menor. E vamos ver dessa forma. Os alimentos estão nesta posição específica onde precisamos calcular isso. O que vamos fazer basicamente é passar por todos esses F1, F2 e F3. E vamos verificar se a posição específica é o elemento nesta lista é menor do que o elemento de pagar. Então, por exemplo, se estamos nesta F1 e deixe-me supor que este é um quarto. Então este é o índice 4, 1234. E o que vamos fazer na verdade é verificar se esta posição específica é menor que esta. É. Então o que vamos fazer é verificar o comprimento máximo neste caso, qual deles é? Menos do que o comprimento máximo nesta posição específica, que é basicamente 0 neste caso. E então se isso é maior que este, se for, então podemos pegar isso incrementado por um e colocá-lo aqui, que é basicamente dois. Vamos fazer exatamente a mesma coisa aqui quando calcularmos este. Então o comprimento aqui é dois. É maior ou igual a 2? Sim, é. Então só pegamos dois mais um e incrementamos se esse for o caso. Agora, como podem ver, cinco é menos que, sinto muito, é maior que dois, então podemos fazer isso. Portanto, temos duas etapas ou duas condições a serem satisfeitas para que possamos atualizar este máximo atual. Então deixe-me escrevê-las. A primeira coisa que vamos verificar se a lista na posição específica, que é I menos um, porque estamos começando em um e esses índices começam com 012, 34, e assim por diante. Então, se esta lista I menos 1 é menor que a lista específica no final com que estamos lidando. Então n menos um, se este for o caso e nosso resultado mais um. Então precisamos lembrar que, se você estiver na posição específica, basta pegar os resultados do final incrementados por um e depois verificar. Então, se esse resultado for maior que o máximo atual que temos, atual max, então o que vamos fazer é simplesmente atualizar o máximo atual. Assim, o máximo atual seria, neste caso, seu resultado deve ser igual ao resultado mais 1. Então isso é basicamente assim que podemos atualizar nosso máximo atual. Agora, depois de terminar de todo este loop para, que é deste. Tudo bem, então deixe-me desenhar. O que vamos fazer é simplesmente verificar se o máximo atual que acabamos de receber neste caso é maior do que o comprimento máximo da matriz total ou P lista total. Se este for o caso, então precisamos atualizar esse comprimento máximo. Então F total, desculpe, se o máximo atual é maior, então o comprimento máximo. Precisamos atualizar o controle deslizante. Portanto, o comprimento máximo deve ser igual ao máximo atual. Então isto é basicamente este é o nosso código e código inteiro. Agora, depois de terminar tudo isso, o que devemos retornar, esta função na verdade não é o maxlength, é o máximo atual. E a razão por que é isso? Porque deixe-me pegar tudo isso e torná-los um pouco menores. Eu sinto muito. Então deixe-me fazer isso a partir daqui. Eu vou fazer loop e apenas minimizá-lo e colocá-lo aqui como antes. E não há que nós vamos retornar este máximo atual é porque nossa função é sobre esta correspondência atual. Então lembrem-se, se estamos neste loop de quatro, o que vamos fazer é pegar esse máximo atual de cada um desses elementos, então devemos retornar o máximo atual. No entanto, quando precisamos chamar essa função não será basicamente interessado neste tipo de matemática. Estamos interessados na versão atualizada do maxlength com que estamos lidando. Então, para dizer que basicamente para este pseudocódigo, e como você pode ver, isso corre de forma exponencial enquanto estamos computando este pulmão. Obrigado cada vez que terminamos isso para loop e estamos chamando isso tantas vezes porque é um recursivo. Então isso é basicamente para este vídeo. No próximo vídeo vamos tentar otimizá-lo usando programação dinâmica. Então, vejo você então. 38. Subsequência maiores de forma significativa de maior corda intensa 1: Ok, então neste vídeo vamos tentar otimizar nossa função recursiva e usando programação dinâmica. Então a coisa é, sempre que estamos usando recursão é chamar esta função uma e outra vez. Por exemplo, se estamos nesta posição específica de sempre para o que estamos basicamente fazendo é codificar F1, F2 e F3. E neste caso um F2, vamos chamar F1 e F3 vamos chamar F1 e F2 novamente. Então, em vez de fazer tudo isso, o que vamos fazer é simplesmente criar um loop for que percorre todos esses juntos. Então F1 e F2 e F3 e verifica o máximo entre eles. E depois disso, vamos devolvê-lo ou apenas colocá-lo neste F4. E, claro, vamos incrementá-lo em um. Então, em vez de usar esse pseudocódigo onde eu vou fazer é simplesmente se livrar dele e começar de novo. Então o que vamos começar com é realmente construir a função onde vamos ter a lista e o índice. E então eu vou chamá-lo de maior aumento do servidor SQL. Levará uma lista e o número inteiro. E agora o que vamos fazer é criar uma lista onde vamos armazenar a maior subsequência crescente até o ponto desses índices. Então, por exemplo, se você está nesta posição específica, que é o índice um, mas vamos armazenar na outra lista que vamos criar é a subseqüência crescente mais longa para este caso, que é na verdade dois . Tudo bem, então deixe-me fazer isso aqui. Esta é a nossa segunda lista, então eu vou chamá-la de L I, S, indicando que esta é a sub-sequência crescente mais longa. E será de tamanho. E neste caso, como de costume, agora a fazer é inicializar nossos índices I e nosso valor máximo. Então temos eu, J e Max. E todos estes devem ser inicializados para 0, portanto máximo para ser em 0. Agora o que vamos fazer é começar com o nosso loop for, Salem, o LINCS com um. Uma vez que em cada índice temos, por exemplo, se estamos no índice dois, o número mínimo aqui é um. Então o comprimento da subsequência mínima possível na verdade é um, e ele apenas inclui este número em si. Então, por exemplo, se você está nesta posição específica cinco, o comprimento mínimo que podemos ter é na verdade um, que é neste cinco aqui. Então, para fazer isso, eu vou pagar olhar de todo o caminho até n e simplesmente armazenar e LINCS na posição específica I, o valor de um. Então o que vamos realmente fazer é criar para um ativo para loops, passar por todos esses itens ou todos esses elementos dentro desta lista. E, em seguida, em cada elemento. Então vamos supor que estamos nesta posição específica, que é a posição específica 3. Mas vamos fazer é passar por 012, obter o máximo entre estes. E enquanto o valor dentro dessas posições for menor que o valor em dois e o máximo aqui for maior do que isso, então podemos atualizá-lo. Então o que vamos fazer é deixar que eu escreva aqui, mas antes disso, deixe-me minimizar isso e depois continuar. Então o que nós vamos dizer é que nós vamos ter um loop for de I até n. E então dentro deste para loop, nós vamos começar de 0 todo o caminho até I. Claro, eu deveria começar em 0. Então o que vamos fazer é verificar, como dissemos, se a lista nesta posição específica eu é maior do que a lista em, eu sinto muito, aqui temos j de 0 todo o caminho até ISO, j igual a 0 o caminho até i. E aqui nós tenho igual a 0 todo o caminho até n e é menor em I é maior do que a lista. Então, se estamos, por exemplo, neste aqui e temos um igual a 3 que suponha que o que vamos fazer é olhar através de todos esses elementos de 0 a. E o que vamos fazer é verificar se esses itens são menores do que o item que temos. Então, se for esse o caso, o que vamos fazer. Então vamos acabar com isso com a maior subsequência crescente. Então vamos supor que estamos nesta posição específica onde temos um. Vamos pegar um e adicionar um a ele. Então, isso fará dois. E lembre-se que inicializamos tudo isso em um. Então, se você é a posição específica que está no índice três, e nós vamos ter um AD como a sub-sequência crescente mais longa. Por enquanto, vamos tomar 1 mais 1, que é igual a dois. Vamos verificar se dois é maior que um. Se for esse o caso, então precisamos atualizar isso. Então, para fazer isso, vamos verificar em uma posição específica, que é j mais 1 é maior que o LINCS na posição de I. Se este for o caso, então precisamos atualizar nosso LAS no atoi. Então eu vou é em, eu deveria ser igual a S em j um. Então é isso, basicamente, agora vamos ter uma lista destes aqui. Então vamos ter 1, 2, 3, 2, 4, 3 e 5. E, claro, para obter o máximo, vamos criar outro loop for que nos ajude a obter o máximo desta lista de Elias. Então, para fazer isso, deixe-me fazer isso aqui. E o que vamos fazer agora é criar outro loop for, looping através I igual a 0 todo o caminho até o fim. E nós vamos encontrar um máximo não distorcido e a variável máxima bem aqui. Então, se Elias em I é maior que o máximo, nós vamos armazenar e maximizar este valor de Elias em I. Então é isso basicamente agora o que vamos retornar é simplesmente retornar o máximo que acabamos de computar, que é na verdade o comprimento da subsequência crescente mais longa que temos escrevendo. Então, simplesmente devolvemos o Max, e agora estamos bem. Então esta é a nossa função. Agora, se quisermos chamá-lo, podemos simplesmente executá-lo usando o array ou o menor que temos e é índice ou o tamanho dele. Então é isso basicamente agora, pensando sobre a complexidade do tempo. Aqui, nós usamos dois aninhados para loops, começando de 0 todo o caminho até n. E nós também temos de I igual j igual a 0 todo o caminho até i, que é basicamente no pior cenário, nós vamos ter n, Então nós têm m ao quadrado bem aqui. E o que nós realmente fizemos no espaço auxiliar é que nós os vendemos em uma matriz ou uma lista, e ele vai levar um espaço de n. Então a complexidade do tempo é O n quadrado e a complexidade do espaço é O de n. e ele vai levar um espaço de n. Então a complexidade do tempo é O n quadrado e a complexidade do espaço é O de n. basicamente para este problema. No próximo vídeo, vamos implementá-lo usando nossos idiomas. 39. Implementação de subsequência maior de maior sequência de aumentando: Oh, hey, então neste vídeo vamos implementar nossa função usando Java. Então a primeira coisa que vou fazer é criar a função que podemos usar. Então, é estática pública, e eu vou nomeá-lo o mais longo, aumentando. E vai levar o cinza. E agora o que vamos fazer é criar a sub-sequência crescente mais longa, que também será uma matriz de tamanho n, como dissemos. Então vamos inicializar nossos índices. E é claro que vamos inicializar o máximo que vamos usar. Depois disso. A primeira coisa que vamos fazer, como dissemos, é preencher a lista a maior subsequência crescente com uns. Então vamos começar com I igual a 0. Eu é menor ou igual a n, e vamos incrementá-lo. Então o que vamos fazer é preencher a maior subsequência crescente na posição específica I, o valor de um. Depois disso, vamos continuar com o nosso loop for. Então temos dois aninhados para loops I menos do que n e eu mais. Então vamos continuar com j igual a 0, j menor que i, e implementar j. como dissemos em nosso pseudocódigo, vamos verificar se esses valores na lista ou a matriz em I é maior do que a matriz em j. E vamos verificar se a maior subsequência crescente em j mais um é maior do que a maior subsequência crescente em que eu tenho. Este é o caso. Precisamos atualizar a maior subsequência crescente em uma posição específica. Então, se matriz em I é maior do que a matriz em j, e como dissemos, a maior subsequência crescente em j mais um é maior do que a maior subsequência crescente em I tenho este é o caso, então precisamos atualizar ele. Então maior subsequência crescente, eu deveria ser igual a um em j mais um. Então, basicamente, é assim que podemos construir nossa matriz. Agora, após a pressão desses dois aninhados para loops, precisamos encontrar o máximo e armazená-lo e o valor máximo. Então nós vamos olhar através I igual a 0 menos que n e, em seguida, incrementar I. Então nós vamos verificar se o máximo é menor do que a subseqüência crescente mais longa na posição específica que este é o caso, então nós devemos atualizar o máximo para ser o valor que temos aqui. Agora, depois disso, mas vamos fazer é simplesmente devolver o máximo que temos. Agora, vamos tentar. O que eu vou fazer é criar uma função principal onde eu vou criar a matriz que nós queremos. Agora. Então, a aeração seja, deixe-me usar o mesmo exemplo exato. Temos 15 728310, então 157283. E então temos o comprimento n, que é basicamente o comprimento, o comprimento desta matriz, 1, 2, 3, 4, 5, 6, 7. Então n igual a sete. Agora e eu vou fazer é armazenar o resultado em um inteiro chamado resultado. E eu vou chamar essa função, que é a sequência crescente mais longa. E, claro, eu vou imprimir o resultado como aqui, alfa, vá em frente e execute este código. Vou pegar cinco como a maior subsequência crescente. E se voltarmos aqui, você pode achar que nosso menos consiste em cinco elementos indicando que o comprimento desta lista é realmente cinco. Então é basicamente agora 400 vão mais longe e visualizam isso. I listar a subsequência crescente mais longa que consiste em 1232435. O que eu vou simplesmente fazer é retornar uma lista ou um array em vez disso. E eu vou simplesmente voltar aqui a maior subsequência crescente. Então o que eu vou fazer é armazená-lo em um resultado como este. E eu vou criar um loop for. E, claro, eu vou imprimi-lo como este algum espaço. E se formos em frente e rodarmos esse código novamente, teremos 1232435. Agora. Precisamos apenas lá. Então temos 1232435 e como podemos ver, temos 1232435. Assim, os resultados correspondem às nossas expectativas. E esta é a documentação da subsequência crescente mais longa usando Java. 40. Implementação de subsequência maiores de maior sequência de aumento: Como k. Então, neste vídeo vamos implementar nossa função usando JavaScript. Então a primeira coisa que vou fazer é criar nossa função e eu vou nomeá-la. Vou pegar uma lista e o número inteiro e indicar o tamanho desta lista. Agora, o que vamos fazer é criar outra lista que é a sub-sequência mais longa que aumenta. Vou chamá-lo de Ally. E uma matriz de e este é o tamanho. E eu ia enchê-lo com um 1s. Então é basicamente isso. Agora vamos inicializar os índices I e j. E então vamos inicializar um máximo que vamos usar, que será igual a 0. Então vamos começar de I a 0. Sinto muito, de eu igual a um até eu igual a e, e apenas implementado. Então vamos tomar J, que é igual a 0. Então j de 0 a I, e é claro que vamos incrementá-lo. Agora vamos fazer a mesma coisa que o pseudocódigo. Nós vamos verificar se a lista em i é maior do que o menor que j. Então, se lista em i maior que a, menor que j, e precisamos verificar se o Elias em j mais um é maior que DALYS em i. Se este for o caso, nós precisa atualizar esta aliança em I para ser igual a Ls em j mais 1. Então, depois disso, podemos retornar o máximo. Agora, o que vamos fazer é procurar o máximo dentro da lista. Então nós vamos começar de 0 todo o caminho até e, e atualizado. Então vamos verificar se Max é menor que o Elias na posição específica em que vamos atualizá-lo. Então Max deve ser Elias em mim e, claro, depois disso, devemos simplesmente devolver o máximo. Então é isso. É isto. Esta é a função que vamos usar agora, eu vou fazer é criar nossa lista, então para executá-la, então vamos apenas igual à mesma lista exata que usamos. Temos 15, 7283 e 10. Então 157283 e 10. Então temos n que é igual a 7, basicamente. Então, depois disso, eu vou armazenar o resultado em uma variável chamada resultado. E dois serão os mais longos, aumentando como menos de 10. Depois disso, vou desconectá-la. Então eu vou registrar os resultados depois disso. O que eu vou fazer é ir para o meu diretório, que é a programação dinâmica JavaScript. E, em seguida, eu vou executar este código usando Node script java. Sinto muito, Node. E o nome do arquivo mais longo crescente subsequência ponto js. E então temos um erro aqui. Então vamos ver, dentro do módulo não encontrado. Então acho que escrevi errado. A maior subsequência crescente. Então está aumentando o nó sub-seqüência aprender subsequência crescente que não tem perícia forense e nós vamos obter cinco como a subseqüência crescente mais longa que temos. E se você quiser visualizar realmente esta lista da sub-sequência crescente mais longa, que é 1, 2, 3, 2, 4, 3 e 5. Podemos simplesmente devolver o Elias em vez do máximo aqui. E agora se eu for em frente e voltar, lê-lo novamente, eu vou obter 1232435 como o resultado que esperávamos e como o resultado que nós realmente geramos até o final aqui. Então é isso basicamente para este problema é, é que para a sub-sequência crescente mais longa usando JavaScript. 41. Implementação de subsequência maior maior de que: Ok, então esta é a implementação Python do problema de sub-sequência crescente mais longo. Então a primeira coisa que vou fazer é definir a função. Vou citar o aumento mais longo. E ele vai levar a matriz ou a lista que nós vamos ter uma lista simplesmente nomeada. Então vamos ter o índice n ou o tamanho desta lista. O que vamos fazer na verdade é armazenar e uma nova lista. Eu vou emitir aliado a nós. Nós vamos armazenar uma vez e eles não vão ser. E uma vez. Depois disso, podemos começar com o intervalo ou os dois para loops. Então, para eu no intervalo de 1 n, nós vamos ir de j no intervalo de 0 até i. E nós vamos verificar, como dissemos antes, dentro de pseudocódigo, podemos verificar se a lista em i é maior do que j. então deixe-me escrevê-lo para baixo bem rápido. Então menos em eu é maior do que a lista L, J. E nós também temos, desculpe, e nós vamos ter o LINCS. J mais 1 é maior do que o chapéu LAS I. J mais 1 é na verdade maior do que o Elias em i f. Este é o caso. Então o que vamos fazer é atualizar a ALS na L2. Vou adicionar j mais 1. Depois disso, podemos definir o máximo que vamos usar. Portanto, o máximo deve ser no primeiro 0. Então vamos olhar por toda a lista de Elias, que tem a maior subsequência crescente para cada um deles. E isso é, e neste caso para eu na faixa de 0 todo o caminho. E então eu vou simplesmente escrever, e se o máximo é igual, último maior do que a variável máxima real que temos aqui, então precisamos atualizar este aqui. Então, como fazemos isso? Podemos simplesmente escrever o máximo é menor do que o LSAT. Vou atualizar o máximo para estar em uma posição específica i. Depois disso, o que vamos simplesmente retornar como o máximo que criamos agora. Agora, para verificar, o que eu vou fazer é criar uma lista, que é exatamente a mesma coisa que nós, hey, então nós temos 15728310. Então vamos ter dentro desta lista 15, 7283 e 10. Então vamos ter n, que é igual a 7. Depois disso, eu vou armazenar um resultado, a sub-sequência crescente mais longa com menos e n. E, claro, eu vou imprimir o resultado. Agora, dê uma olhada. O que eu vou fazer é simplesmente ir para a área de trabalho CMD e para o diretório de programação dinâmica Python. E eu vou rodar este código. Tão maior aumento da sub-sequência dot py. Então aqui temos um erro porque criamos um resultado variável e não podemos usá-lo em Python. Então, agora, se voltarmos e atualizarmos, como vocês podem ver aqui, como vocês podem ver aqui,vamos obter cinco como a subseqüência crescente mais longa dentro desta sub-sequência de inteiros. Agora, se quisermos ver toda a lista, isso é o que, o 1, 2, 3, 2, 4, 3 e 5. Podemos simplesmente retornar o máximo, apenas o aliado como, como é. Agora, se você voltar e executá-lo novamente, nós vamos obter esta lista 1, 2, 3, 2, 4, 3 e 5. Então, estas são a subsequência crescente real para cada índice dentro da nossa lista de entrada. Então eu não tinha 0 com os ingredientes mais longos. O músculo oblíquo é um, índice, um, é 23. E aqui nós temos dois porque nós, na posição específica, que é nós somos, nós temos que, a subseqüência crescente mais longa é 12 e seu comprimento é na verdade 2. Então é isso basicamente agora o que nós realmente fizemos no final é calcular o máximo desses, que é cinco, e retorná-lo como nosso resultado. Então é isso basicamente para este problema. Esta é a implementação da sub-sequência crescente mais longa usando Python. 42. Projeto: Ok, então, no último problema, nós resolvemos o comprimento da subseqüência crescente mais longa usando uma complexidade de tempo de O n quadrado, como você pode ver aqui. Então o que realmente fizemos foi encontrar o comprimento da subsequência mais longa dentro de uma lista de inteiros como este, e é o mais longo é 15, 7, 8, 10, e seu comprimento é na verdade 5. Agora, o que você supõe fazer é melhorar a hora da solução para encontrar uma maneira melhor em termos de complexidade do tempo. Então nossa complexidade de tempo é O n ao quadrado. Sua tarefa é melhorá-lo em o e login. Então, o que você precisa fazer é pensar sobre um método e implementado usando sua linguagem de programação favorita e melhorar a solução em termos de complexidade de tempo. Agora, tenha em mente ao lidar com esse problema, você pode sacrificar a complexidade do espaço para ter uma complexidade de tempo melhor. Então, por exemplo, se não estamos usando uma matriz ou se estamos usando uma lista, podemos usar mais. Você pode usar a matriz 2D, um HashMap ou qualquer coisa desse tipo, a fim de melhorar sua complexidade de tempo. Então, estamos nos concentrando na complexidade do tempo e ignorando o espaço por enquanto. Então é isso. Esta é a sua tarefa. Espero que goste. Pontuação, e não se esqueça de soltar seu projeto na seção do projeto. E boa sorte e aproveite. 43. Conclusão: Então, parabéns, você acabou de terminar este curso. Esta é apenas uma breve recapitulação sobre o que cobrimos nele. Então a primeira coisa que fizemos foi usar a sequência de Fibonacci para definir memorização e tabulação e aprender as diferenças entre eles. Então resolvemos alguns dos mais famosos algoritmos de programação dinâmica. E no começo desenhamos as árvores, suas IRAs ou matriz 2D ao lado do pseudocódigo que vamos usar. Depois disso, nós os implementamos usando nossos idiomas. Então, agora, apenas dicas rápidas. Sempre que você vendeu este tipo de problemas de programação dinâmica, você precisa resolvê-lo por um 100 sedento tentou chegar com a solução que funciona, talvez por recursão. E, claro, depois disso, você pode começar por otimizá-lo e chegar uma solução melhor usando memoização e tabulação. Então, com isso dito, este é o fim do nosso curso. Espero que tenha gostado. Finalmente, se você tiver alguma dúvida, sugestões ou melhorias, então eu posso fazer o discurso. Ou se você quiser que eu cubra problemas extras, por favor, pergunte na seção de perguntas e respostas. E seria ótimo deixar um comentário para que eu possa melhorar este curso. Então, obrigado por estar aqui e boa sorte na sua próxima viagem.