Programación dinámica: Java, JavaScript y Python

1. Introducción: Hola a todos y bienvenidos a este nuevo curso el cual se trata de programación dinámica. Mi nombre es 100 unidades y voy a ser tu instructor a lo largo de este curso. Entonces, en primer lugar, permítanme empezar mostrándoles el esquema con el esquema de este curso. Vamos a empezar definiendo la programación dinámica. Y vamos a aprender sobre dos de las técnicas más populares que suelen utilizarse dentro de este tema. El primero es la memorización, y el segundo es la tabulación. Y vamos a aprender sobre ellos usando la secuencia de Fibonacci. Vamos a resolver este problema usando tres métodos. El primero es usar la recursión generativa que todos conocemos. Y vamos a pasar a la memorización y la tabulación. Y vamos a ver las diferencias entre ellos. Y vamos a aprender cuándo y dónde usar cada uno de ellos. Después de eso, lo que vamos a hacer es resolver algunos de los ejercicios más famosos utilizando programación dinámica. Entonces lo primero que vamos a hacer es tratar de construir un árbol o tal vez una especie de matriz o una matriz 2D de este problema. Después de eso, vamos a intentar escribir un pseudocódigo que nos ayude a implementar este problema. Y por último, vamos a implementar realmente usando tres lenguajes, Java, JavaScript y Python. Por lo que al pasar por las secciones, puede notar que vamos a resolver un problema principal en cada sección. Y el problema contiene la explicación del problema junto al código o ejemplo de trabajo a través. Entonces vamos a tener un pseudocódigo que explique nuestra lógica y fórmulas. Y después de eso lo vamos a implementar usando los tres idiomas antes mencionados. También tenemos una característica adicional que es este sitio web. Creé este sitio web con el fin de que ejecutes tu código y lo probé. Entonces aquí tenemos algunos problemas que vamos a resolver. Y puedes seguir adelante y elegir uno de los problemas. Trata de resolverlo aquí antes de volver a la explicación video e implementación que tenemos y el discurso. Entonces eso dicho básicamente, este es el esquema o el esquema de nuestro curso. Espero que lo disfruten y nos vemos en el siguiente apartado. 2. Requisitos: De acuerdo, entonces antes de que empecemos, hay una lista de requisitos que debes descargar de acuerdo al idioma que vas a usar. Entonces, por ejemplo, si estás usando Java, pero necesitas descargar es Eclipse o algún tipo de IDE donde puedes ejecutar Java. Entonces por supuesto vas a necesitar descargar Java. Vas a dirigirte a Java SDK y ellos simplemente presionan y están de acuerdo y tal descarga gratuita. Y obtendrás tu versión más reciente. Si estás usando Python, por ejemplo, necesitas descargar Python. Y por supuesto, voy a descargar Visual Studio Code donde vamos a ejecutar nuestro código con Python y JavaScript. Por último, para JavaScript, vamos a usar Node.JS para ejecutarlo en nuestro servidor. Por lo que estos son los requisitos que necesitas. Voy a añadir los enlaces en la sección de descripción. Y espero que hayan disfrutado de esta clase. Entonces nos vemos en el siguiente apartado. 3. Sequence de Fibonacci: Muy bien, Así que hola y bienvenidos. Y este par de videos, vamos a contestar la pregunta de ¿qué es la programación dinámica? Entonces, empecemos con algo sencillo. Esa es la secuencia de Fibonacci. Y la secuencia de Fibonacci es en realidad una secuencia donde cada número es la suma de sus dos números anteriores. Por lo que nuestros casos base son en realidad los dos primeros números, es decir 01. Por lo que estos son los dos primeros números en la secuencia de Fibonacci. Y el resto de ellos son en realidad la suma de los números anteriores. Por ejemplo, si uno obtengo este número, es 0 más uno es uno. Entonces tenemos 1 más 1, 2, 1, 2, 3, 2 más 35, así sucesivamente y así sucesivamente. Entonces esta es la secuencia de Fibonacci. Ahora cada vez que queremos resolverlo, nuestro primer pensamiento entra en recursión. Ya que cada vez que queremos computar el número en una posición específica, necesitamos volver a los números anteriores. Entonces déjame solo escribir los índices aquí mismo. Entonces este es el índice 0, 1, 2, 3, 4, 5, 6, y 7. Ahora déjame dibujar un árbol donde vamos a representar estos números. Entonces supongamos que quiero computar el Fibonacci de cinco. Entonces para computar el Fibonacci de cinco, necesito computar el Fibonacci de cuatro y luego el Fibonacci de tres y luego sumarlos juntos. Ahora para conseguir este Fibonacci de cuatro, lo que en realidad debería hacer es computar el Fibonacci de tres y luego el Fibonacci de dos. Y aquí se aplica lo mismo. Por lo que quiero conseguir f de 2 y f de 1. Y aquí nos encontraremos para conseguir f de 1 y f de 0. Y recuerda que f de 1 y f de z son los casos base. Y siempre que lleguemos a este punto, en realidad deberíamos simplemente devolver estos dos valores que tenemos aquí mismo. Entonces aquí tenemos f de 1 también y f de 0. Y aquí se aplica lo mismo. Entonces sólo voy a escribir estos puntos. Entonces eso es todo básicamente ahora, si pensamos en la complejidad temporal de este algoritmo, tomará una forma exponencial, ya que como podemos ver, estamos calculando los mismos números una y otra vez. Entonces aquí tenemos f de 2, 2, y aquí tenemos f de 1, 1, y 1. Y en realidad los estás computando una y otra vez como podemos ver. Por lo que nuestra solución podría funcionar, o en realidad funciona para números pequeños, pero tomará mucho tiempo, podría tardar segundos, minutos o incluso horas en computar una secuencia de Fibonacci grande. Entonces, ¿qué código absoluto podría verse? Entonces déjame solo escribir el Fibonacci y debería ser igual a este código. Entonces lo primero que vamos a hacer es escribir nuestros casos base. Si n es igual a 0. Entonces si n está en el índice 0, simplemente deberíamos devolver este valor que es 0. Entonces simplemente voy a devolver 0 en este caso. Ahora si n es igual a 1, lo que deberíamos devolver como en realidad este valor en un índice específico uno, que en realidad es uno. Entonces simplemente voy a devolver uno. Ahora podemos empezar con nuestro caso base o lo siento, con nuestra recursión. Lo que necesitamos para regresar en realidad son los dos números anteriores. Entonces si estamos a Banaji de n, que es igual a cinco, deberíamos fingir a Fibonacci de cuatro más Fibonacci de tres. Entonces, ¿cómo hicimos eso? Simplemente llamamos a la función Fibonacci de n-minos-1. Y luego lo sumamos con el Fibonacci de n menos 2. Entonces eso es todo. Básicamente esto es para nuestro pseudocódigo. Ahora lo que voy a hacer es tomar el espíritu de Dios y realmente implementado usando Java. Ten en cuenta que solo vamos a usar Java con el propósito de visualizar complejidad del tiempo en este problema y el resto de tus problemas se presentarán en todos los idiomas, Java, JavaScript, y Python. Entonces para hacer eso, déjame simplemente dirigirme a Eclipse. Y lo que voy a hacer es escribir este código aquí. Por lo que f n es igual a 0. Voy a hacer es simplemente devolver 0. Ahora si n es igual a uno, voy a devolver uno. Y si estos no son los casos, lo que voy a hacer es simplemente regresar. Entonces voy a devolver Fibonacci de n menos 1 más Fibonacci de n menos dos. Ahora, después de eso, me voy, lo siento, me olvidé aquí. Ahora para probar esto, lo que voy a hacer es crear una función principal y llamar al Fibonacci de un número específico impreso, imprimir el Fibonacci de 7 en este caso. Como pueden ver, si sigo adelante y ejecuto este código aquí mismo. Pero en realidad voy a conseguir como P número 13. Y si vuelves aquí, podemos ver que este Fibonacci de este específico y X7 es en realidad 13. Por lo que nuestro código funciona correctamente. No obstante, si vuelvo ahora y probemos el Fibonacci 50. Y si ejecutamos este código el martes, algún tiempo para ser ejecutado ya que tenemos llamadas recursivas donde vamos a ejecutar el mismo código o ejecutar la misma función una y otra vez. Y tomará tal vez segundos o tal vez minutos en este caso. Por lo que necesitamos tener una mejor manera de solo obtener estas secuencias de Fibonacci o los resultados en este caso. Y aquí viene en programación dinámica. Entonces tenemos dos técnicas con las que vamos a presentar. El primero se llama memoización, y el segundo se llama tabulación. Y los vamos a presentar en el próximo par de videos. Entonces nos vemos. 4. Memorización: Muy bien, Así que encontramos la solución donde utilizamos recursión para resolver este problema de Fibonacci. No obstante, nos topamos con un problema por su complejidad temporal. Porque estamos ejecutando la misma función o llamando a la misma función una y otra vez. Entonces, ¿cómo nos enfrentamos a eso? Aquí viene la programación dinámica. Entonces la primera técnica que vamos a utilizar se llama memoización, que básicamente es solo para almacenar los valores que vamos a usar una y otra vez. Entonces para hacer eso, en lugar de solo llamar a f de 2 aquí una vez y aquí otra vez. Pero en realidad vamos a dos para resolver este f de dos la primera vez que lo vemos. Por lo que nuestro código va a funcionar de esta manera. Vamos a llamar a f de 5, 10. En este caso, lo llamará f de 4, 4, 3. No obstante, antes de llamar a esto, irá por aquí. Entonces el flujo de nuestro código en realidad está siendo f de 5, 4, 3, y luego vamos a ir hasta el 21, y estamos bien y luego vamos a ir todo el camino de vuelta aquí. Y como se puede ver ahí mismo. Entonces este es el flujo de nuestro código. Ahora lo que hemos hecho para básicamente hacer es almacenar todos estos valores cada vez o la primera vez que los vamos a ver. Y por supuesto, siempre que queramos usarlos de nuevo, sólo los vamos a sacar de nuestra memoria. Entonces para hacer eso, lo que realmente voy a agregar en este caso es una lista aquí. Entonces, déjame simplemente borrar esto. Y voy a cambiar los parámetros aquí mismo, de N a N y un recuerdo. Y en este caso, lo que realmente vamos a hacer es tomar este recuerdo y usarlo más tarde. Entonces antes de hacer todos estos, vamos a comprobar si el fibonacci de esta secuencia, y en realidad está almacenado dentro de nuestra memoria. Entonces, ¿cómo hacemos eso? Permítanme simplemente cambiar el color para que visualicemos los cambios. Entonces si la memoria en esta posición específica y no es igual a 0. Ahora recuerda que cada vez que creemos esta memoria, solo vamos a poner ceros y la posición de Annette y FDA, que está en n, no es igual a 0. Lo que realmente vamos a hacer es simplemente devolverlo tal como está. Entonces vamos a devolver la memoria en esta posición específica. Y ahora si este no es el caso, vamos a seguir con nuestro código como antes. No obstante, antes de devolver este de aquí, lo que realmente vamos a hacer es almacenarlo dentro de nuestra memoria. Porque recuerda que Fibonacci n es devuelto por esta cadera derecha. Entonces para hacer eso, simplemente lo voy a almacenar en la memoria en n y luego regresé. Entonces déjame hacer eso simplemente tomando todos estos y tal vez empujarlos a escuchar. Y lo que voy a hacer ahora es tomar esto y colocarlo aquí. Ahora, sigamos. Entonces en lugar de devolver este, y lo voy a hacer es simplemente ponerlos dentro de nuestra memoria y devolver la memoria real. Entonces déjame probarlo aquí. Tenemos memoria en n será igual a éste. Y por supuesto, después de eso, simplemente vamos a devolver la memoria en esta posición específica. Y entonces eso es todo ahora, en lugar de llamar a todas estas funciones una y otra vez, ¿quién sólo va a comprobar si están en este recuerdo? Si este es el caso, simplemente los vamos a devolver. Si este no es el caso, los vamos a computar y almacenarlos dentro la memoria por segunda vez, los vamos a usar. Por supuesto, funcionará correctamente. Ahora, sigamos adelante y usemos este pseudocódigo y nuestro Java. Entonces en lugar de solo conseguir n, me voy a llevar un recuerdo. Y por supuesto cuando llamamos aquí al nazi, también debemos devolver la memoria. No obstante, antes de devolverlo, lo que realmente deberíamos hacer es simplemente agregar una cola. Por lo que la memoria en n debe ser igual a ds, y por supuesto debemos encajar en la memoria. Y después de eso, Ahora, llamémoslo criterio. Entonces como puedes ver, este gran número tardó un tiempo en llegar y es negativo porque estábamos usando enteros. Entonces tal vez vamos a usar 24 ahora. No obstante, tenemos que incrementarlo. Entonces vamos a tener un nuevo extremo de tamaño 21 para usar dentro de pseudocódigo. Ahora si volvemos atrás y ejecutamos este código, como pueden ver, obtuvimos nuestro resultado que es 67, 65, que es, no nos tomamos mucho tiempo como antes. Entonces ahora déjame revisar el número 30. Y como podemos ver, por no descubierto, vamos a conseguir este gran número y este número que pudo no sólo haber computado usando la función recursiva original porque estamos llamando a las mismas funciones exactas una y otra vez. Entonces ahora lo que vamos a hacer es intentar un número muy grande como el 20000. En este caso, si seguimos adelante y lo ejecutamos, podemos ver que nos dieron un error. Y este error es en realidad StackOverflow. Por lo que nuestro código se ejecutará con celeridad. No obstante, cada vez que llamamos a estas funciones una y otra vez. Entonces si estamos en una posición específica donde tenemos 10 mil, vamos a llamar a diez mil novecientos mil novecientos noventa y nueve mil novecientos noventa y ocho todo el camino hasta el último que está en 0. Por lo que todas estas funciones de devolución de llamada o de devolución SysML van a ser o el o simplemente almacenado en una pila. Y es posible que nuestro personal no tome todos estos o quepa todos estos juntos. Entonces lo que vamos a hacer es usar otra técnica que se llama tabulación. Y también es una técnica de programación dinámica, y la vamos a ver en el siguiente video. 5. Tabla: De acuerdo, Entonces en el último video, usamos la memoización para resolver este problema de Fibonacci. No obstante, nos topamos con un problema en el que tuvimos un error de desbordamiento de pila porque estábamos usando demasiadas sentencias de retorno , devoluciones de llamada, y las estamos almacenando todas dentro de nuestra pila y no les cabía. Entonces ahora, lo que vamos a hacer es usar la tabulación para resolver este problema de Fibonacci. Ahora bien, si sabemos que necesitamos conseguir este f de cinco, y para conseguir este f de 5, necesitamos obtener f de cuatro, f de 2 y f de uno. Por lo que tiene sentido resolver todos estos de antemano y simplemente almacenarlos en una especie de lista de array o algo así. Y luego sólo regresa f de 5. Entonces lo que vamos a hacer es empezar desde abajo hasta el último elemento. Y a esto se le llama tabulación, que es básicamente programación dinámica de abajo hacia arriba. Y en realidad llamó a esto porque lo vamos a construir desde abajo, uno por 12, predicando nuestro propósito. Entonces lo que realmente vamos a hacer es empezar desde 0, llenar nuestra función, o a través de nuestro descanso, y luego devolver la última que necesitamos. Por lo tanto, permítanme borrar todo este pseudocódigo y escribirlo de nuevo con tabulación. Entonces voy a hacer en realidad es crear una función y será una función iterativa, así iterada. Y en este caso lo que vamos a hacer es tener un número y que vamos a regresar. Y en este caso, lo que voy a hacer es crear tal vez una lista o una matriz. Simplemente lo llamaré lista. Y será de tamaño y más uno. Y lo que vamos a hacer en realidad es llenar esta lista con estos valores aquí mismo. Por lo que la lista en el índice específico 0 debe ser igual a 0. Y entonces la lista en un índice específico 1 es igual a uno. Y entonces podemos empezar con un bucle for empezando en I igual a dos todo el camino hasta n. y cada vez dentro de esta lista vamos a almacenar ese índice específico I, el valor de la lista en i minos1, y el más en I menos dos. Entonces tomará una gran O de n. Entonces esta es la complejidad de tiempo de ejecución porque estamos recorriendo todos los elementos de 0 a n. Y siempre que lleguemos al último elemento que está en un índice específico, y podemos devolverlo. Por lo que después de terminar de todas estas, simplemente regresamos la lista en el puesto. Y en este caso, así que eso es todo básicamente ahora, en lugar de volver a llamar a todas y cada vez que necesitamos llamar a esto, por ejemplo, f al 99, 99, podemos simplemente almacenarlo en nuestra lista y finalmente, conseguirlo cuando queramos. Entonces en este caso, permítanme simplemente leer tipo esta función aquí mismo usando tabulación. Entonces en lugar de conseguir todos estos, lo que voy a hacer es simplemente crear una función y lo será. Y en lugar de almacenar ese parámetro, simplemente lo voy a escribir aquí mismo. Entonces voy a tener a la señora aquí mismo de talla n más uno. Y en este caso, lo que voy a hacer es almacenar en Mammoth 0 el valor de 0, la mamá de uno será uno. Y ahora podemos empezar con el bucle for, partiendo de yo igual a dos todo el camino. Y así incluido. Y por supuesto vamos a incrementarlo después de eso. Lo que voy a hacer es comenzar en esta posición específica en i, el valor de m en I menos 1, y agregarle el valor de n menos dos en este caso. Como podemos ver, si seguimos adelante y devolvemos el valor de y al final, lo que vamos a conseguir en realidad como el valor correcto de este 20000 aquí mismo. Entonces si ejecuto este código, voy a conseguir 93637285. Y esta es la secuencia Fibonacci correcta en un índice específico de 20000. Por lo que nos limitamos a deshacernos de los problemas de StackOverflow que solíamos tener usando la memoización y ya usamos la tabulación en esta solución. Entonces eso dicho básicamente para la memorización y tabulación, lo que vamos a hacer a continuación es realmente resolver algunos de los problemas de programación dinámica más famosos utilizando la memoización y la tabulación. Entonces lo que vamos a hacer es ver el problema, leerlo a través de él, y trabajar a través de un ejemplo de un tratado de resolverlo usando una mano. Y después de eso, vamos a crear o simplemente generar un pseudo código. Y esto nos ayudará a implementarlo en nuestros idiomas, Java, JavaScript, y Python. Por lo que el esquema de nuestros costos será el siguiente. Vamos a tener el problema que el pseudocódigo y luego la implementación. Entonces eso es todo, básicamente lo que este video te ve en el siguiente. 6. Número mínimo de las facturaciones para devolver una cantidad: De acuerdo, entonces en este video vamos a pasar por uno de los ejemplos más populares que suele resolverse con programación dinámica. Y el problema va así. Así que imagina que tienes una tienda y un cliente entra y ordena con $60 en comida. Ahora te entrega un billete de 100 dólares y en este caso vas a devolver los restos, eso son los 40 dólares. Entonces por ejemplo, supongamos que tenemos un $100 y él compra con 60 dólares y debe devolvérselo. Ahora, por el bien de este problema, supongamos que tenemos cuatro tipos de campanas. Entonces supongamos que tenemos el billete de $1. Yo los escribo aquí mismo. Entonces tenemos el olor y es el $1, tenemos el cinco dólares. También tenemos 10, y también tenemos el 25. Entonces eso es todo. Entonces tenemos estos cuatro tipos de campanas. Ahora bien, si queremos resolver este problema usando un algoritmo codicioso, probémoslo aquí mismo. Para este ejemplo, tenemos una devolución de 40 dólares. Y en este caso, el algoritmo codicioso va así. El primero que vamos a hacer es buscar la mayor factura posible con la que podamos pagar. Entonces en este caso, deberíamos devolver 40 dólares. Entonces déjame escribirlo aquí mismo. Entonces estos son los 40 dólares que debemos devolver. Ahora vamos a revisar junto a estos cuatro tipos, ¿cuál es la mayor cantidad que podemos extraer de este 40? En este caso, tenemos el 25, por lo que $40 menos 25. Por lo que utilizamos este 11 tiempo. Ahora vamos a tener 15. Y en este caso, también tenemos un 10 que es menor a 15, por lo que 15, podemos extraerlos. Por lo que utilizamos este 10 también una vez. Y esto nos dejará con cinco y luego se escapa. Por último, tenemos cinco menos cinco, que es igual a 0. Para resolver, también utilizamos este 5 una vez. Por lo que terminamos con 25 más 10 más 5. Y este caso, este algoritmo codicioso realmente funciona y nos da la solución más óptima, que es usar facturas de 25, 10 y 5 dólares. Ahora, imagina que también tenemos un billete de 20 dólares en lugar de sólo tener estos cuatro tipos. Así que déjame borrar todo esto y vamos a intentarlo de nuevo. Entonces si tengo aquí mismo otros billetes de 20 dólares, y probemos el algoritmo codicioso una vez más. En este caso, ahora ya tenemos dólares en mora que debemos devolver. Y en este caso, el algoritmo codicioso funcionará exactamente como antes. Por lo que vamos a buscar el cinturón más o el más grande que podamos extraer de estos $40 debe ser menor a estos $40. No obstante, tenemos 25. Entonces estamos bien. Nos vamos a quedar con 15. Y en este caso, si queremos trabajar con unos 20 dólares, no podemos porque ahora tenemos 15. Tenemos que buscar cualquier cosa que sea igual o menor a 15. Y este caso. Y así nos vamos a quedar con la misma cosa exacta que antes. Y esta claramente no es la solución óptima. Por lo que la solución óptima es simplemente utilizar los billetes de 20 dólares por dos. Entonces vamos a usar estos billetes de 20 dólares dos veces y vamos a conseguir los 40 dólares que necesitamos para volver al cliente. Y en este caso, como puedes ver, el algoritmo codicioso no funcionará. En realidad no será la solución óptima. Por lo que vamos a utilizar la programación dinámica en su lugar. Entonces déjame despejar todo esto y vamos a pasar por otro ejemplo usando el método de programación dinámica. ¿ Verdad? Entonces este es otro ejemplo. Entonces tenemos 7 dólares que debemos regresar y tenemos los 1, 3, y 4 cinturones. En este caso. Estas campanas constituyen las que dibujamos antes. Entonces no te preocupes por ello, se ajusta con ellos y se alistan. Y en este caso, lo que vamos a hacer es construir una matriz o una lista. Y vamos a hablar de ello en un segundo. Pero antes que nada, permítanme construir y esta matriz será redimensionada, este siete más uno. Entonces en este caso, sólo voy a dibujar siete. Todo bien aquí, así que 3, 4, 5, 6, 7. Y como dijimos, algunos más uno, que es un caso S, los índices serán 0, 1, 2, 3, 4, 5, 6, y 7. Por lo que como dijimos, tenemos ocho elementos en esta lista. Y lo que vamos a hacer es ir a través de esta lista de campanas una por una y comprobar la posible implementación de posible adición en esta cadera derecha. Entonces, en otras palabras, lo que vamos a hacer es comprobar, por ejemplo, si sólo tenemos un billete de 1 dólar, ¿qué va a pasar para estos aquí mismo? Entonces en este caso, probémoslo con la factura de 1 dólar. Entonces, por ejemplo, si tenemos este $1, pero ¿cuántas facturas necesitamos para constituir el 0? Y en este caso no necesitamos ningún construido, así que solo escribimos 0. Entonces esto es sólo un caso base. Ahora, supongamos que tenemos que devolver $1. ¿ Cuántos billetes de $1 necesitamos para devolver $1? Sólo necesitamos uno. Ahora, pasemos a la segunda. Entonces, por ejemplo, si tenemos, necesitamos devolver 2 dólares. Cuántos $1 factura haciéndolo para devolver estos $2 sólo necesitaría $1 facturas. Entonces en este caso, lo que estamos diciendo que necesitamos 1 factura para devolver la cantidad que es de 2 dólares. Entonces para que sea un poco más fácil, estos son el monto y estos son simplemente el número mínimo de facturas que debemos devolver en este caso. Entonces lo que estamos diciendo aquí es que sólo tenemos este billete de 1 dólar, y este es el número mínimo de billetes de 1 dólar que debemos devolver si queremos tener estos montos. Y bueno, sin pasar por todas estas, es lo mismo. Es bastante sencillo. Por lo que necesitamos facturas de 3 dólares para devolver una cantidad de tres. Necesitamos 4567. Entonces eso es todo. Básicamente esto es lo que necesitamos. Permítanme simplemente borrar esto y sigamos con ello. Entonces en este caso, acabamos de pasar por el $1 aquí mismo. Entonces lo que tenemos que hacer en este momento es comprobar los 3 dólares. Ahora supongamos que solo, no sólo tenemos la diabetes única. Tenemos el $1 así como el $3. Pero en este caso, lo que vamos a hacer es comprobar desde el principio. Entonces a 0, ¿cuántos billetes de dólar necesitaríamos para representar la cantidad 0? No necesitamos ninguna. Ahora, tres, cuántos billetes de 3 dólares necesitamos para representar uno podemos para evitar uno con billetes de 3 dólares. Entonces pasamos a dos. En este caso, vamos a revisar también y llegamos a presentar dos con billetes de 3 dólares. Entonces vamos a pasar a estos tres aquí mismo. Y en este caso nos preguntamos, ¿cuántos billetes de 3 dólares necesitamos para representar esta cantidad de 3 dólares? Y la respuesta es bastante directa. No necesitamos tres, sólo necesitamos uno. Ahora, lo que estamos diciendo aquí es que necesitamos un billete de tres dólares para representar esta cantidad. Y pasemos a la cuarta. Entonces, ¿cuántos bits necesitamos para representar a estos cuatro? Y en realidad sólo necesitamos facturas, esa es la factura de $3 más la de $1 para presentar esto. Entonces no necesitamos cinturones, sólo necesitamos y este caso, son tres más uno. Entonces, ¿qué hacemos? Cancelamos esto y sustituimos aquí también. Y en cuanto al cinco dólares, ¿cuántos bits necesitamos para presentar la cantidad de 5? Y en realidad necesitamos tres bits. Esa es la factura de $3 Más una más $1 factura entonces es de 3 años aquí mismo. Ahora en cuanto al sexo, y ¿cuántos pedacitos necesitamos para presentar el sexo? En realidad necesitamos, sólo para recordar que tres, tenemos tantos como queramos. Por lo que en lugar de representarlo con seis unos, podemos presentarlo, representó con dos treses. En este caso, sólo necesitamos pasar ahora a la séptima. Y en este caso, lo que vamos a hacer es usar $3.3 nacimientos, lo siento. Y eso son billetes de 2 a 3 dólares y 1 billete de 1 dólar. Y en este caso vamos a terminar con algo así. Tenemos 01212323. Ahora, pasemos a la final. Es decir, representar al cuarto. Por lo que ahora también tenemos el Cinturón de $4. En este caso, tenemos los números de 1, 3 y 4 dólares todos a la vez y podemos usarlos todos en este caso. Ahora lo que vamos a hacer es omitir todos estos hasta los cuatro porque no podemos representar ninguna de la menor cantidad, 0, 1, 2 y 3. Y vamos a ir todo el camino hasta el cuarto. Y en este caso nos vamos a preguntar como antes, ¿cuántos billetes de 4 dólares necesitamos para representar monto en dólares por defecto? Y la respuesta es una. Entonces, ¿cuántos? Para billetes de dólar o cualquier campanilla, necesitamos presentar los cinco y la respuesta es bastante sencilla. Es decir, necesitamos factura de $4 más $1 factura. Y en este caso, hay dos. Y lo mismo vale para esto. Entonces aquí tenemos dos. Y por supuesto que vamos a revisar. Entonces ahora tenemos también cuatro. Por lo que cuatro más uno más uno es igual a 6 dólares. Entonces en este caso utilizamos tres cinturones, y esto no es óptimo. Ya tenemos una solución que funciona mejor con dos cinturones. Eso son los billetes de 2 dólares 3. Si tenemos tres o dos, vamos a elegir quedarnos con estos dos. Y por último, si nos vamos a pedir el último, ese es el $7. En este caso, vamos a necesitar 4 $3. Por lo que puede representarlo con tres en lugar a un conjunto de tres. Entonces eso es todo. Básicamente así es como llegamos con una respuesta finita. Es decir, podemos representar esta cantidad usando sólo dos campanas. Entonces eso es todo por la idea del trabajo a través de ahora. Pequeño pseudocódigo para ver exactamente qué está pasando y cómo podemos pensarlo de esa manera. Entonces, ¿qué dijimos cuando estábamos a las tres o cuatro? Dijimos que podemos saltarnos todos estos, 43 ya que son más pequeños que tres. Y denotemos esto en realidad por las campanas aquí mismo. Entonces estas son las creencias que tenemos. Estos son el número mínimo y este es el monto. Ahora en este caso, si la campana, por lo que las campanas son 1, 3, y 4, por lo que campana significa ya sea 12 o tres. Y en este caso, si este proyecto de ley es menor o igual a la cantidad que nosotros, que estamos buscando. Lo que vamos a hacer es actualizar el número mínimo. Y si volvemos a nuestro ejemplo, podemos ver que el número mínimo debe ser una de dos cosas. Ese es éste de aquí o necesitamos actualizarlo como aquí. Entonces por ejemplo, 012, no necesitábamos actualizarlos. Por lo que enviaron los mismos o los actualizados, es decir 1, 2, 2, y 2, como podemos ver arriba. Y en este caso, ¿cómo conseguimos estos números actualizados? Entonces si miramos a los cuatro este caso y estos cuatro proyectos de ley, lo que realmente hicimos es que tomamos este cuatro de cada una de las cantidades que nosotros. Entonces pensémoslo un segundo. Entonces por ejemplo, en este caso, cuando teníamos este cinco aquí mismo, así que tenemos 5 dólares para regresar. Y este caso lo que hicimos es que restamos 4 dólares de aquí. Entonces tenemos 5 menos 4, así que aún tenemos $1. Y este caso, lo que vamos a hacer es mirar el monto de $1 aquí mismo en la mesa. Esta es la cantidad de $1. Y en este caso, lo que hicimos es justo que lleváramos este número mínimo justo aquí y sumamos a la cantidad de facturas, ¿cuántos billetes de 4 dólares usamos? ¿ Aquí? Acabamos de usar un billete. Ese es el $4 y aún tenemos que devolver la cantidad sobrante que es de $1. En este caso, el conjunto de datos aquí mismo. Tenemos el de aquí mismo. Entonces esta es la cantidad que debemos devolver. Por lo que 1, 4 billetes de dólar más 1 billete de $1. Y este caso, la respuesta es dos, como podemos ver, que es usar esta fórmula. Entonces lo que vamos a hacer después de eso es que vamos a escribir pseudocódigo para esto en realidad. Y luego lo vamos a implementar en Java. 7. Pseudo-Code del problema: Muy bien, entonces ahora que realmente sabemos cómo funciona este algoritmo, y pasamos por un ejemplo real. Ya conocemos la idea detrás de ella. Ahora, intentemos llegar a un pseudocódigo que nos ayude a nosotros y a nuestra escritura de código en un poco. Entonces si queremos pasar por el pseudocódigo, como dijimos, la factura fuerte es menor que la cantidad. En este caso, lo que vamos a hacer es que vamos a actualizar este número mínimo aquí mismo. Entonces lo que vamos a hacer es pasar por toda esta lista para cada uno de estos cinturones. Entonces vamos a tener dos para bucles anidados uno en el otro. El primero es será, será el bucle de facturas de facturas, y el segundo será el número mínimo que vamos a actualizar cada y cada vez que pasemos por el número. Y en este caso, lo que vamos a hacer es actualizar el número mínimo cada vez que la factura sea menor o igual al monto. En este caso, por ejemplo, tuvimos para el examen 4, 3 proyecto de ley. Ya tenemos este 012 y hay más pequeños que tres, por lo que no necesitamos actualizarlos. Empezamos con la cantidad que es más grande o igual, este cinturón aquí mismo. Entonces como dijimos, partimos desde aquí todo el camino que el final para todos y cada uno de los cinturones justo aquí. Entonces lo que vamos a hacer es comprobar el mínimo entre dos cosas. Como dijimos, el mínimo entre este número justo aquí y el número real que podemos actualizar. Entonces lo que tenemos que hacer es cambiar el número mínimo. actualizarse el número mínimo a esta cantidad específica. En este caso, será igual a 2, una de las cosas que es la mínima entre ellas. Por lo que será igual a los hombres entre lo primero y lo otro. Y como dijimos, lo primero es la cantidad real que ya tenemos. Por lo que será el número mínimo de la cantidad. Entonces es lo mismo que antes, o necesitamos tener uno más pequeño. Entonces, lo que realmente estamos haciendo es simplemente comprobar si nuestra nueva solución es mejor que la otra. Entonces como dijimos aquí, ya tenemos esta solución 01234567, y están representados con este billete de 1 dólar. No obstante, por el monto de tres, por ejemplo, podemos representarlo con la cantidad de 3, 0, el uno de los Tres Dólares Bill. En este caso, quitamos estas tres campanas y acabamos de sumar una con cinturón es de $3. Y en este caso, es mucho mejor y más eficiente usar billete de 13 dólares en lugar de 3 billetes de $1. Entonces lo que hicimos en realidad aquí mismo es que tomamos esta cantidad tres y justo, solo atacó desde aquí el proyecto de ley S3. Por lo que nos fuimos con 0. Y este caso nos fuimos todo el camino atrás la cantidad de 0 y nos fijamos en este número mínimo y en este caso 0. Y entonces lo que realmente hicimos es que solo usamos una pastilla aquí mismo. Y luego comprobamos por esta cantidad 0. Y en realidad usamos una campana 0 justo aquí. Y esto nos dejará con un antígeno de campana. Entonces por eso tenemos tres aquí mismo. Y lo mismo vale para este seis de aquí. Lo que realmente hicimos es que usamos 2 billetes de 3 dólares. Entonces nosotros esta x justo aquí, menos dos veces tres, que es igual a 0. Por lo que este tres se usa dos veces. Entonces usa tuplas. Y fuimos todo el camino de regreso al número mínimo o al monto de 0 y comprobamos que es número mínimo, que en realidad es 0. Entonces nosotros, usamos 02 menos 0 a más 0, lo siento, es igual a dos. Por lo que terminamos teniendo que golpearlo campana. Entonces este es el trabajo real a través. Entonces si quieres pensarlo de otra manera, para este seis cinturones justo aquí, lo que realmente hicimos es que dijimos que o billetes de 6 $1 o algo más usando estos tres, Dahlberg aquí mismo. Y en este caso, lo que realmente hicimos es que acabamos de tomar esta factura de 3 dólares. Entonces son seis menos tres. Y este caso, terminamos con tres, ¿verdad? Entonces esto, sólo usamos un billete de aquí. Y luego revisamos por la cantidad de tres, que es justo aquí. Cuántos, cuál es el número mínimo en este caso que necesitamos terminar con un devolver todos los montos que tenemos en este caso para tres, podemos ver claramente que es uno. Y así es como conseguimos una campana más 1, que es igual a dos billetes. Entonces esto es todo. Esta es una idea general. Si tenemos multiplicación en este caso, podemos usar esto directamente. No obstante, este es el camino real. Entonces déjame, déjame solo borrar estos y Estamos bien. Podemos continuar. Entonces aquí nosotros Sr. bueno, lo siento. Entonces aquí tenemos a Bill. Entonces si el proyecto de ley es menor que mount, como dijimos antes, necesitamos actualizar el número mínimo, que será igual o igual al mismo o al, agregamos uno, como dijimos. Por lo que es una factura más el número mínimo en la cantidad menos la factura. Eso tiene sentido. Entonces déjame escribirlo y luego te lo explicaré. Tan mínimo entre la cantidad real que tenemos menos el cinturón que almohadillamos que tenemos. Entonces eso es todo básicamente. Ahora si queremos pasar por este ejemplo usando esta fórmula, Sigamos adelante y hagámoslo. Y por supuesto, no voy a pasar por todo el ejemplo. Yo sólo voy a tomar situaciones específicas. Entonces, por ejemplo, supongamos que estamos en este cinco aquí mismo. Y sólo tenemos los 3 billetes de $1 que podemos representar este 51 y este caso lo que vamos a hacer. Entonces estamos en esta etapa justo aquí. Y vamos a pensar a través del proceso. Tenemos estos billetes de 3 dólares. Y en este caso, lo que vamos a hacer es que vamos a sumar uno. Entonces es o el mínimo entre dos cosas, ¿verdad? Entonces es o esta de aquí, que son cinco. No lo ves ahora mismo porque simplemente lo quitamos antes, pero está justo aquí. Y esto son cinco. Entonces son o cinco o algo más. Y usar esta fórmula es uno más la cantidad mínima, mínima entre cantidad, mente, espíritu. Y en este caso, lo que vamos a hacer es, así que son o cinco o uno, más. Vamos a ir todo el camino al número mínimo de cantidad. En este caso, la cantidad es de cinco. El cupido constructor es de tres. Por lo que el número mínimo suma 5 menos 3, que es el número mínimo a dos. En este caso, vamos a ver esto. Y como podemos ver, tenemos el número mínimo en este caso es de dos. Entonces 1 más 2, que es 3. Por lo que el mínimo entre 53 es en realidad tres. Y esto es lo que tenemos aquí mismo, es el número tres. Por lo que podemos representar los billetes de 5 dólares con un billete de tres dólares y a billetes de 1 dólar. Entonces eso es todo. Es así como podemos usar esta fórmula. Y si fue pruébalo por última vez, podemos probarlo para éste aquí mismo. Entonces antes de esto, teníamos un tres aquí. Y en este caso lo que realmente estamos haciendo es que vamos a sumar uno por billete de dólar. Entonces permítanme simplemente borrar esto y sigamos. Entonces el mínimo entre dos cosas, el monto real que tenemos o el número mínimo real que ya tenemos, o necesitamos actualizarlo sumando uno por billete de dólar. Entonces tiene uno. Plus. Pasamos al número mínimo en la cantidad que es 7 menos wL, que es 4. Por lo que 7 menos 4 es 3. Entonces vamos a ir todo el camino a estos tres aquí mismo. Vamos a ver el número mínimo. En este caso, es uno. Vamos a sumar uno justo aquí, así que es el mínimo entre 32. Entonces la respuesta es dos. Eso es todo. Básicamente así es como podemos usar este pseudocódigo para ayudarnos a escribir nuestro código en este momento, esta es la parte más difícil. Simplemente se nos ocurre este método real o algoritmo real o idea que podemos usar para resolver el problema específico. Y usando este método, pudimos llegar a la solución más óptima. A diferencia del algoritmo codicioso que teníamos al principio. En este caso, como dijimos, podemos representar estos 7 dólares construidos con uno para billetes de dólar y 13 crédulos. Y este caso, la respuesta es dos. Y con eso dicho, este es el final del pseudo código aquí mismo. Y el siguiente video vamos a implementar nuestra función usando Java. Entonces nos vemos. 8. Aplicación del número mínimo Java: De acuerdo, entonces ahora que sabemos cómo funciona exactamente este algoritmo, y escribimos el pseudocódigo que nos va a ayudar en nuestro código caminar. Ahora mismo. Podemos empezar con la codificación. Y en realidad este es uno de los más importantes, pero siempre debes empezar con esto, algo así. Para que puedas escribir tu código o escribir tus pensamientos en un pedazo de papel y tal vez dibujar algunas cosas. En este caso, dibujamos esta lista y actualizamos cada vez que pasamos por una campana. Por lo que había sido una necesidad de trabajar con un bolígrafo y papel y no sólo visualizar todas las cosas que hay dentro de tu cabeza. Especialmente en programación dinámica. Porque visualizar algo o tenías trabajos usualmente fusiona problemas más simples. No obstante, en algunos problemas profundos o complejos, siempre se necesita usar un bolígrafo y papel. Y este caso, vamos a nuestro Eclipse. Y en este caso lo que vamos a hacer es empezar con la creación de la función. Entonces simplemente, solo necesitamos Min devuelve el número mínimo de cambio, que es un entero y un número mínimo de función vacío, en este caso, lo que vamos a tomarlo, la cantidad que regresará y se denota por N. Y cuántos o el tipo de cinturones que tenemos. En este caso, les vamos a nombrar campanas. Entonces vamos a abrirla y vamos a empezar con eso implementado. Entonces lo primero que vamos a hacer es crear esta lista de la que hablamos antes, y este es el número mínimo. Entonces para crearlo, simplemente crearé una lista de números mínimos. Y en realidad es contradice el, es lo mismo que el método, ¿no? Cuatro, tan íntimos de manera diferente. Y en este caso, este será el tamaño, el número o la cantidad de más uno, como dijimos. Y lo que vamos a hacer es al principio llenarlo con el máximo valor que podamos. Entonces vamos a usar matrices que sintieron. Y lo que vamos a hacer es llenar estas campanas con entero, ese valor máximo. Es así como podemos almacenar el máximo de valor entero aquí mismo. Y parece que necesitamos importar matrices. Por lo que sólo intentamos el espacio de contraste, golpeamos Enter, y sólo se lo llevará justo aquí. Ahora bien, esta zona, bueno que aún no devolvimos el entero, pero podemos manejarlo más tarde. Pero por ahora, lo que vamos a hacer es recordar que siempre queremos empezar con cantidad de 0. Por lo que el número mínimo debe ser 0. En este caso, lo que vamos a hacer es almacenar y el, lo siento, no es dobles es el número mínimo aquí mismo. Y vamos a empezar en número mínimo en 0, vamos a almacenar 0. Entonces este es el primer paso. Ahora vamos a pasar por todos los datos reales. Entonces lo que vamos a hacer es pasar por el autobús y dentro de cada uno, bueno, vamos a pasar por la cantidad en este caso. Tan int igual a 0 todo el camino a las campanas, esa longitud y luego actualizada. Ahora, el segundo será j igual a 0. Entonces J es menor que el número mínimo. Lo siento. Por lo que aquí agregué S por error. Y ahora estamos bien. Por lo que vamos a ir todo el camino al número mínimo de esa longitud y luego actualizado. Ahora, lo que vamos a hacer es comprobar si la campana es menor que la cantidad. Entonces, ¿cómo se hace eso? Simplemente comprobamos si las campanas en yo son menos que algo, que es la cantidad. Y en este caso, la cantidad es en realidad el índice. Como podemos ver, la cantidad es el índice de esta matriz de número mínimo o menos. Entonces es, si es menor o igual a esta cantidad, vamos a hacer algo sin nada. Vamos a, no vamos a hacer nada. En este caso. Lo que vamos a hacer es tomar la diferencia entre esta cantidad y la campana. Por lo que podemos decir que este j es el monto y las facturas en ISB campana real. Por lo que la diferencia será j menos sátira de cinturón. Y también queremos calcular la campana en este caso. Entonces voy a denotar por tal vez podría ser el número mínimo en este caso, nuevo, acabo de denotar por B. Y lo que vamos a hacer es agregar este más el monto o el número mínimo. Esta diferencia. Entonces lo que hicimos en realidad aquí es que computamos la fórmula. En la fórmula se dice que es el número mínimo. Y lo mínimo. Este es el nuevo actualizado. Será uno más esto aquí mismo. Y cómo computamos esto es que en realidad tomamos el número mínimo y la cantidad menos campana y le golpea. Por lo que 1 más 1 más el número mínimo. Entonces así es como, este es el número mínimo en monto menos la factura. Y computamos la diferencia justo en la línea anterior. En este caso, conseguimos el que podría actualizarse. Entonces en este caso lo que vamos a hacer es regresar. Apenas dijo que cinturones a voy a ser las matemáticas, pero los hombres. Entonces es una de dos cosas. Es el yo lo siento, el número mínimo en I y j Lo siento. Y será una de dos cosas. Será o lo mismo que antes y, o el BI que acabamos de crear antes. Y este caso, podemos actualizar estos números mínimos fácilmente. Entonces lo que hicimos en realidad es que tomamos la diferencia entre el monto y la factura, computamos que el número mínimo, solo computamos esta fórmula y conseguimos esto aquí mismo. Entonces dijimos que el número mínimo en esta cantidad debe ser igual al número mínimo en este alrededor o uno más el número mínimo de cantidad 2012. Y este caso, lo tenemos justo aquí, lo actualizamos. Entonces es o el mismo o el que es TBI. Ahora, lo que vamos a hacer es comprobar si el número mínimo al final o en sí. Por lo que a la cantidad no es igual al valor de Emax. Y te vas a decir por qué en un segundo. Vamos a devolver número mínimo y de lo contrario regresar menos uno. Entonces lo que realmente hicimos aquí es que revisamos, en realidad podemos hacer o devolver esta cantidad. En este caso, si podemos obtener ese último valor no debería ser el valor máximo. Debe ser un número natural. Y si este es el caso, acabamos de devolver este número. Y si no, vamos a regresar minús1, mismo que no podemos calcular o no podemos tener este retorno con esto, esta estrategia de proyecto de ley. Y un ejemplo de esto es imaginar que necesitamos devolver una cantidad de $5 o $5 y sólo tenemos 78 dobles. En este caso, no podemos devolver cinco porque sólo tenemos 78. Entonces es por eso que este siempre será valor máximo y no podemos devolver la cantidad, por lo que solo regresamos menos uno. Entonces esa es la implementación. Creo que es bastante sencillo después de toda la explicación que hicimos aquí mismo y caminar. Y eso es todo para este video. Nos vemos en el siguiente. 9. Implementación de número mínimo: De acuerdo, Entonces en este video vamos a implementar nuestra función o el pseudocódigo que creamos antes usando JavaScript. Entonces, sin más preámbulos, vamos a meternos en ello. El primero que voy a hacer es crear el nombre de la función al mínimo cambio. Y en este caso tomará y facturará como parámetros. Abrámoslo. Y en este caso, lo que vamos a hacer es crear una matriz en JavaScript. Podemos hacer eso. Démosle un nombre. Démosle un nombre. En realidad la cantidad. Y lo que no queremos hacer es tomar esta cantidad. Y por supuesto vamos a pasar por todas estas en un rato. Pero por ahora, lo que vamos a hacer es crearlo como una matriz de un plus 1. Y lo vamos a llenar de infinito. Entonces eso es todo, básicamente esto, cómo podemos crear una matriz en JavaScript. Ahora lo que vamos a hacer es actualizar esta cantidad en la primera debe ser igual a 0. Entonces si volvemos a este, podemos ver que esta cantidad debe ser igual a 0. En realidad, digámoslo números mínimos, ya que hicimos eso aquí, número mínimo. Entonces vamos a solo, oiría número mínimo. Aquí se aplica lo mismo. Ahora lo que vamos a hacer es crear nuestro for loop. Entonces lo primero que vamos a crear es el for loop para las campanas. Entonces lo que vamos a hacer es crear, construir y campanas, campanas, luego abrirla. Ahora, el segundo será por el número mínimo real. Y vamos a denotar estos índices por cantidad, como dijimos aquí mismo. Entonces lo vamos a crear aquí para el laboratorio. Importe igual a 0, entonces la cantidad debe ser menor que el número, número mínimo esa longitud. Y entonces por supuesto, vamos a incrementar la cantidad. Ahora vamos a abrirla y ahora podemos empezar con nuestro código real. Simplemente vamos a escribir el pseudocódigo que escribimos antes. Entonces dice que si el monto es mayor o igual a la factura, necesitamos hacer algo. En este caso, lo que vamos a hacer es actualizar el número mínimo, que será igual, debe ser en cantidad para ser igual al mínimo entre dos cosas. Entonces vamos a usar los hombres métodos. Y este mínimo será el número de número mínimo de cantidad y el número mínimo de cantidad menos la factura. Ahora lo que vamos a hacer, claro que aquí tenemos que sumar uno. Por lo que es el número mínimo de cantidad menos p más 1. Y en este caso, terminamos en realidad con esta función. Es así como podemos implementarlo usando JavaScript con este pseudocódigo que creamos anteriormente, con solo usar lo importado destinado a tomar el mínimo entre estas dos cosas. Y por supuesto lo llenaremos de infinito. Y que no se olvide de llenar el primero con 0, ya que es como el caso base justo aquí. Ahora lo que vamos a hacer es simplemente devolverlos aquí mismo. Por lo tanto, ten en cuenta que si esta función funciona correctamente, debería actualizar la última. No obstante, a veces podemos tener el infinito al final. Y en este caso, si tienes infinito, esto significa que no resolvimos el problema, no hay una solución adecuada. Entonces permítanme darles un ejemplo para tal cosa que supongamos que tenemos el cinco dólares para representar y también tenemos 678. En este caso, no hay una solución adecuada y este último infinito no se actualizará ya que $5 no se pueden representar con facturas de 67 ni tampoco de $8. Entonces lo que vamos a hacer es comprobar si este último es igual al infinito, vamos a regresar minús1. De lo contrario, vamos a devolver el número mínimo real que obtuvimos. Entonces ahora, si realmente regresamos esto, déjame simplemente devolverlo aquí mismo para que devuelva el número mínimo en, y lo que hemos hecho para conseguir un simplemente el último de la lista. Entonces esta es la lista que vamos a conseguir 0, 1, 2, 1, 1, 2, 2, 2. Y vamos a conseguir el número mínimo. Ahora, para que quede más claro, principio voy a devolver toda la lista y luego vamos a discutirla. Por lo que la variable n será igual a realmente los datos reales aquí mismo, que es siete. Y el último sería 1, 3, 4, así e igual a siete. Y la lista será igual a la lista 134. Y en este caso, lo que vamos a hacer es llamar a esta función de cambio mínimo con un y facturas. Y por supuesto vamos a iniciar sesión. Entonces console.log y suerte esta función. Ahora si volvemos aquí. Y vamos a JavaScript, programación dinámica. Y lo que vamos a hacer es simplemente usar hombres de nodo, cambiar eso JS y vamos a conseguir 0, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, que es exactamente lo mismo que generamos antes manualmente. Hacer ahora es devolver el último usando el número mínimo en. Y ahora si regresamos y grandiosos otra vez, vamos a conseguir dos como el número mínimo de cambios que necesitamos para presentar un número específico. No obstante, si por ejemplo, no tenemos esto. Supongamos que tenemos cinco. En este caso. Supongamos que tenemos 678 como cinturones. Lo que vamos a conseguir es en realidad infinito y esta no es una respuesta correcta. Tenemos que regresar menos uno. En este caso, simplemente necesitamos comprobar si el número mínimo en n es igual al infinito. Ahora este es el caso. Vamos a actualizarlo a menos 1. Entonces hay múltiples maneras. Entonces, por ejemplo, una forma de hacer como si este número mínimo fuera igual al infinito, pero no lo hacemos es simplemente regresar o actualizar. Entonces si es igual al infinito, vamos a, lo siento, necesitamos agregar los corchetes para que el número mínimo en n sea igual al infinito. Vamos a actualizarlo en menos 1. Ahora si volvemos atrás y golpeamos refresco, vamos a conseguir menos 17 f infinito. Otra forma de hacerlo es simplemente comprobar junto a la declaración de retorno. Entonces para hacer eso, simplemente comprobamos si este número mínimo es igual al infinito. Si este es el caso, tenemos que hacer algo. Y para ello, simplemente escribimos este signo de interrogación y luego tenemos dos opciones. Por lo que esta afirmación está satisfecha. La primera opción será, por lo que se ve algo así. Entonces si esta ecuación está satisfecha, si devuelve verdadera, vamos a conseguir esta opción. De lo contrario vamos a conseguir el segundo. Entonces si esto es cierto, pero lo vamos a hacer es regresar minús1. De lo contrario, vamos a devolver el número mínimo en Penn. Y vamos a revisarlo de nuevo. Si volvemos a correr, nos vamos a poner minús1 como antes. Ahora, por ejemplo, si aquí tenemos esto como bronceado, y volvamos a volver a ejecutarlo. Y por supuesto, no debería ser, debería ser múltiplo de seis, por ejemplo. Ahora, si volvemos atrás y corremos, vamos a conseguir dos como el número mínimo de cambios que podemos tener usando este 12 y estas facturas como monto. Entonces eso es todo básicamente para esta implementación. Es así como podemos implementarlo en JavaScript. Dicho esto, este es el final de este video. Nos vemos en el siguiente. 10. Aplicación del número mínimo Python: De acuerdo, Entonces en este video, vamos a hacer es crear la función Python para nuestro pseudocódigo que se nos ocurrió antes. Entonces permítanme sólo agregar unas cosas justo aquí porque el borrado. Entonces lo que vamos a hacer es determinar la función mínima de ésta aquí mismo. Entonces déjame solo hacer más grande. Entonces tenemos 7 dólares y los cambios o más profundos que tenemos son 1, 3, y 4. Entonces para hacer eso, Empecemos con definir nuestros parámetros de inmediato en Python. Por lo que n igual a siete. Y tenemos esta lista que es 134. Y éstos representarán dels de jabón de las personas iguales a 1, 3, 4. Ahora podemos empezar con nuestra función. Entonces lo que vamos a hacer es al principio, necesitamos crear esta lista de números mínimos y debe inicializarse a infinito. Y después de eso, lo que vamos a hacer es agregarla o modificarla cada vez que pasemos por cada uno de estos elementos. Entonces lo que vamos a hacer al principio es crear la lista real simplemente agregándole o nombrándole número mínimo. Y será igual a un menos que en este caso, lo que vamos a hacer es llenarlo con él. Y cómo podemos hacer eso, simplemente podemos pasar por un bucle for en rango de n más uno y luego llenarlo, llenar el número mínimo que vamos a anexar a él. Flotar, indicando que esto es un infinito. Por lo que ahora un libre ir adelante e imprimirlo. Eso vamos a ver. Entonces si sigo adelante e imprimo éste, vamos a sacar estos infinitos como los elementos de esta lista. Ahora, para empezar, volvamos aquí mismo y veamos nuestra función, nuestro, nuestro pseudocódigo. Ahora recuerda que necesitamos éste, que es el primero que será igual a 0. Entonces, antes de hacer algo, hagámoslo igual a 0. Por lo que número mínimo a 0 para ser igual a 0. Ahora podemos pasar por nuestro código, así que déjame volver a ejecutarlo aquí mismo. Y como puedes ver, la primera es 0 y todas las demás son infinitas. Entonces lo que vamos a hacer ahora es pasar por 24 bucles anidados netos. Y mientras hacemos eso vamos a pasar por todas estas y luego actualizarlas todas. Entonces déjame solo crear así para Bell y cinturones, vamos a empezar con esos y luego vamos a ir al número mínimo. Entonces para hacer eso, simplemente podemos crear un segundo for loop usando un rango de la longitud de este número. Entonces es por la cantidad y rango de la longitud de esta lista real que creamos. Es el número mínimo. Y lo que vamos a hacer al principio es comprobar si el monto es mayor o igual a la factura. En este caso, si este es el caso, necesitamos actualizarlo. Y es una de dos cosas según nuestras fórmulas. Es el mínimo entre la cantidad mínima real y o uno más el número mínimo a la cantidad menos derrame. Entonces déjenme simplemente implementado aquí mismo. ¿ Cómo hacemos eso? Por lo que es número mínimo en la cantidad debe ser igual a dos cosas. El mínimo entre la cantidad número mínimo y el número mínimo 1 más el número mínimo en cantidad menos el, eso es todo. Básicamente, así es como podemos implementarlo. Ahora si volvemos atrás y vamos a golpear refrescar y ejecutar de nuevo este código. Como se puede ver, tenemos 0, 1, 2, 1, 1, 2, 2, 2. Y si lo miramos aquí, tenemos 0, 1, 2, 1, 1, 2, 2, 2. Entonces es exactamente el mismo resultado. Ahora ten en cuenta que esto no es lo que realmente necesitamos. La solución real de este problema es conseguir el último aquí mismo. Entonces vamos a devolver el último de aquí. Ahora, una cosa a la que debemos prestar atención es que tal vez algunas, no existe tal combinación que nos permita obtener el número específico. Entonces supongamos que tenemos los $5 y todo el denominador, todo lo mejor que tenemos, nuestro 678. Por lo que en este caso podemos representar a cinco usando cualquiera de estos proyectos de ley. Por lo que la respuesta se mantendrá infinito. Ahora en este caso, si la respuesta es infinito, no regresamos infinito, sólo regresamos menos uno, lo que indica que no hay solución para tal problema. En este caso, necesitamos prestar atención y asegurarnos de que obtenemos este caso de borde. Entonces, ¿cómo hacemos eso? Simplemente podemos crear una declaración if si el número de monedas. Entonces si el número mínimo es la cantidad, o tal vez si el número mínimo en el último, que es n, es igual al infinito. Lo que vamos a hacer es dejarme sólo tratar de fluir probado aquí. Y si esto es igual a este número, lo que vamos a hacer es devolver minús1, minús1. De lo contrario, vamos a imprimir el número exacto, número mínimo en. Y así es. Básicamente así es como podemos hacerlo. Ahora si volvemos atrás, pulsamos refrescar, y ejecutamos de nuevo este código, creo que tenemos una sangría no coincide con la otra. Muy bien, así que vamos a arreglarlo muy rápido. Vamos a hacer es hacerlo así. Y ahora creo que estamos bien Si volvemos, vuelve a ejecutarlo. Y la respuesta serían dos. Ahora en este caso, si tenemos el ejemplo que dijimos antes, tenemos 6, 7, y 8. Si volvemos atrás y refrescamos, vamos a conseguir menos uno, lo que indica que no hay forma de obtener esta cantidad usando estos tres tipos de facturas porque son mayores a cinco. Entonces eso es todo básicamente para este problema, es como podemos ser atendidos con Python. Dicho esto, este es el final de este video. Nos vemos en el siguiente. 11. Número de formas para devolver una cantidad: Está bien, entonces en este ejemplo, se va a pasar por otro problema, que es el número de formas que tenemos para hacer un cambio por una cantidad específica. Entonces supongamos que tenemos una cantidad de $5 que está justo aquí. Y lo que vamos a hacer es calcular el número de formas que podemos representar este cinco dólares si tenemos estos billetes aquí mismo. Entonces si tienes factura 1.2.34, y en este caso, lo que vamos a hacer es usar la programación dinámica para tener la solución más óptima o el número exacto de formas que podemos calcular usando estas facturas para tener esta cantidad de $5. Entonces para hacer eso, empecemos con crear la lista que vamos a necesitar. Y como dijimos antes, este cinco dólares, vamos a crear una lista que puede conformar hasta $5. Entonces para ello, vamos a tener el tamaño de esta lista como cinco más uno, que son seis. Y este caso, déjame solo crear esta lista aquí mismo. Por lo que tenemos 123456 elementos en esta lista. Por lo que los índices son los siguientes, 012, día 4 y 5. Por lo que estos índices representan la cantidad. Entonces déjame escribirlo aquí mismo. Lo siento. Entonces aquí tenemos la cantidad. Y lo que vamos a tener aquí es el número de formas. Por lo que sólo lo denotaré como número de formas. Entonces lo que vamos a hacer es ir por toda la base que tenemos uno por uno y luego comprobar el número de formas en que podemos representar a este cinco dólares usando estos Belk justo aquí. Entonces, en primer lugar, lo que vamos a hacer es inicializar todos estos a 0. Por lo que 00000. No obstante, el primero sería el caso base. Y es seguro decir que éste debe inicializarse como uno. Ya que si lo pensamos, si no tenemos oh, tenemos un billete de $1 o $2 o tres o 4 dólares y necesitamos presentar la cantidad de ceros. Sólo hay una forma de representar esta cantidad simplemente no teniendo o no usando ninguna de estas cantidades. Por lo que es seguro decir que podemos usar el número de formas como una por la cantidad 0. ¿ Verdad? Ahora, si lo miramos, Empecemos con este de aquí. Entonces déjame cambiar el color. Por lo que ahora estamos trabajando con este billete de 1 dólar. Entonces, ¿cuántas formas podemos representar la cantidad de uno usando una factura de $1? Y es bastante sencillo. Podemos representarlo de una manera. Entonces en lugar de tener 0 aquí, vamos a tener uno. Ahora, pasemos a la cantidad de 2 dólares. ¿ De cuántas maneras podemos representar estos $2 cantidad usando esta factura de $1? Y por supuesto que es lo mismo. Simplemente tenemos una forma que es usar 2 facturas de $1. Lo mismo aquí. Entonces vamos a tener 111. Entonces lo que estamos diciendo es que podemos representar esta cantidad de 34 o 5 dólares usando factura de $1 de una y única manera. Y esto es para usar, por ejemplo, aquí si tenemos cantidad de $3, entonces cómo podemos, ¿cómo podemos obtener esta cantidad de $3? Podemos usar 3 $1 mejor de aquí. Y es lo mismo por 4 $5. Ahora pasemos a la segunda. Es decir, tenemos estos $2, pero ahora lo que vamos a hacer es simplemente omitir 01 cantidad ya que podemos presentar estos montos usando una factura de $2, porque dos es mayor a 01. Entonces vamos a ir todo el camino a esta cantidad de 2 dólares. Ahora, pensémoslo. ¿ Qué tenemos? Tenemos estos $2 cantidad, ¿verdad? Y esto también tenemos estos billetes de 2 dólares. Por lo que podemos representar estos $2 cantidad usando 1 factura de $2 desde aquí. Y por supuesto, no queremos olvidar que podemos representarlo de una manera usando estos billetes de 1 dólar. Entonces lo que vamos a hacer es quitar esto y agregar dos aquí mismo porque podemos representarlo ahora de dos maneras. Y vamos a averiguar la fórmula en un poco, pero vamos a arreglarlo ahora. Entonces por ejemplo, ahora tenemos esta cantidad de 3 dólares. Entonces lo que vamos a hacer es representar también de dos maneras, ¿no? Entonces déjame escribir aquí también, y pensemos en cómo podemos representar esta cantidad tres. Entonces si tenemos $3, podemos usar dos, uh, 3 billetes de $1. Entonces 3 veces 1 o 2, o 1 a billetes de dólar y 1 billete de $1, ¿verdad? Por lo que 12. Facturaciones y 1 billete de $1. Y vamos a conseguir la cantidad que es tres como antes. Ahora bien, si volvemos a aquí y vamos averiguar para cuántas formas podemos representar esta cantidad. Entonces si tenemos 4 dólares y vamos a necesitar ya sea para billetes de 1 dólar o para billetes de dos dólares, o 1 billete de 2 dólares más 2 billetes de 1 dólar. Entonces si esto tiene sentido, está bien si no lo hace, pensemos en ello que tenemos aquí por facturas de 1 dólar. Y aquí tenemos, o tenemos que hacerlo, a billetes de dólar, o tenemos 1 billetes de 2 dólares y a 1 factura. Por lo que todas estas serán las mismas que puedes ver aquí. Si lo dibujo. Nosotros también vamos a tener aquí, y aquí, lo mismo y tenemos por facturas de $1. Entonces eso es todo básicamente. Ahora, pensemos en la fórmula. ¿ Cómo podemos conseguir eso? Tenemos tres vías aquí. Por lo que tenemos tres posibilidades para representar este número cuatro. Y en lugar de tener uno aquí, lo vamos a quitar y añadir tres. Entonces si lo pensamos, podemos ver que si tenemos este billete de $2.2 dólares aquí mismo, lo que realmente hicimos es que agregamos una al número de formas en las que teníamos. Entonces para que quede claro, déjame, sólo escribir la fórmula aquí mismo. Entonces lo que estamos diciendo es que necesitamos actualizar este número, que es número de formas en un índice específico. Supongamos que es anuncio I. Será igual a uno más el número de formas. Y permítanme borrar todo esto. Y es el número de formas a esta cantidad específica, que es cuatro menos lo que obtenemos de aquí. Y vamos a nombrar a esto, a esta lista como facturas y denotar a todos y cada uno de ellos como el proyecto de ley. Entonces es cantidad menos cinturón. Entonces en este caso, si vamos a ver este ejemplo, estamos en la montaña antes y la construcción número dos. Entonces lo que realmente hicimos es que agregamos éste desde aquí. Entonces aquí no es uno, es el número de formas. Entonces es más 0 igual. Y déjame simplemente borrar esto. Entonces, en realidad es igual a este número de formas en I, igual a número de formas en i Entonces lo que ya tenemos, el número real de vías más el número de vías. Escuchemos este número de formas a la cantidad menos las facturas. Entonces esta es la fórmula que vamos a usar ahora si usas aquí mismo, Pensemos en ello. Ya tenemos uno aquí. Entonces el número de formas en, escribo aquí, será igual al uno más número de vías en 4 menos 2, que es igual a 2. Entonces si volvemos al índice para ir a ver que ya tenemos dos aquí. Entonces vamos a tener 1 más 2, que es igual a 3. Y esto es lo que obtuvimos usando el pensamiento o usando el ejemplo que hicimos antes. Por lo que nos enteramos de que tenemos tres formas de representar a estos cuatro. Tenemos facturas de 1 $2. Ahora, pasemos a la última que es de cinco. Y usando esta fórmula, podemos calcular que si tenemos la cantidad de $5 y tenemos esto, estas tuplas, podemos tener una vía más el número de vías a cinco menos dos, que es número de formas en este índice justo aquí, tres. Entonces son dos, así que 1 más 2 serán 3. Ahora bien, si hacemos exactamente lo mismo por el 34 que podemos conseguir. Entonces déjame simplemente cambiar el color. Déjame simplemente hacer que sea tinta azul sea más fácil. Entonces lo que vamos a hacer es simplemente recortar estos desde aquí y pegarlos aquí. Eliminemos esto y sigamos. Entonces lo que estamos diciendo es que ahora estamos a las tres. Entonces como dijimos, podemos saltarnos 012 porque son más pequeñas que tres. Vamos a ir todo el camino a tres. Y ahora lo que vamos a hacer es decir que podemos representar a este Amar tres usando dos vías más el número de vías a tres menos tres. Entonces esta cantidad menos estos tres de aquí, que es el cinturón. Y si vamos al número de caminos, tres meses hoy está en 0, así que tenemos uno. Entonces en lugar de tener tres aquí mismo, vamos a tener 2 más 1, que es 3. Ahora vamos a hacer exactamente lo mismo para éste. Por lo que es 3 más el número de formas a la cantidad menos mil, que es cuatro menos tres, que en realidad es uno. Entonces vamos a cambiar esto en 3 más 1, que es 4. Ahora vamos a terminar con este archivo, que es que tenemos 3 más el número de vías en cantidad que es 5 menos el número de palabras, número de campanas, o el cinturón real, que es genial. Por lo que 5 menos 3 nos dará 2. Y vamos a mirar para tener aquí el número de formas, que es de dos. Entonces vamos a actualizar esto en tres más dos a cinco. Entonces espero que esto tenga sentido. Vamos a seguir con esta final, que son cuatro. Ahora tenemos el monto de cuatro factura a la cena recién computado para estos dos porque no tiene sentido tener este cuatro en 0123 ya que son más pequeños. Entonces lo que vamos a hacer es llevarnos este 4. Tenemos este cuatro, que es el número de vías a I más el número de vías a la cantidad menos 12. Por lo que 4. Esta es la cantidad menos antes de Bill. Entonces vamos a conseguir el número de vías en 0. Entonces podemos ver que son cuatro más uno son cinco. Entonces vamos a llevarnos este cinco aquí mismo. Más el número de formas a la cantidad menos bien, que también está en una, porque número de formas de 5 menos 4 que es igual a una. Entonces número de formas a una, va a comprobar que sea igual a una. Entonces vamos a actualizar esto a cinco más uno. Vamos a terminar con seis. Entonces eso es todo. Básicamente así es como podemos obtener el número de formas usando el método de programación dinámica usando esta cantidad específica. Ahora lo que vamos a hacer es que se vería, si esto es exactamente este es el número correcto de formas. Entonces si tienes esta cantidad de $5 y tenemos estos cuatro tipos de Bill, lo que vamos a hacer es representar este archivo usando estos manualmente. Entonces pensémoslo. Podemos tener cuatro o 5 facturas de $1, o podemos tener 2122 dobles más 1 factura de $1. O también podemos tener dos o 1 billetes de $2 y 3 de $1. O también podemos tener 32. Por lo que 1 billete de 3 dólares y 23 billetes de dólar y 12 dólares lado de negocios. O también podemos tener y 1, así que 1, 4 billetes de dólar y 1 billete de $1. Entonces estos cinco o también podemos tener los 311, por lo que 13 billetes de dólar y a billetes de $1. Y esto si los contamos, 123456. Por lo que terminaremos con seis formas de representar esta cantidad de 5 dólares usando estos cuatro tipos de personas. Entonces espero que esto tenga sentido. En el siguiente video, simplemente vamos a escribir el pseudocódigo de esto y luego lo vamos a implementar en nuestros idiomas. Entonces nos vemos. 12. Número de formas de la forma de pseudo-Code: De acuerdo, entonces en este video que vamos a hacer es resumir nuestros pensamientos y en realidad escribir un pseudocódigo que vamos a usar cuando implementemos esta magnitud, este algoritmo ahora código. Por lo tanto, permítanme borrar todos estos. Y por supuesto todo esto también. Por lo que ahora podemos continuar. Ahora pensémoslo un segundo. Entonces lo que realmente hicimos es que cada vez vamos a usar una obra con cinturón. Así que déjame escribir las píldoras aquí rápido. Por lo que cada vez que vamos a trabajar con un proyecto de ley desde aquí, vamos a sumar o actualizar este número de formas. Entonces lo que vamos a decir es que si la cantidad es menor que esta campana real, No vamos a hacer nada. Nos lo vamos a saltar. Entonces el pseudocódigo debería ir así. Entonces lo primero que vamos a hacer es comprobar si la cantidad es mayor que el cinturón. Pero este es el caso. Vamos a continuar. Por lo que el monto es mayor o igual al proyecto de ley que tenemos. Vamos a hacer algo. En este caso, lo que vamos a hacer es actualizar el número de formas en este cinturón real, ¿verdad? Entonces lo que vamos a hacer lo siento, por esta cantidad real. Entonces lo que vamos a hacer es actualizar el número de formas. Y este caso, será por la cantidad real. Vamos a actualizarlo en. Será igual a dos cosas sumadas para ser igual al número real de formas que realmente tenemos en este momento. Por lo que será igual a número de vías en cantidad. Podemos agregar algo nuevo, que es el número de formas a la cantidad menos una. Por lo que será igual a número de formas a la cantidad menos la campana que tenemos. Ahora, si quieres asegurarte de que este algoritmo realmente funcione, Hagámoslo, por ejemplo, a las cuatro y te permite usar el último aquí mismo, que también es la campana para. Entonces lo que vamos a hacer es asumir que tenemos aquí para. Por lo que ahora estamos en la etapa donde tenemos el número de formas, que son cuatro y lo vamos a actualizar. Entonces vamos a ver si el monto es mayor o igual a la factura. Y este caso la cantidad es de cuatro, que es igual a cuatro. Entonces esto realmente funciona. Lo que vamos a hacer ahora es actualizar el número de formas a la cantidad específica. Por lo que el número de vías a cuatro sería igual al número de vías a cuatro, que es cuatro más el número de formas a la cantidad menos derrame. Entonces el número de formas en cantidad mi hechizo, que es 4 menos 4, para ser igual a 0. Vamos a ir al número de caminos. Toma esta añadida a la 4 nos dará 5. Entonces ahora podemos, sabemos que nuestra fórmula real aquí que generamos es en realidad verdadera y funciona exactamente bien. Entonces eso es todo. Básicamente esto es profundo para la cancha. Y en realidad esto en realidad bastante sencillo. Una vez que conozcas el método puedes llegar a este pseudocódigo. Por lo que animo mucho a todas y cada vez que resuelvas el problema de programación dinámica a escribir, escribirlo así, y tratar de llegar a una solución. Y intenta inventar el método real o la fórmula real que es la TB utilizada en este problema. Entonces como la primera parte del problema, no sabíamos que la fórmula simplemente iría con el flujo. Entonces por ejemplo, aquí, acabamos de decir que en la cantidad 0, no podemos representar de ninguna manera que no sea una y única manera que es no use ninguna cantidad de dinero. Ahora en la cantidad número uno, podemos representarlo si tenemos este $1, pero podemos representarlo por uno. Y aquí exactamente lo mismo para los demás. Y entonces no fue hasta esta cantidad número tres que conocimos la fórmula. Lo siento. No fue hasta la suma del número cuatro que conocimos esa fórmula. Y calculamos usando este ejemplo aquí mismo. Por lo que siempre empieza con un ejemplo y trata de llegar a una fórmula más adelante. Entonces eso es todo. Básicamente, esto es para el pseudocódigo. En el siguiente video lo vamos a implementar y nuestro código real. A verte entonces. 13. Número de formas de Java: Muy bien, entonces en este video vamos a implementar nuestra función, función que se nos ocurrió antes. Y ya instancié este método público estático int número de maneras. Y nos dieron dos parámetros. El primero es la cantidad real denotada por N, y el segundo son las campanas reales. Entonces esta es una matriz de esas de aquí. Entonces lo que vamos a hacer es que vamos a crear una nueva matriz como antes, como dijimos antes, es decir, implementar o agregar el número de formas a todas y cada una de las cantidades. Entonces déjame simplemente instanciar como formas será igual a 0 y más uno, como dijimos. Ahora lo que vamos a hacer es denotar o sumar al primero, como dijimos aquí mismo es el primero debe ser igual a uno. Entonces desperdicio a 0 para ser igual a uno. Y el otro será igual a 0, que son el número predeterminado predeterminado o la forma predeterminada de ser instanciado en una matriz. Entonces como dijimos, ya tenemos uno aquí. Lo que vamos a hacer es pasar por todos estos aquí es de un poco pasar por todo lo que he construido. Y entonces por supuesto vamos a actualizar el número de vías aquí mismo. Entonces volvamos. Ahora, si lo pensamos, lo que vamos a hacer es pagar el bucle for, comenzando con 0 todo el camino a las facturas que longitud y actualizadas. Y el segundo, vamos a tener también 0. Todo el camino a, lo siento, aquí en realidad podemos decir que es uno. Y los dos estarán todo el camino a los caminos. Esa talla de punto longitud, lo siento, yo y j plus, plus. Ahora lo que vamos a hacer en un primer momento es comprobar si esta cantidad es mayor o igual a la factura. Y como dijimos, esta cantidad en realidad está en el segundo for loop denotado como j En realidad podemos cambiar este j en cantidad de ella nos hará, hacerlo más fácil. Entonces déjame cambiar eso de verdad rápido. Y entonces tenemos cantidad también. Ahora lo que vamos a hacer es comprobar si esta cantidad es mayor o igual a la factura real. ¿ Y qué dijimos? Dijimos que éste se anotará como proyectos de ley. Y el ancho de banda real de la factura será en el mejor de los casos en I, que es 0, 1 , 2, 3, y 4, así sucesivamente. Y este caso, lo que vamos a hacer es comprobar si el monto es mayor o igual a lo que será igual a las facturas en. Sé que este es el caso. Tenemos que actualizar el número de formas. Entonces las formas que yo, o las formas que montan algún sitio se actualizarán de dos maneras a la cantidad más formas en, como dijimos, vamos a usar la fórmula, cantidad menos esto aquí mismo. Entonces, ¿cómo conseguimos este proyecto de ley? Serán las campanas en I. Así que en este caso lo que dijimos que podemos calcular esto usando campanas en i Así que simplemente lo voy a escribir aquí mismo en I y actualizamos con éxito. Ahora lo que vamos a hacer es simplemente devolver el número de formas en la última que tenemos. Entonces si volvemos aquí mismo, sólo necesitamos éste de la suya. Entonces este es el número de seis. Recuerda que el propósito de este problema es que si tenemos una cantidad de 5 dólares, ¿cuántas maneras podemos representar este cinco dólares? Y en realidad hicimos todos estos para llegar a la solución final, es decir, un seis. Entonces, ¿cómo podemos tomar esto? Simplemente podemos pedir el número de vías a nuestra cantidad inicial, que es de cinco. Y será igual a seis vías. Entonces eso es todo básicamente ahora, esto es lo que deberíamos regresar aquí mismo. Entonces después de terminar de estos dos para bucles anidados para bucles, vamos a representar las formas en. Entonces eso es todo. Básicamente esto es por este problema. Ahora si vamos a probarlo, simplemente podemos usar una función principal. Entonces simplemente voy a crear un criterio de función principal. Y lo que vamos a hacer es llamar al número de olas con n y facturas. Y antes de eso vamos a inicializar esto aquí mismo. Por lo que n será igual a la muestra real, que es de cinco. Y las facturas finales serán iguales a este real, que es 12341. Bien. Ahora, si queremos imprimirlo, déjame solo lo siento. Sistema solar punto fuera, punto, imprimir aquí mismo. Y vamos a ejecutarlo. Y como podemos ver aquí sobre este problema, voy a conseguir seis, que es el último. Ahora si queremos devolver todo esto por ahora, ver que el último aquí mismo. Entonces lo que vamos a hacer es devolver una lista. Y si lo volvemos a ejecutar , lo siento, no podemos correr esto. Por supuesto, solo necesitamos crear un bucle for aquí mismo. Entonces para yo igual a 0, yo es menos que el final y paso. Entonces creo que tenemos, podemos imprimir lo que tenemos. Entonces déjame simplemente crear este lugar aquí mismo para ser igual a número de formas. Entonces creo que estamos bien. Podemos eliminar esto desde aquí. Y por supuesto podemos imprimir formas en todas y cada una de ellas. Entonces con ADD, simplemente lo imprimo. Y lo vamos a imprimir. Por lo que en algún espacio podría continuar. Ahora si lo ejecutamos, vamos a conseguir 11 a 35. Si vamos a aquí, podemos ver que tenemos 1, 1 a 5. Por supuesto, nos olvidamos de la última, olvidamos que es y más uno. Ahora si lo ejecutamos de nuevo, vamos a conseguir uno, 1, 2, 3, 5, 6. Y es la misma exacta menor, la matriz exacta que se nos ocurre usando este ejemplo aquí de forma manual. Entonces eso es todo básicamente para la implementación. Es así como podemos implementarlo. Y por supuesto, no necesitas todo esto. Esto es para fines de visualización. Simplemente necesitamos el último índice o el último elemento en el número de formas menos. Es decir, para representar la cantidad cinco usando cuántas formas de usar esta aquí mismo. Entonces eso es todo básicamente para este ejemplo, nos vemos en el siguiente video. 14. Número de formas de la implementación en JavaScript: Muy bien, entonces en este video, quién puede implementar nuestra función usando un JavaScript. Entonces como dijimos antes, lo vamos a implementar usando este número de formas como una matriz. Y podemos tener dos cosas. El monto real, que es de 5 dólares, y el número de camas, o los tipos de campanas y una matriz o una lista. Entonces lo que vamos a hacer es simplemente empezar con la creación de la función. Entonces la función será una serie de maneras y lo que no hagamos y cuál es la cantidad. Y entonces también hemos denotado por mascotas aquí mismo. Y podemos empezar con la creación de la matriz y nombrarla dos formas de ser iguales a una nueva matriz. Y como dijimos, necesitamos n más uno como talla. Y lo vamos a llenar de ceros. Ahora, como dijimos antes. Pero lo que tenemos que hacer es sentir esta cantidad en 0 por número de maneras, que es una. Entonces para hacer eso, simplemente vamos a escribir formas a 0 para ser iguales a uno. Y ahora podemos empezar con la creación de nuestros dos bucles para anidados. lo que volviendo a este ejemplo, podemos ver que vamos a empezar con un for loop, que será para las campanas. Y luego vamos a actualizar el número de formas cada vez que pasemos por un nuevo proyecto de ley. Por lo que la primera será para el nacimiento. Para tenemos una cantidad variable o el primero será menos mismo en realidad, y será igual a 0 al principio. Y entonces lo que vamos a hacer es actualizarlo. Por supuesto que será hasta y más uno. Y luego vamos a construir. Entonces eso es todo básicamente. Y ahora lo que vamos a hacer, lo siento, no hasta el n más uno. Es culpable y la lista real. Y en este caso, lo que vamos a escribir es Bills dot length. Entonces eso es todo para el primer bucle for. El otro estaría anidado, será cantidad variable, que será igual a 1. Y este caso vamos a mirar todo el camino a cantidad que será igual a menos que y más uno. Ahora lo que vamos a hacer es actualizar esta cantidad cada vez que lo pasemos. Ahora, podemos empezar con la función real. Entonces lo que vamos a decir es que vamos a mirar, mira este específico aquí mismo. Entonces si la cantidad es mayor o igual a la cama, y como usted dijo, Bill no es un índice como lo inicializamos antes, realidad es lo mejor en este índice real. Entonces por ejemplo, aquí a 0 vamos a conseguir uno, éste vamos a conseguir 2 y así sucesivamente y así sucesivamente. Entonces implementarse, pero tenemos que hacer es comprobar si el monto es igual o igual. Esta campanas en este índice el cual se construirá. Ahora para que sea más fácil, lo que voy a hacer es simplemente eliminar todo esto y usar otro método para bucle el cual se construirá de facturas. Entonces lo que voy a decir es que vamos a dejar a Bill, facturas. Y ahora podemos usar campana y en lugar de esto en este índice. Entonces esta es otra función. Entonces lo que simplemente estamos diciendo aquí es que el cinturón de nacimiento es en realidad no hacer Reemplazar facturas, 0 de facturas a una y así sucesivamente y así sucesivamente. Por lo que realmente ya no necesitamos eso. Podemos simplemente usarlo como. Ahora lo que vamos a hacer es actualizar el número de formas a la cantidad específica simplemente agregando este número de formas a la cantidad específica a una cosa nueva. Ese es el número de formas a la cantidad menos la factura real. Entonces esta es la fórmula que se nos ocurre aquí mismo. Y ya dijimos que este proyecto de ley está construido en i Así que estamos bien. Esta es la fórmula real que continuará. Y ahora simplemente necesitamos devolver el número de formas en el último índice. Entonces esto es seis. Basta con devolver el número de vías a la cantidad que es de cinco. En este caso, lo tenemos tan denotado como n. Entonces simplemente vamos a regresar caminos. Y ahora estamos bien. Creo que podemos trabajar con ello. Esta es nuestra fórmula real. Ahora bien, si queremos usarlo o probarlo, en realidad podemos hacerlo aquí mismo. Entonces denotemos, dejemos n igual a cinco y llevemos a un área de 12345. Ahora, lo que vamos a hacer es imprimir el número de formas que podemos crear con esta cantidad y se llena. Entonces ahora si realmente probamos, bien, así que aquí hemos consultado rama amigdalar. Y en este caso lo que voy a dirigirme a CMD y lo que voy a usar para ejecutar el JavaScript. Voy a usar el servidor NodeJS. Si aún no lo has instalado. Puedes seguir adelante e instalarlo ahora mismo. Simplemente puede dirigirse a anotar. Y como dijimos, puede descargarlo desde aquí. Así que adelante y descárguelo. Entonces lo que haces es dirigirte a tu dinámica o a tu directorio. En este caso, lo voy a nombrar JavaScript programación dinámica. Y en esta programación dinámica, voy a tener esta cantidad de formas cantidad que creé antes. Y simplemente puedes ejecutarlo desde el suyo. Entonces voy a usar estos nodos y simplemente escribir número de formas, cantidad dot js. Y voy a conseguir seis como el número de vías. Ahora, recuerda que sólo queríamos tener este último. Ahora si queremos visualizar este número de formas, menos. Entonces, en otras palabras, queremos visualizar esta lista como 1, 2, 3, 1, 1, 2, 3, 5, 6. Ten en cuenta que debemos devolver otra cosa. Entonces aquí estamos regresando formas en las que podemos competir formas escritas. Ahora si lo volvemos a ejecutar, vamos a conseguir esto menos que, es 112357. Ahora ten en cuenta que sólo necesitamos el último que es representar para representar esta cantidad de 5 dólares con estos cuatro tipos de cinturón. Entonces tenemos seis maneras de hacer eso. Entonces eso es todo básicamente esto es para este problema. Nos vemos en el siguiente video. 15. Número de formas de la implementación de Python: Muy bien, entonces en este video vamos a continuar o función incremental usando Python. Entonces como dijimos antes, tenemos el número de formas que es una lista que vamos a almacenar. El número de formas por cada cantidad específica todo el camino hasta la cantidad final o la cantidad que queremos. Entonces haz eso, empecemos con crear una lista en Python. Entonces vamos a nuestro Visual Studio. Y en este caso, voy a hacer es crear una lista. Yo lo nombraré. Y será simplemente lista, como ésta o simplemente puedo hacer que entre corchetes. Y en este caso lo que voy a hacer es llenar esta lista hasta el final, aquí mismo. Entonces, en primer lugar, definamos nuestros dos parámetros. Entonces el primero es y será igual a cinco. Y se construirá el segundo que también es una lista. Y será igual a 1, 2, 3, y 4. Y en este caso, lo que voy a hacer es crear esta lista L o LastName. En realidad pesa ya que lo vamos a usar como desperdicio. Y claro que lo voy a llenar con ceros. Entonces para yo en rango de tal vez n más uno, vamos a hacer es anexar a este 0. Desechos que anexan. Y voy a anexar 0 aquí mismo. Y por supuesto si lo imprimimos, vamos a conseguir que nuestra lista los llene de ceros. Entonces si vamos a aquí y a la derecha, por el número de formas vamos a conseguir 000, 000, 000, y esto está quedando vacía la lista. Por lo que tenemos 012345 elementos o cinco índices, que son seis desde que empezamos con 0. Ahora lo que vamos a hacer es a tercero, el primero fue uno con uno. Entonces lo que voy a hacer es simplemente decir que a las 0, lo voy a llenar con uno. Lo volveré a ejecutar. Vamos a conseguir uno justo aquí. Por lo que ahora podemos empezar con nuestra función. Tenemos todo listo para nosotros. Podemos resolver nuestros bucles for. Ya que tenemos esta función, lo que vamos a hacer es recorrer todos los elementos o todos los extremos de los números justo aquí en las campanas, luego hacer lo mismo por el número de formas y actualizadas. Entonces voy a eliminar marca y voy a seguir con creación de una construcción a partir de las facturas. Entonces ahora que podemos continuar, podemos crear la cantidad ahora mismo para estas formas específicas. Entonces lo que vamos a hacer es que vamos a empezar de uno todo el camino hasta el n plus 1. Y cómo podemos hacer eso, podemos usar rango de uno todo el camino hasta el final más uno. Y entonces claro que vamos a abrir este look. Y vamos a comprobar, como dijimos antes, si el monto es mayor que el proyecto de ley, vamos a actualizar el número de vías. Entonces, ¿cómo se hace eso? Simplemente comprobamos si la cantidad es mayor o igual a las campanas o se crea la tensión. Si este es el caso, vamos a necesitar actualizar el número de formas. Por lo que un número de formas a la cantidad será igual, como dijimos, usando la fórmula que generamos en el pseudocódigo, número de vías igual al número de vías más número de vías a la cantidad menos minus 1. Entonces en este caso, número de formas A cantidad igual a dos vías a cantidad más formas a cantidad menos el cinturón. Ahora ten en cuenta que este proyecto de ley es en realidad que estamos usando construido y construido. Y esto nos dará campanas a 0, campanas a yo y así sucesivamente y así sucesivamente. Entonces esto es solo tal vez una solución de atajo para el for-loop en lugar de tenerlo en rango de y acceso y campanas en i para índices específicos podemos usar factura y campanas. Entonces eso es todo. Básicamente así es como podemos actualizarlo. Ahora lo que vamos a hacer es simplemente imprimir aquí mismo. Entonces si imprimimos formas, y ahora volvamos aquí. Y como pueden ver, obtuvimos el mismo resultado exacto que esperábamos uno, 1, 2, 3, 5 y 6. Entonces aquí esta, 1, 2, 3, 5, y 6. Por lo que sabemos que funciona nuestro programa. Ahora lo que pretendemos hacer o cuál era nuestro objetivo, generar el número de formas que podemos especificar o podemos crear $5 a cambio $5 con el supuesto de que sólo tenemos estos cuatro tipos de facturas. Entonces, ¿cómo hacemos eso? Simplemente devolvemos el último porque el último elemento de la lista indica que es por la cantidad de 5. Entonces eso es todo. Básicamente acabamos de devolver los caminos en. Y ahora si volvemos atrás y lo ejecutamos de nuevo, vamos a conseguir seis indicando que tenemos seis formas de implementar o a MD sí, para implementar esta función o para tener 5 dólares de estos cuatro tipos de facturas. Entonces eso es todo básicamente para la implementación de Python. Dicho esto, este es el final de este video. Nos vemos en el siguiente. 16. Problema de la Knapsack: De acuerdo, entonces en este video, lo que vamos a hacer es repasar uno de los problemas más famosos en la programación dinámica. Y se le conoce como el problema de la mochila. Y este problema tiene en realidad dos versiones del mismo. El primero es la versión fraccional y el otro es el discreto. Ahora lo que vamos a hacer es pasar por un ejemplo. Y vamos a discutir estas dos versiones y vamos a aprender sobre una de ellas. Y en realidad se ha resuelto usando programación dinámica. Entonces para repasarlo, Empecemos con el ejemplo. La idea de este problema es que tienes algunos artículos o productos, y todos y cada uno de estos artículos tiene un peso y un valor. Entonces supongamos que tenemos cuatro artículos. El primero, así que simplemente los escribo aquí. Por lo que el primero será un peso cinco. El segundo será de peso para el tercero se esperan tres, y el último será de peso también. Entonces aquí estamos. Tenemos cuatro productos teniendo todas estas formas. Ahora tenemos que sumar la cantidad o el valor de estos productos. Por lo que el primero será un valor 28. Por lo que 28 dólares, el segundo será un valor 20. El tercero será a los 18, y el último a los 11. Por lo que 18 y 11. Ahora, el problema real es que te van a dar estos artículos junto a un peso específico que puedes sostener. Entonces, por ejemplo, supongamos que tienes una bolsa. Y en esta bolsa solo puedes sostener hasta 10 en peso. Por lo que necesitas conseguir todos estos productos y sumar hasta 10. Entonces supongamos que tienes aquí bolsa. Y en esta bolsa solo puedes aguantar diez. Por lo que ahora la versión fraccional de este problema en realidad se puede resolver usando algoritmos codiciosos. Y en este caso, veámoslo aquí mismo. Entonces lo que vamos a hacer es que podamos tomar una fracción de estos artículos en peso. Entonces en lugar de tomar todo el artículo, así que tenemos aquí el peso para realmente podemos tomar fracciones de esto. Entonces, por ejemplo, si queremos tener esto desde aquí, entonces tenemos 10, lo que vamos a hacer es dividir estos montos sobre los valores y tomar el máximo de los cuales. Por ejemplo, si tienes 28 más de cinco, vamos a conseguir algo como 5.6. Déjame escribirlo aquí mismo. El segundo será de cinco. El tercero será de 18 sobre tres, que serán seis. Y el final será en realidad 5.5. Ahora, siempre podemos resolverlo usando la cantidad máxima. Entonces para llenar estos pesos de 10, lo que vamos a hacer es tomar todos estos tres de aquí. Entonces vamos a tomar estos tres ya que tienen el valor más alto respecto a la cantidad sobre peso. Y este caso nos vamos a llevar todos estos, así que sumamos hasta 18 dólares. Ahora, vamos a seguir tomando este que es cinco. Entonces si volvemos aquí mismo y sumamos estos cinco, que serán alrededor de 28 dólares. Y porque tiene el valor más alto. Ahora recuerda que el propósito de este problema es resolverlo o tener un peso de diez con una cantidad máxima de dinero. Ahora en este caso tenemos 18 más 28. Y por último, lo que vamos a hacer es tomar este 5.5. Entonces si recuerdas aquí tenemos 532. Ahora, si tomamos 11, vamos a terminar con algo como 11 o 18 más 28 más 11. Entonces esto es, el peso es de tres más cinco más dos, y es igual a 10. Ahora, supongamos que no tenemos un peso de diez. Entonces en lugar de tener un peso de 10, vamos a tener un peso de nueve este caso. Y si vamos a resolver este problema con un peso de nueve, vamos a terminar con lo mismo que antes. No obstante, no quiero tener aquí dos hace dos más tres más cinco es nueve. En este caso. Cuando lleguemos a esta posición, lo que vamos a hacer es tomar una fracción de estos dos. En lugar de tomar Net como un todo, podemos tomar una fracción de ella. Entonces vamos a tomar una fracción de dos. Entonces no vamos a tomar toda la herramienta va a tomar una fracción, que es que se puede tomar una. Y este caso, el valor será de 5.5. Por lo que es 11 sobre 2, que es 525. Ahora toda la cantidad o todo el peso es de 3 más 5 más 1, que es. En realidad igual a nueve. Y en este caso, podemos usar un algoritmo codicioso que busca algo o el valor, el valor más grande que tenemos. Entonces por ejemplo, aquí tenemos seis, Bueno Toma todos estos. Entonces vamos a comprobar si todavía tenemos un lugar. Por supuesto que vamos a tener un lugar ya que sólo sumamos el peso de tres. Por lo que nueve menos tres, todavía nos quedan seis. Nos vamos a llevar todos estos. Entonces sólo nos queda uno. Vamos a ir y buscar entre 55.55.5 es más grande y vamos a tomarlo como el más grande. Y por supuesto podemos tomar una fracción de ella, no toda la cantidad. Entonces esta es la idea de una mochila fraccional. Y esto es en realidad, esto en realidad no funciona si tenemos uno discreto. Entonces imagina que tenemos una mochila discreta. Y en este caso, podemos trabajar con ello porque una vez que lleguemos a esta etapa aquí, y tenemos 35, entonces todavía nos queda uno. Y este caso no podemos dividir este aquí mismo. Por lo que la solución óptima en realidad neblina para usar cuatro más cinco y esperar. Y por supuesto vamos a terminar con 48 en lugar de 18 más 28. En este caso. Como podemos ver, necesitará utilizar la versión discreta de este problema para tener la programación dinámica como solución para ello. Y eso dicho básicamente para la mochila fraccional, siempre se puede usar el algoritmo codicioso con él, pero no tratamos el rasgo ahora realmente queremos simplemente trabajar con la versión discreta donde tenemos la programación dinámica. Entonces permítanme borrar todo esto desde aquí. Ahora, para la versión discreta, también tenemos dos versiones aquí. Tenemos la cantidad ilimitada y la limitada. Entonces aquí cuando se conoce como sin repetición. Ahora, hablemos de ello un segundo. Para la cantidad ilimitada, significan que tenemos cantidad ilimitada de este artículo, este artículo, este artículo y este artículo. No obstante, hasta que la cantidad limitada, que es sin repetición, sólo tenemos uno de este ítem, E1, producto de este ítem, uno de éstos y uno de éstos. Por lo que realmente no podemos usar este más de una vez. Ahora, lo que vamos a hacer es que vamos a tener un ejemplo y pasar por la cantidad ilimitada al lado de la limitada o sin repetición. Entonces pensémoslo un segundo. Si tenemos este ejemplo aquí mismo, déjame enseñarte. Y déjame realmente tomar todos estos y hacerlos más pequeños y venir aquí. Y voy a hacer exactamente lo mismo para esto también. Y los puse aquí. Ahora, podemos continuar con nuestro trabajo. Ahora imaginemos que tenemos ilimitado o el sin la petición, uno que se sentó con el, sin la repetición. Entonces sin repetición lo que vamos a hacer. Entonces aquí tenemos Without, vamos a tomar este tres, que es el más alto. Entonces otra vez, toma estos tres. Ahora recuerda que necesitamos un peso de diez. Entonces tenemos este tres más éste, más éste de cinco. Ahora si queremos sumar todos estos, entonces aquí tenemos 18.11.28. En este caso, vamos a terminar con 57 dólares como valor final. Y será la más alta para la sin la repetición LFO. Y basta con calcular este 13 más dos más cinco, que es igual a 10. Entonces estamos bien ahora con cantidad ilimitada, pero podemos hacer es, así que déjame simplemente cambiar el color aquí mismo. Entonces aquí tenemos lo ilimitado. Echémosle un vistazo. Entonces imagina que tenemos más de 13, así que tenemos 3 plus. También puede utilizar otros tres, que sumarán hasta seis. Y también podemos usar dos dos dos en este caso. Entonces ahora si lo calculamos, entonces aquí tenemos tres más tres, para que tres sean 18 dólares. Aquí también 18, tenemos 11 y 11. Entonces como pueden ver, esto se convertirá en $58, que será mejor que el anterior si tenemos cantidad ilimitada. Y suponiendo que tengamos el mismo número o los mismos pesos y las mismas cantidades. Entonces en este caso, como puedes ver, es mejor usar la cantidad ilimitada o la repetición de ancho aquí mismo. Entonces estas son las dos versiones que tenemos en la versión discreta del problema de la mochila. Y nos vamos a centrar en ellos. Y también podemos resolverlos usando programación dinámica y el próximo par de videos. Entonces nos vemos. 17. Bolso con repetición: Muy bien, entonces en este video nos vamos a centrar en lo discreto con cantidad ilimitada de versión del problema de la mochila. Entonces, para hacer eso, permítanme simplemente borrar todo esto de aquí. Y también es un indicador. Y déjame tomar todas estas y hacerlas más pequeñas y guardarlas aquí mismo. Y yo hago exactamente lo mismo. Este tipo me deja simplemente tomarlos y colocarlos aquí mismo. Por lo que ahora podemos empezar con nuestro problema de mochila con repetición con cantidad ilimitada o artículos. Entonces en este caso, si queremos mirar, míralo, de esa manera, vamos a terminar con algo que es igual. Por lo que aquí tenemos 58 dólares en total. Por lo tanto, ten en cuenta ese número para los datos. Ahora lo que vamos a hacer es que vamos a usar una matriz o una lista para tratar de resolver este problema y llegar a una solución adecuada usando programación dinámica. Entonces lo que vamos a hacer es que vamos a tomar la cantidad o el peso máximo que tenemos, que es 10, y crear una lista, diez más uno como talla. Entonces déjame solo crear, y esta es nuestra lista. Y lo que vamos a hacer es que vamos a actualizar todas estas, todas y cada una de las veces va a pasar por ellas. Ahora pensémoslo. Lo que pretendemos hacer es que podamos, necesitamos tener la cantidad máxima de dinero usando estos, asumiendo que tenemos 10 como peso. Entonces vamos a usar todos estos. Tenemos una cantidad limitada y vamos a usar cantidad ilimitada y necesitamos encontrar la cantidad máxima de dinero. Empecemos con 01. Por más alto que podamos ver, no tenemos nada y no estamos usando fraccional, así que podemos dividir esto. Entonces lo que vamos a hacer es simplemente escribir 00 aquí. Déjame cambiar el color. Ahora tenemos dos y como podemos ver, podemos usar para, y el costo será de 11 dólares. Ahora recuerda que necesitamos maximizar discutido por ahora, no podemos usar nada más que este 11 para los dos. Ahora si vamos todo el camino hasta las 2, 3, y echemos un vistazo a los tres. Tenemos 18 dólares que es más grande que 11, así que podemos trabajar con 18 aquí mismo. Disculpe, déjame escribirlo mejor. Por lo que tenemos tres, que serán un total de 18. Ahora si vamos al primer plano, como podemos ver para el, por ejemplo, tenemos aquí el valor de 20. Ahora en este caso veinte mayores que 11 y 18. Entonces vamos a escribir 20 aquí. Ahora si vamos a los cinco, en realidad tenemos más de una opción. En este caso, veámoslo. O podemos tener dos y agregarle un tres, que será 11 más 18, que en realidad serán 29. O, lo siento, o si tenemos tres y le sumamos, dos también obtendrán el resultado de 29. Entonces lo que vamos a hacer es simplemente escribir aquí 29. Así que ten en cuenta que lo que hicimos en realidad es usar ya sea 2 más 3 o 3 más 2. Y vamos a conseguir 29. Ahora como el sexo, el valor total o el valor máximo que podemos llegar a ser 3600. Explícalo en un minuto. Mile, piénsalo así. También puedes tener toda esta información aquí mismo. Entonces pensemos en este cinco y en este cinco. Tenga en cuenta que este archivo es la solución óptima para la cantidad máxima, que es 29. Ahora piénsalo como si tuviéramos un cinco y le vamos a sumar uno para que sea un peso de seis. Y este caso, no hay nada que podamos sumar para hacer de esta manera más de 29. Y en este caso vamos a mirar a cuatro. Entonces echemos un vistazo a cuatro. Si tenemos 20 aquí mismo, ¿qué podemos añadir de aquí para hacerlo más grande que 29? En este caso, si lo miramos, podemos sumar dos desde aquí, que tiene el valor de 11. Por lo que 20 más 11, será igual a 31 nazis. Ahora pensemos en este viaje. Entonces tenemos tres. ¿ Qué podemos añadir posiblemente a tres? Tener relaciones sexuales como cantidad era o como peso. En este caso, lo que podemos sumar otros tres, que también sumarán a 18 dólares. Por lo que 18 más 18 para ser 36, que es más grande que 31. Entonces vamos a eliminar esto y tú vas a usar 36. Ahora también vamos a ir todo el camino de vuelta a esto también. Entonces nos vamos a hacer la misma pregunta. ¿ A qué podemos sumar posiblemente, a, para que sea seis? Y por suerte tenemos este cuatro aquí mismo, que es el valor de 20. Entonces si queremos usarlo, podemos sumar el valor de dos, que es 11 más 20, para darnos también 31, que no es el valor óptimo, ya tienen un valor óptimo que es 36. Entonces así es como podemos computar esto. Ahora, pasando a la séptima, y como podemos ver, tenemos 36, pero no podemos agregarle nada. Entonces si queremos usarlo aquí, podemos. Entonces déjame probar eso por ahora, 36. Ahora si volvemos a este expediente, si tenemos 29 y le sumamos estos dos, entonces cinco más dos para darnos siete. Por lo que 2029 más 11, nos dará en realidad 40, que es más grande que 36. Entonces lo vamos a usar. Y por supuesto podemos ir todo el camino de regreso a los 4, 3, y 2, pero esta es la solución óptima y puedes probarlo tú mismo. Ahora pasemos a la ayuda. Esta ayuda, la solución óptima será de 47 y en realidad será de 36 más este de los dos que es 11, por lo que 36 más 11 es 47. Entonces vamos a tener la solución óptima para el peso de nueve, que es 454. Y finalmente 58 para el último, que en realidad está usando este borde desde aquí, la solución óptima de ocho más agregando a ella estos dos de aquí, que tiene un valor de 11, por lo que 47 más 11, que nos dará 58. Y como pueden ver, obtuvimos el mismo resultado exacto que antes. Entonces eso es todo. Es así como podemos obtener la cantidad máxima utilizando el método de programación dinámica. Sé que si vas a resolver el problema de la mochila, y si tiene un pequeño problema, puede resolverlo solo de cabeza. Realmente no necesitas a éste. Pero, ¿qué pasa si tienes tal vez 10 o 15 productos o artículos aquí mismo? En realidad no se puede simplemente pensar en ello y llegar a la solución adecuada. Entonces esta es la forma correcta. Es así como podemos calcularlo usando la solución óptima que podemos obtener. Entonces eso es todo básicamente para este video. Y el siguiente vamos a escribir pseudocódigo. Y en realidad vamos a llegar a una fórmula que usamos aquí mismo. Entonces dicho eso, este es el final de este video. Nos vemos en el siguiente. 18. Bolso con la repetición de: De acuerdo, entonces ahora que tenemos una idea sobre el problema de la mochila con la repetición, Tomemos sobre o ideemos una fórmula real o solución a este problema en forma de pseudocódigo. Ahora en este caso, lo que vamos a hacer es al principio definir nuestros parámetros. Entonces lo que vamos a conseguir en realidad son tres o cuatro parámetros. Voy a hablar de ellos. Entonces el primero será en realidad el peso que vamos a necesitar. Entonces lo que vamos a hacer es escribir aquí w Entonces este es el primer parámetro. El segundo serán los valores reales como 54, lo siento, como 282809, 11. Por lo que esta será una matriz. Entonces en este caso, sólo los denotaré por Val. Entonces es una lista o una matriz. Ahora, este tercero van a ser los pesos reales. Entonces sólo voy a intentar y ancho. Y por supuesto que va a ser otra matriz de lista. Y por supuesto el final sería el tamaño de la longitud de este archivo y pesos. Entonces sólo denotaré por n. Está bien, entonces, ¿qué significa esto? Por lo que Val y las olas deberían ser lo mismo. Por ejemplo, val a 0. Tenemos, en este ejemplo específico, tendremos el valor 28 y espera en 0. Tendremos el valor de cinco. Entonces es así como podemos acceder a ellos ya que tienen el mismo índice. Por lo que 28, 524, 18, 3, 11, y 2. Entonces esto es un, básicamente esto es lo que vamos a conseguir ahora, pensémoslo de una manera dinámica de programación. Entonces lo primero que vamos a hacer es crear esta matriz, ¿verdad? Y el semi en realidad es de tamaño w más uno, como dijimos. Por lo que simplemente denoté como un denotaje que es la capacidad máxima que podemos conseguir. Entonces nuestra matriz será MA, y por supuesto su tamaño debería serlo. Entonces esta es la matriz o la lista y de tamaño Tune ser este peso más 1. Entonces w más uno. Ahora recordemos que cuando teníamos el sello como peso, creamos este array de longitud diez más uno. Entonces esta es la longitud 11, todo el camino desde el índice uno, índice 0, lo siento, hasta el final del índice 10. Ahora bien, esta es nuestra matriz llamada MA. Ahora podemos empezar a formular o pasar por dos bucles para anidados y actualizar estos valores aquí mismo. Entonces déjame enumerar algunas de estas. Elimine esto. Voy a tomar todos estos y hacerlos más pequeños. Creo que realmente no los necesitamos por ahora. Simplemente los agregaré aquí mismo. Ahora el segundo será éste. Entonces esto es lo primero que vamos a hacer y nuestro código. Ahora recuerda que lo que pretendemos hacer es crear una lista o una matriz que contenga los valores óptimos para cada peso específico. Por ejemplo, el valor óptimo aquí para este peso de 0 es 0. El índice óptimo de uno es 0. El peso óptimo de 2 es 11, y así sucesivamente y así sucesivamente. Entonces por supuesto, cuando lleguemos a este punto, y ese es el seis. Y utilizamos la pantalla desde aquí, usamos 18 más otros 3, que es 36. Sabíamos que esta es la forma óptima que podemos conseguir por este valor de tres. Y por supuesto, esto es muy importante porque los valores dependen unos de otros. Entonces por ejemplo, si esta no es la manera óptima para este valor de tres, y lo usamos en sexo que, por lo tanto, este seis no es la manera óptima también. Entonces eso dice, esta es la idea detrás de ella. Simplemente pretendemos hacer el camino óptimo para cada peso hasta el final. Y por supuesto terminaremos con una manera óptima también. Entonces lo que vamos a hacer ahora es empezar con nuestro for loops. El primero, iremos de 0 todo el camino hasta el final de este peso. Entonces será de 0 a W. Ahora, claro que esto es mayúscula W. Y entonces lo que vamos a hacer es ir y otro for loop. Y esta fórmula será un valor j Ahora este j irá de 0 todo el camino hasta el final. Entonces hablaré de ello en un segundo. Ahora si lo piensas, lo que estamos haciendo básicamente es que estamos dando un bucle. Todos estos uno por uno. Y cada vez, por ejemplo, si eres un dos, lo que vamos a hacer es mirar a través de todos estos aquí mismo. Entonces vamos a mirar a través de 5, 4, 3, y 2. Por lo que estos pesos deben, debemos acceder a ellos. Y también podemos acceder a estos valores utilizando los válidos de los que hablamos antes. Entonces eso es todo. Básicamente, tenemos nuestro Val y desechos y podemos acceder a ellos dentro de estos dos para bucles. Y lo que vamos a hacer es comprobar si este peso en un índice específico de j, ¿verdad? Tan extremidad, recuerda que estamos loping, buceando por esto con j Así que de esta manera, en un índice específico es menor o igual a los pesos reales por los que estamos pasando, entonces podemos hacer algo. De lo contrario nosotros, realmente no importa y no tiene sentido cambiar. Entonces, por ejemplo, pasemos por uno de los ejemplos. Supongamos que estamos en una justo aquí. Lo que vamos a hacer es recorrer todos estos. Ahora lo que vamos a decir es si este cinco es menor o igual a uno, entonces vamos a hacer algo. Ahora. Recordemos que cinco no es mayor que ni menor que uno. Entonces lo que vamos a hacer es simplemente ignorarlo, ya que podemos representar la disuasoria S1 usando estos cinco. Ahora lo que vas a hacer es pasar por todo esto hasta el momento, 432. Y vamos a ver que no son menos de uno. Entonces por supuesto que lo vamos a ignorar, que el 0 descanse como están. Ahora lo que vamos a hacer es pasar por otro ejemplo. Ahora, estamos en yo igual a dos en este caso, este es yo. entonces preguntémonos si estos dos son menos de cinco, lo siento, si estos dos son mayores a cinco, entonces no va a hacer nada. Este dos es mayor que cuatro o tres. No. Entonces es este dos es mayor o igual a 2. Sí. Entonces podemos usar esto para aquí. Entonces agregamos el valor que tenemos aquí, que fue 0 realmente agregado a este valor a partir de aquí. Entonces eso es todo. Básicamente, así es como podemos hacerlo. Ahora, probémoslo con el último ejemplo. Entonces, por ejemplo, supongamos que estamos a las cuatro. Preguntémonos así que son 4 mayores que 5? No, no podemos usarlo. Es para mayor que cuatro, mayor que o igual En realidad, sí, lo es. Entonces lo que vamos a hacer es tomar este 4 y acceder a él. Por supuesto, usando el, entonces por ejemplo, estamos aquí en esto porque lo que vamos a hacer es escribir, déjame escribir la fórmula. Entonces lo que vamos a conseguir en realidad es que vamos a actualizar este valor a las cuatro en otra cosa. Eso es MA, al peso que teníamos. Entonces esta es la forma con la que estamos trabajando menos el peso que vamos a tomar. Y en este caso es antes. Por supuesto, esta no es fórmula definida. Vamos a necesitar agregarle este valor aquí desde el defecto que obtenemos. Entonces es más 20, soy un f a 0 en realidad. Entonces esto es 0 MA a 0. Lo vamos a ver y es 0. Entonces 0 más 20, vamos a conseguir 20. Ahora, pensémoslo un segundo. ¿ Qué hicimos aquí mismo? Bueno, si realmente lo hiciste, es que estamos en peso por ahora, recuerda que necesitas un peso de cuatro. Y por supuesto, si vas a conseguir el peso de cuatro de aquí, en realidad necesitas estar teniendo 0 pesos y agregarle este cuatro para ser un 284, ¿verdad? Entonces, por ejemplo, si vas a sumar el peso de tres, vas a necesitar estar teniendo un peso de uno, luego agregarle tres, obtenemos este peso de cuatro, ¿verdad? Entonces eso es todo. Básicamente así es como puedes calcularlo. Simplemente piensa en ello que si vas a sumar este peso de cuatro, ¿a dónde preferirías volar antes para llegar a esta posición aquí mismo? Y la solución en realidad, la, la solución real es bastante sencilla. Deberías estar en el índice 0. Añádele este cuatro. Desde aquí, vamos a llegar a él. Entonces, por eso estamos agregando este valor desde aquí al de aquí. Y luego lo vamos a tener a los 20 aquí mismo. Entonces esa es la idea detrás de ella, es cómo podemos reunirnos. Ahora pensemos en otro, otro bucle. Entonces ahora supongamos que estamos a las tres. Nos vamos a preguntar si cuatro es mayor o igual a tres. Sí, lo es. Lo que vamos a hacer es tomar MA a las cuatro. Vamos a actualizarlo. Por supuesto, no vamos a hacerlo si es menos que este 20 real de aquí. Por supuesto. Por lo que tenemos aquí nuestros 20. Ahora, déjame mostrarlo aquí mismo. Entonces aquí tenemos, ya teníamos 0, ¿verdad? Ahora, lo pensamos ya que es 20 mayor que 0. Sí, deberíamos actualizarlo. Entonces aquí tenemos 20. Ahora si estamos en este árbol, lo que vas a hacer es preguntarnos, es mayor que cuatro? Lo siento, Es genial para mayor o igual a tres. Sí, lo es. Podemos actualizarlo. Ahora tenemos que comprobar el valor. Si es mayor a 20, entonces podemos actualizar este. Si no lo es, entonces no tiene sentido actualizarse. Ahora veámoslo. ¿ Qué vamos a hacer? Entonces decimos que MA a los cuatro debe ser igual a MA a este cuatro menos tres más el valor que obtenemos de aquí, que es 18. Ahora el valor en M, un cuatro menos tres, que es un 01, lo siento, también es 0. Entonces vamos a sumar 0 más 8, que es igual a A1. Ahora vamos a comprobar si 20, menos de 18. No, no lo es. Entonces vamos a mantener el sudor 20 e ignorar este. Y por supuesto que vamos a continuar. Por lo que aún nos queda este. Y por supuesto vamos a decir que MA en, para tal vez igual a MA a 4 menos 2 más el valor que teníamos un que es 11. Muy bien, ¿Entonces es este el caso? Entonces soy un a las dos, en realidad son 11. Entonces vamos a conseguir 11 más 11, que en realidad es 22, que también es mayor que este 20. Por lo que podemos actualizarlo aquí mismo. Entonces eso es todo. Básicamente esta es toda la idea al respecto. Esta es la idea general sobre este problema de mochila. Ahora lo que vamos a hacer es simplemente hacer que se vea mejor y código absoluto. Entonces ya tenemos esta fórmula aquí, pero feliz, acaba de borrarla y escribirla de nuevo. Y de manera bonita. Entonces lo que vamos a decir es que vamos a recorrer todos los pesos. Entonces recorreremos todos los residuos de aquí para cada forma que tengamos en nuestra matriz. Y vamos a comprobar si el peso de aquí en este índice específico. Entonces pesos y j que o igual a la forma que tenemos aquí, que es I. En realidad. Si este es el caso, entonces vamos a actualizar algo. Pero vamos a actualizar en realidad es la forma en que tenemos MDMA para crearlo. Entonces MA y este índice específico, que es yo, deberían ser iguales al máximo entre dos cosas. Por lo que debe ser igual al máximo entre el primero que es MA a i. Entonces es el máximo entre sí o la MA a I menos los pesos a j Por supuesto, después de terminar de esto, vamos a llegar a agregar el valor que está en la matriz val a partir de aquí. Entonces vamos a sumar un valor en j Ahora pensémoslo por un segundo. En este caso, lo que vamos a decir es que estamos, si estamos en esto por, por ejemplo, y estamos aquí en estas cuatro. Por lo que cuatro es mayor o igual a cuatro. Esto es con una J, que es como accedemos al marcador, es 4. Este es mayor o igual a los pesos a j Sí, los vamos a actualizar un a cuatro. En este caso, la MA a los cuatro, debe ser igual al valor real y la MA a cuatro, o la MA a cuatro menos cuatro, que es 0, más el valor en este índice específico, que es 20. Entonces eso es todo. Básicamente esta es la fórmula. Y por supuesto, siempre debes empezar pensando en la matriz que diseñaste antes, luego llegar a una solución real. Trató de pensar en cómo usamos los valores de antes y nuestros índices reales aquí. Y en realidad, realmente necesitas pasar por todos los ejemplos para ver el patrón real de esta fórmula. Entonces dicho eso, este es el final de este video. Nos vemos. 19. Knapsack con la aplicación de la versión de la: Oh, bien, entonces en este video vamos a resolver el problema de la mochila con la repetición. Entonces lo primero que voy a hacer es crear una función. Por lo que será público, estático. Y lo voy a nombrar mochila. Entonces vamos a conseguir que los parámetros al primero debe ser el peso, como dijimos, el segundo debe ser la longitud de los valores y los ítems. Entonces tenemos el valor, los valores, y luego tenemos el peso. Ahora, vamos a abrirla. Y ahora lo que vamos a hacer es crear nuestra lista real. Ese es el, MA. Vamos a definirlo como una matriz. En este caso, un íntimo. Y para tener señales de W más uno, dijimos. Y por supuesto, por defecto en Java, todos estos deberían ser ceros. Por lo que realmente no nos importa poner el primero en 0 y así sucesivamente y así sucesivamente. Por lo que podemos saltarnos esto y empezar directamente con nuestro for loop. Para el primero estará a I igual a 0 y todo el camino hasta el final e incrementado. Entonces el segundo for loop debe ser la mitad j Y en este caso, vamos a ir todo el camino hasta el final de los valores y pesos. Entonces lo vamos a actualizar. Y por supuesto, lo que vamos a hacer ahora es comprobar si estos pesos son menores o iguales a las formas por las que estamos atravesando. Entonces vamos a actualizar el valor dentro de esta fórmula, dentro de esta lista. Entonces esto es todo. Simplemente vamos a usar este que usamos antes. Entonces, déjame volver y escribirlo aquí abajo. Entonces si los pesos a j es menor o igual al peso o al ojo. Ahora recuerda que soy sinónimo del peso, del peso real. Entonces si estamos en yo igual a cuatro, esto significa que tenemos, que es, esta es la forma que representa. Por último, vamos a terminar con la forma final que necesitamos, que es diez. Y esto es a lo que realmente estamos apuntando. Entonces si la espera, lo siento, tenemos un error tipográfico. Entonces si los pesos a j es menor o igual a, yo, puedo actualizar las PMas para el empate mayor debe ser igual a máximo entre dos. Entonces lo que vamos a hacer es usar a Mad Max. Y por supuesto que lo vamos a usar. O soy un at i o algo más que está en i Como dijimos, cinco, simplemente restamos los pesos en j. Y claro vamos a sumar el valor de los valores en j. Así que eso es todo. Básicamente así es como podemos actualizarlo. Y aquí tenemos un error tipográfico. Déjenme aclararlo. Dijeron básicamente esta es nuestra fórmula, así es como podemos actualizarla, solo usa esta fórmula desde aquí. Ahora lo que vamos a hacer es simplemente devolver los últimos de la lista. Por lo tanto, devuelve un a al peso real que queremos. Ahora usémoslo aquí mismo. Entonces en simplemente crear una función principal, solo voy a definir algunos parámetros. Entonces supongamos, usemos el mismo problema exacto o los mismos parámetros exactos de aquí. Entonces tenemos el peso igual a 10, entonces tenemos los valores que son 5, 4, 3, y 2. Por lo que es una menor una matriz. Los valores deben ser 5, 4, 3 y 2. Entonces vamos a pasar a los pesos reales, que también son yo sólo puedo copiar eso desde aquí, 28201811, así 2828 y 11. Entonces vamos a terminar con los valores de esa longitud. Y por supuesto, esto es, claro que lo que vamos a hacer ahora es llamar a la función real. Así que déjame imprimir aquí mismo. Por lo que el sistema dot out, dot print para imprimir en realidad es la mochila. Entonces voy a llamar a esta función aquí mismo con, junto a los siguientes parámetros, por lo que los valores w. Y ahora lo que estamos diciendo, bueno, tenemos un problema aquí mismo. Déjame solo comprobarlo. Método. No es un libro de jugadas. Está bien. Está bien. Entonces simplemente los olvidamos. Deberíamos agregar este desolado Básicamente ahora si seguimos adelante y ejecutamos este. Entonces nos dieron 0, déjame revisar valores y ponderar hacia fuera. ¿ De acuerdo? Entonces yo, vale, entonces aquí tenemos pesos y tú tendrás valores. Es sólo el cambio hecho por error. Ahora si lo volvemos a ejecutar, vamos a conseguir 58, que es exactamente el mismo resultado que se nos ocurrió aquí y aquí. Entonces vimos eso usando tres vías. El primero es usar nuestros pensamientos y solo pensar en pensarlo. Entonces usamos éste y nos dieron 58. Y finalmente lo usamos en nuestro código. Por lo que lo más probable es que este sea el camino correcto. Ahora, lo que vamos a hacer es simplemente visualizarlo una última vez. Vamos a visualizar toda la matriz. Entonces en lugar de regresar, solo llama a uno, voy a devolver una matriz. Y por supuesto, voy a crear un for loop, ¿verdad? Sí. Perdón. Por lo que por demasiado tiempo hacer es iterar a través de todo esto. Entonces lo voy a nombrar también aquí, MHC2, y soy una mochila de W y valores y pesos. Ahora ve todo el camino para ser un largo. Y claro que los vamos a imprimir. Entonces simplemente voy a imprimir y con el subespacio de tu correrlo de nuevo, vamos a conseguir exactamente lo mismo que tenemos de aquí. Por lo que tenemos cuarenta setecientos cincuenta y cuatro y cincuenta ocho. Entonces dijeron básicamente, esto es por el problema de la mochila usando Java. 20. Knapsack con la implementación de la versión de Reptition: De acuerdo, Entonces en este video vamos a resolver la mochila con problema de manipulación usando JavaScript. Entonces lo primero que voy a hacer es crear nuestra función. Por lo que la función y el nombre Knapsack. Voy a conseguir los parámetros por lo que tenemos que esperar la longitud de los artículos. Tienes valores y E. Ahora vamos a abrirla. Ahora, vamos a hacer, es realmente crear este método o este menos elástico y a. así que déjame volver atrás y dejarle una nueva matriz de talla n. dijimos que el tamaño debería ser el peso que tenemos más 1. Ahora lo que vamos a hacer es llenarlo de ceros. Entonces vamos a empezar con nuestros dos anidados para bucles. Entonces déjenme igual a 0, soy menor o igual al peso. Y yo plus. Entonces no estamos haciendo nada más que este B se discute aquí, así que solo estamos consiguiendo estos dos por bucles. El primero de 0 a w, El segundo es de dos. Y para que N1, tenemos j igual a 0 todo el camino hasta el final y j plus, plus. Entonces vamos a comprobar si los pesos con los que estamos tratando son en realidad menores o iguales al desperdicio que estamos en esta lista. Y este es el caso, entonces necesitamos actualizarlo con apenas vienen a hacer esto en JavaScript. Entonces si peso en lo específico y eso es menor o igual al índice, lo ablando. Vamos a actualizar el MBA en I debería ser igual al máximo entre dos cosas. Debe ser igual al máximo entre sí. O estoy en I menos P ondas. Como dijimos antes. Y por supuesto vamos a sumar el valor de la lista de valores en i j también. Entonces hay un, básicamente esta es nuestra función real. Ahora lo que vas a hacer es, después de terminar de estos dos para bucles, ir a devolver el MA en WWW. Ahora bien, si sólo vamos a probarlo, vamos a ejecutarlo. Definamos en realidad. Entonces deja w igual a 10, va a tomar el mismo ejemplo exacto de él. Entonces w igual a 10, vamos a tener valores que son iguales a. El valor real es 28, 2018 y 11. Por lo que los valores iguales a 2828 y 11. Entonces tenemos las pesas. Pesos iguales a él es igual a realmente 5, 4, 3, y 2. Entonces vamos a tener n, que es valores longitud de punto. Entonces lo que vamos a hacer es llamar realmente a la función junto a estos parámetros. Entonces W y valores y pesos. Y por supuesto que lo vamos a diseñar. Entonces registro de consola. Y lo conseguimos después de que vamos a hacer es en realidad sólo subir y bajar el símbolo del sistema. Y luego voy a dirigirme a mi directorio dentro de este escritorio de tareas, tengo JavaScript aquí mismo. Estoy un poco copiando esto y dirigiéndome a ello. Y luego voy a ejecutar este problema usando nodo. Por lo que nodo mochila con repeticiones, el ab.js y nos dieron un a y como resultado, lo que indica que esto no es un número. Entonces déjame revisarlo. Todo se ve bien para el cabello y máximo. Entonces el problema es, acuerdo, así que el problema está justo aquí. Por lo que tenemos, necesitamos cerrarlo como un plus. Tan sólo para que esta sea la fórmula real. Ahora si volvemos atrás y Annette de nuevo va a conseguir 58 como el número máximo que podemos obtener de esta fórmula. Ahora lo que vamos a hacer es imprimir todo esto en realidad. Entonces en lugar de tener sólo el último, lo voy a hacer sólo por el bien de este problema. Por lo que como podemos ver respecto 000 011, 1822. Y si volvemos aquí, podemos ver 000 011, 1822. Y por supuesto, está todo el camino hasta 2936404912, que es exactamente un 293640 cuarenta y siete cincuenta y cuatro cincuenta ocho. Entonces con eso, podemos asegurarnos de que nuestro problema funcione y obtuvimos el mismo resultado que el que realizamos manualmente aquí mismo en esta lista. Entonces eso es todo, básicamente esto es todo para implementar la mochila con su petición usando script java. 21. Knapsack con la implementación de Python de la Repetition: De acuerdo, Entonces en este video vamos a resolver la mochila con problema de repetición usando Python. Entonces lo primero que voy a hacer es crear la definición o la función. Voy a llamarlo mochila. Y al lado de los parámetros que vamos a utilizar. Tan wn valores y pesos. Ahora vamos a abrirla. Lo primero dentro de esta función, vamos a visualizar el array de lista real que tiene MA, organismo lo, MA, y quién no puede tenerlo en rango de. Por lo que será de ceros y será para I en rango de w más uno. Entonces así es como podemos crear esta lista usando una línea de código en Python. Entonces lo que vamos a hacer es empezar con nuestros dos bucles anidados para. Entonces para I en rango de W, cisne, vamos a crear otro for loop, que es para j en rango de AMP. Entonces vamos a empezar con el padecimiento. Entonces no hicimos nada por ahora. Acabamos de crear estos dos para bucles. Ahora vamos a comprobar si los pesos en j son menores o iguales a I. Entonces si pesos en j es menor o igual a i, vamos a actualizar el AMA en I. Así que puedo agregar, debería ser igual a una de dos cosas. Es el máximo entre el valor real que tenemos, o el máximo o el otro, que es MA en Pi menos pesos en j más el valor de j Ahora volvamos atrás y anotarlo. Entonces max en ya sea MA en o en el segundo, que es MA en pesos en j. Entonces por supuesto vamos a sumar a ella los valores en j. Entonces eso es todo básicamente. Ahora lo que vamos a hacer es simplemente devolver el MA en el último, que está en w Ya que sólo vamos a necesitar este de aquí. Entonces solo lo devolveremos como es ahora para probarlo, déjame solo crear tus cosas. Vamos a usar el mismo ejemplo exacto que usamos aquí. Por lo que w igual a 10, los pesos son 5432. Por lo que peso igual a una lista de 5432. Entonces tenemos los valores que son 28201811. Entonces, por último, tenemos la longitud de estos valores de peso. Ahora lo que vamos a hacer es llamar a esta función e imprimirla. Por lo que simplemente puedes imprimir esta mochila junto a estos valores y pesos de W. Ahora si vamos aquí y lo ejecutamos, así que voy a escribir Python al lado de la mochila con repeticiones y ejecutarlo. Y vamos a conseguir 58 como el número máximo permitido para este ejemplo específico. Ahora para visualizar la lista real que creamos aquí, déjame solo imprimir en lugar de MA y luego vuelvo y a, toda la lista en lugar de devolver el último elemento. Ahora si volvemos atrás y actualizamos y corriendo de nuevo, vamos a conseguir 0011182258. Y si los comparas, son exactamente lo mismo que el ejemplo que hicimos antes. Así 01118, veintidós veintinueve treinta y seis cuarenta, luego cuarenta y siete, cincuenta y cuatro y cincuenta ocho. Entonces eso dicho básicamente, así es como podemos usar Python para crear esta función, la mochila sin repetición. Entonces nos vemos en el siguiente video. 22. Bolso sin repetición: Está bien, entonces en este video vamos a discutir la mochila sin problema de repetición. Ahora bien, este problema específico no funcionará con este método que creamos aquí por la cantidad ilimitada o la cantidad ilimitada de artículos que tenemos. Entonces vamos a usar una matriz 2D y hablaremos de ello en un segundo. Pero antes vamos a usar exactamente el mismo problema o a ejercer este ejemplo. Entonces recuerda que con el, sin versión, obtuvimos 57 como respuesta final. Vamos a usar exactamente el mismo ejemplo. Y ya veremos si vamos a conseguir esto y 57 como resultado. Entonces para hacer eso, permítanme simplemente borrar todos estos y eliminarlos también junto a esto. Ahora podemos empezar, lo que vamos a hacer es crear una matriz 2D. Entonces déjame crearlo y verte en un rato. Como sabemos, esta es la lista o la matriz que vamos a crear y podemos pensar en estos como el peso. Ya que necesitamos un peso de 10, lo que vamos a hacer en realidad es levantar estos lugares vacíos por algunos valores. En cuanto a, son, considerando que tenemos, por ejemplo, este tubo. Entonces hay dos SD espera, déjame simplemente escribirlos aquí. Como dijimos antes. Ya tenemos, por ejemplo, estos dos. Y tiene el valor o la cantidad de 11. Tenemos tres con 18, tenemos cuatro con 20, y cinco con 28. Entonces déjame probarlos aquí muy rápido. Entonces aquí tenemos la cantidad. Tenemos 11, 18, y 20, y 28. Entonces qué vamos a hacer aquí, así que déjame, de acuerdo. Entonces lo primero que vamos a pensar en este problema es que vamos a llenar estos lugares vacíos asumiendo que sólo tenemos este artículo para llenar. Entonces por ejemplo aquí, si queremos llenar el peso de 0 con este artículo, no podemos, así que solo lo dejaremos vacío con 0. Ahora de nuevo, si tenemos un peso de uno y sólo tenemos este artículo. Ahora podemos ver el peso de este ítem que es dos, que es mayor que uno, entonces no podemos hacer con realmente. Ahora entonces nos preguntamos, si tenemos un peso de dos, tienes un artículo que tiene un peso de dos. ¿ Podemos auditar? ¿ Y lo almacenamos aquí? Sí, podemos. Por lo que sólo va a almacenar su valor, que es 11. Está bien, así que déjame cambiar el color a verde y déjame borrar todos estos, escribirlos de nuevo con el verde. Entonces como dijimos, aquí tenemos 0, 0, y aquí también podemos encajar esto. Entonces lo vamos a encajar. Es 11. Ahora, como pueden ver, nos vamos a preguntar si tenemos un peso de tres y sólo tenemos un artículo de ancho dos, ¿podemos guardarlo? Sí, podemos. Por lo que tienda orgánica 11 aquí. Y es lo mismo para todos estos, nos vamos a hacer la misma pregunta. Entonces si tienes un peso de 10, por ejemplo, y solo tenemos un artículo que tiene un peso de dos. ¿ Podemos almacenarlo? Sí, cancelamos. Vamos a almacenar su valor. Entonces vamos a pasar a esto. Ahora aquí no sólo estamos buscando este peso de tres, buscando ambos 32. Entonces lo que vamos a hacer es escribir 000. Y aquí no vamos a almacenar ceros. Porque recuerda que vamos a tener estos dos artículos juntos. Entonces es o podemos almacenar dos o tres o ambos al mismo tiempo. Ahora como sólo tenemos esto como un peso de dos, vamos a almacenar este artículo que es 11. Entonces lo que vamos a hacer es ir a tres. Ahora nos vamos a preguntar, ¿podemos almacenar esto aquí mismo? Sí, porque es igual a a. Entonces lo que vamos a hacer retrocede tres veces aquí. Entonces somos los 11, vamos a ir 1, 2, y 3 vamos a ir a éste que es 0. Y aquí tenemos 18. Entonces vamos a chequear con 18 más 0 es mayor que este. Entonces lo vamos a agregar. En este caso lo es. Entonces le voy a sumar 18. Entonces piénsalo así. Por lo que puedes almacenar o puedes almacenar tres. En este caso, si quieres empezar, solo puedes almacenarlo con un valor de 11. Entonces vamos a sumar aquí 11. No obstante, si no lo haces, necesitas almacenar el valor de 18. Ahora recuerda que cada vez que estamos trabajando con esta matriz 2D, si queremos tener respuestas o si queremos asegurarnos de que aquí nos quedan un peso de tres, necesitamos retroceder tres veces como lo hicimos en la matriz 1D en el ejemplo del problema de repetición de ancho. Entonces en este caso, lo que vamos a hacer es ir a todo el camino arriba y vamos a revisar tres veces antes. Y este caso, si estás en este punto aquí mismo, siempre podemos sumar un ancho de tres y terminar con esta fila justo aquí. Entonces estamos bien. Estamos aquí. Vamos a conseguir 0 más 80 y vamos a tener 18 como respuesta. Ahora pasemos a esto por ahora, nos vamos a preguntar. Está bien, Entonces que tienen 11 o tenemos 18 más este cuatro menos uno. Entonces vamos a conseguir 4 menos 3, que es 1. Vamos a llegar a este punto que es 0. Entonces vamos a almacenar 18. ¿ De acuerdo? Por lo que 0 más 18 igual a 18 es mayor que 11. Nosotros lo vamos a almacenar. Entonces vamos a pasar a este expediente. Ahora, nos vamos a preguntar, ¿es cinco mayor que tres? Sí, lo es. Para que podamos empezar tres. Lo que vamos a hacer es ir a la izquierda, déjenos pensarlo al principio y r sombrero. Entonces si tenemos un peso de cinco, seguramente podemos almacenar ambos artículos con los que son 23. Está bien, entonces les vamos a sumar estos, 11 más 18, van a ser 29. Ahora pensémoslo. El modo en que estamos enfrentando este problema es que si estamos a las cinco, sólo vamos a restarle tres, así que es 2. Vamos a ir todo el camino a dos, vamos a ver el valor aquí, y es 11. Entonces vamos a o almacenar este 11, sólo vamos a agregarlo aquí, o vamos a tomar 11 más 80, que es 29, y 11 más 80 metros 29, que es más grande. Entonces vamos a empezar a los 29. Ahora vamos a hacer exactamente lo mismo para éste. Por lo que es o 11 más 18 u 11, por lo que seguramente cogería 29. Entonces 29, todo el camino hasta el final. Ahora vamos a hacer exactamente lo mismo aquí. Nos vamos a preguntar, aquí podemos almacenar cualquier cosa. No obstante, como ya tenemos 11 aquí, lo vamos a sumar. Y vamos a llegar a este punto donde tenemos cuatro. Vamos a revisar es este 20 más los 4 menos 4. Vamos a ir todo el camino de regreso a 0. Por lo que 0 más 20 es mayor que 18. Sí, lo es. Entonces vamos a almacenar 20, luego vamos a pasar por 20. También vamos a chequear es 20 más 5 menos 4, que está en uno. Entonces aquí tenemos este 0 es 20 más 0. No hay. Entonces solo voy a almacenar 29 en su lugar. Entonces lo que estamos diciendo aquí es que realmente no necesitamos esto para si queremos. Si solo tienes un ancho de cinco, podemos almacenar 32 y nos darán una mejor respuesta de 29 en lugar de tener justo este otoño con una respuesta de 20. Ahora bien, si pensamos en este seis, en realidad podemos resolver 24 con un valor de 31. Pensémoslo con la fórmula. Entonces estamos adheridos a las seis, vamos a tomar seis menos cuatro, que son dos, vas a mirar a 211 más 20, 31 mayor a 9029. Entonces lo vamos a almacenar aquí todo el camino ahora, vamos a pensar en ello con los siete. Entonces a las siete, podemos almacenar 20 más el 7 menos 4, que es 3. Tenemos 18, por lo que 20 más 1838. Por lo que podemos almacenar 38 o el valor anterior, que es 29, yendo a elegir 38. Y en realidad los usamos todos hasta el final. Aquí donde tenemos nueve. Ahora pensémoslo. Si tenemos 20 más nueve menos cuatro, que en realidad son cinco. Entonces vamos a tomar 29 más 20, que es 49. Por lo que podemos elegir 49 o 29 te mostrará elegir 2049, que es picker. Y por último, para los 10, vamos a tener el mismo 49 exacto que antes. Ahora en cuanto a éste, vamos a tener los mismos valores exactos hasta el archivo. Ahora vamos a chequear es 28 mayor a 29? No, no lo hace. Por lo que simplemente vamos a almacenar el 2009. Ahora, cuando dije que si es 28 es mayor que 29, se puede, hay que hacer 28 más esto. Cinco menos cinco, va a ir todo el camino a 0. Vamos a ver el de arriba, que está aquí 0. Por lo que 0 más 28 es mayor que 29. No, Así que vamos a almacenar 29. Ahora en este caso a las seis, también vamos a almacenar sólo 31 ya que no hay nada aquí en también 0. Lo siento, aquí mismo. Entonces vamos a mirar a los siete. Entonces aquí tenemos 38 y el valor de éste Eso es Check it out. Tenemos 28 más siete menos cinco, que está a las dos. Por lo que 28 más 11, en realidad es 39, que es mayor a 38. Entonces vamos a ir con 39. Por último, vamos a hacer, para estos últimos, estamos a las 8. Vamos a tomar ya sea 38 o 28 más 8 menos 5, que es 29. Por lo que 28 más 29 nos va a dar 46. Vamos a elegirlo entonces 9 menos 5, que es 4. Por lo que tenemos en el otoño 20 o 20 más 28 o 49. Entonces tenemos 48 o 49, vamos a ir con 49, que es más grande. Entonces finalmente, para el último, vamos a comprobar si vamos a tomar 49 o vamos a tomar 8 más 10 menos 5, que es a las cinco también. Entonces tenemos 29 más 28, que en realidad es 57. Y este es el mayor o el mayor sensor que podemos tener. Y como podemos ver, obtuvimos exactamente este mismo resultado que hicimos usando nuestro 1000. Y este caso lo que hicimos, en realidad, usamos los cinco más dos más tres. Y si queremos asegurarnos en este ejemplo, siempre se puede hacer eso simplemente diciendo que estás aquí en este 57. ¿ Cómo lo conseguiste? Acabas de agregar 28, que es el peso cinco en el diez menos cinco, que estaba aquí, Este 29. ¿ Todo bien? Y este 29 significa que no agregaste 4, solo agregas el de arriba que está a las tres, ¿verdad? Entonces aquí tenemos cinco hasta ahora. Y ahora vamos a chequear es 29 y 11 el mismo? No, Esto significa que agregaste 32 también. Entonces eso es todo básicamente para el ejemplo a pie de este problema. El siguiente video que vamos a discutir o trabajar con el pseudocódigo que vamos a usar y la implementación del código. Entonces nos vemos. 23. Bolso sin repetición: De acuerdo, entonces lo que venimos a hacer ahora es que vamos a pasar por el pseudocódigo de este problema. Ahora que hemos implementado o trabajado con una solución y trabajamos a través de este problema a través de un ejemplo, realidad podemos llegar a las fórmulas que enrealidad podemos llegar a las fórmulas quevamos a utilizar para escribir el pseudocódigo. Entonces lo primero que vamos a hacer es crear nuestra matriz o nuestra matriz 2D. Ahora en este caso, vamos a asumir es que al principio aquí tenemos una lista vacía. Entonces lo que vamos a decir es que el primero se vaciaría. El segundo estará teniendo este ítem. El tercero, que está aquí, estará teniendo este ítem junto a este ítem también, la cuarta fila estaría teniendo estos tres ítems y el último estaría teniendo todos estos ítems. Y cuando digo que estarían teniendo estos artículos, quiero decir que pueden elegir donde quieran de estos artículos. Entonces eso es todo. Básicamente comenzamos con una matriz vacía. Por supuesto que lo vamos a llenar de ceros. Y por supuesto, el primero aquí va a ser todos ceros también. Entonces eso es todo básicamente. Ahora lo que vamos a hacer es crear nuestra matriz 2D real, que es una y luego una imagen, MA. Ahora lo que vamos a hacer es especificar los tamaños. Recuerda que necesitamos uno vacío aquí. Entonces lo que vamos a hacer es agregarle uno. Entonces, en lugar de tener la longitud de cuatro, por ejemplo, supongamos este ejemplo. Tenemos 2345. Entonces tenemos la longitud de cuatro que vamos a hacer es crear esta matriz 2D como una longitud o un tamaño de cinco en lugar de cuatro, ya que necesitamos agregar este vacío aquí mismo. Entonces lo que vamos a hacer es decir que los tamaños deben ser n más uno para las filas y W más uno para la columna, lo que indica que necesitamos 11 columnas aquí, todo el camino hasta el baile que necesitamos extraer. Ahora lo que vamos a hacer es empezar con nuestros dos for loops. El primero será a partir, así que seré de 0 todo el camino a fin. Y esto es inclusivo. Entonces vamos a crear otro for loop. Yo lo voy a nombrar. W va a ser de 0 todo el camino hasta la gran W. Y también este es inclusivo. Ahora lo que vamos a hacer es comprobar si estamos en una posición específica donde tenemos yo igual a 0. Entonces si el rho I es igual a 0 o la columna es igual a 0. Por lo que podría ser 0 o w igual a 0. Lo que vamos a hacer es poner esto en 0. Como dijimos, tenemos estos valores, ceros aquí mismo, y éstos se usarán más adelante. Por lo que siempre que queramos volver a la posición anterior. Entonces imagina que estamos en este 1112 y estamos pidiendo la posición anterior de esto y no existe. Por lo tanto, necesitamos tener algo antes de un pedido para que no tengamos un error mientras escribo nuestro código. Entonces, por eso asumimos este vacío al principio, que serán sólo ceros. Entonces si voy a 0 o w igual a 0, lo que vamos a hacer es decir que estoy en i y w debería ser igual a 0. Por lo que esta es la primera condición. Ahora, la segunda condición, si los pesos que tenemos mientras pasamos por estos pesos son menores o iguales a la forma real que podría pasarlo. Ahora, en este caso, lo que vamos a hacer es actualizar la MA o esta matriz 2D. Entonces pensémoslo un segundo. Asumamos que estamos en esta posición cuatro, y estamos en esta justo aquí. Tenemos temp tres. Por lo que aún no conocemos este valor. Entonces vamos a chequear. El primero que vamos a comprobar es que mientras pasamos por esto, así que si estos tres son menores o iguales a cuatro, ahora este es el caso, es cierto, entonces podemos actualizarlo. ¿ Cómo podemos actualizarlo? Podemos o ir por 4 menos 3, que será uno, y agregarle este valor de tres, que va a ser 18 más 0. O vamos a tomar el valor por encima de él, que es 11. Entonces, por eso necesitamos comprobar si los pesos son en realidad menores o iguales a esta forma. Y por supuesto, si este no es el caso, lo que vamos a hacer es simplemente tomar el valor desde arriba. Y por supuesto, uno de los ejemplos de esto podría ser es que estamos en este peso tres. Voy a comprobar si este peso es menor o igual a dos y no es menor o igual a dos. Lo que vamos a hacer es simplemente tomar el valor de arriba. Entonces vamos a acceder a la misma una a al mismo peso. No obstante, vamos a acceder a ella con un índice minús1 para tener el valor de lo anterior. Entonces eso es todo básicamente déjame tomar todos estos y hacerlos un poco más pequeños. Y yo los voy a escribir aquí. Entonces sigamos con nuestro código. Entonces dijimos que si f igual a 0 o w igual a 0, vamos a hacer esto. Ahora. El segundo condicionante es comprobar si los pesos al peso específico son menores o iguales al peso que tenemos aquí. Y si este es el caso, necesitamos actualizar la matriz 2D real. Entonces lo que vamos a hacer es comprobar si este peso, por lo que peso en un índice específico, lo voy a dejar vacío por ahora, es menor o igual a w si esta condición se cumple. Pero vamos a hacer es actualizar este i w específico para ser igual a cualquiera, Así que el máximo entre dos cosas. Entonces es o el K i, así que lo voy a escribir aquí. Entonces es o en I menos 1 w Entonces es o el valor por encima o el valor de la lista. Entonces estamos en esta matriz 2D, vamos a, como dijimos, vamos a retroceder por uno. Y en cuanto a las columnas, vamos a de w. Entonces esto, Supongamos que estamos a este valor cuatro y estamos a este peso tres. Y hago cuatro menos tres, que es igual a uno. Entonces vamos a hacer w, que es cuatro menos los pesos en un índice específico con el que estamos tratando. Y entonces lo que vamos a hacer es agregar este valor a partir de valores. Entonces vamos a sumar el valor de nuestro nuevo peso. Es decir, por ejemplo, éste, 18 o 20, o 28 o así sucesivamente. Entonces es el máximo entre el de arriba o el de aquí. Entonces esa es básicamente esta es la fórmula que vamos a usar. Ahora tenemos, todavía tenemos la última condición. Entonces si se cumplen estas dos condiciones, la última es simplemente tomar el valor desde arriba. Y como dijimos, esto no es mayor. Lo siento, no es menor o igual a nuestro peso. Simplemente vamos a copiar el valor desde arriba. Entonces de lo contrario, lo que vamos a hacer es especificar que el índice en i, w, lo siento, el valor de a debe ser igual al valor en I menos 1 w Entonces eso es todo básicamente para nuestro pseudocódigo para este problema. En los próximos videos, los vamos a implementar en nuestro código o en nuestros idiomas. Entonces nos vemos. 24. Knapsack sin repetición Java: De acuerdo, entonces en este video vamos a implementar nuestra función usando Java. Entonces lo primero que voy a hacer es inicializar nuestra función que es una estática pública. Y así puedo devolver el entero? Voy a ir mochila de habilitación. Y va a tomar algunos parámetros como la espera. Y tomo una matriz de peso, entonces vamos a tomar valores profundos como una matriz también. Y por último, tú, voy a tomar la capacidad o la longitud de estos valores y pesos. Ahora lo que vamos a hacer es, al principio y ella miente y w. Entonces vamos a construir nuestra matriz 2D, que se va a llamar una y va a tener n más uno y W más uno como el tamaño de la longitud n. Entonces recordemos que dijimos que necesitamos n más uno porque creamos aquí una matriz vacía o lista vacía. Y cada vez que vamos a pasar, por ejemplo, si estás en esta y siguiente, va a tener una lista vacía más esta. O si estás en, oye, vamos a tener este más éste, y así sucesivamente y así sucesivamente. Entonces es por eso que agregamos n plus 1 aquí indicando que tenemos y más uno crece. De acuerdo, entonces ahora lo que vamos a hacer es empezar con nuestro for loop. Entonces el primero que dijimos que se va a llamar yo hasta el final. Y el segundo será j, así sucesivamente. Lo sentimos, W. Así que w es igual a 0, luego w menor o igual a, crea una w Así que w es menor o igual al botón W mayúscula y W más. Entonces podemos comprobar si i o w es igual a 0. Vamos a simplemente ignorar pero almacenando en I y w el valor de 0. Ahora el segundo caso es que si el peso en i minos1, y veremos por qué es yo menos 1 es menor o igual a w Si este es el caso, entonces vamos a actualizar este y hacer el máximo entre dos cosas. Es decir, el primero debe ser el valor real que tenemos. Entonces soy un en w y este valor p por encima de él. O lo que vamos a hacer es ir arriba. Y en cuanto a la W, vamos a sumar w menos los pesos en I menos 1. Entonces eso es todo. Básicamente, así es como podemos hacerlo. Por supuesto, necesitamos agregar un, algo que sea el valor o el valor de los ítems que tenemos. Y lo vamos a ver en un rato. Pero por ahora, simplemente agregaré valores a I menos 1. Entonces pensémoslo un minuto. ¿ Qué estamos diciendo aquí? Entonces estamos diciendo que si los pesos a I menos 1 es menor o igual a w Ahora, vamos a referirnos a esto por menos uno. ¿ Por qué estamos usando I minús1 set de AI? Ahora bien, recordemos que agregamos aquí una lista vacía. Entonces si un valor, por ejemplo, si estamos tratando con este , tendrá un índice de uno. No obstante, en la lista que vamos a conseguir, los vamos a tener como 2345. Entonces supongamos que son así. Por lo que 2345 y sus valores o montos son los siguientes. A 11182028. Entonces estos son los índices. Por lo que tenemos el índice 0, 1, 2, y 3. Entonces si quieres acceder a ellos desde aquí, aquí tenemos los pesos y aquí tenemos los valores. Y por supuesto, si queremos guardarlos en la lista, vamos a necesitar ordenar. Por ejemplo, supongamos que estamos aquí en I. Si queremos acceder a éste, ahora estamos en el índice uno. No obstante, este índice está en 0 y esta lista de pesos, porque agregamos esta lista vacía, que ocupó un lugar. Entonces si queremos acceder a estos pesos y valores usando I y w, necesitamos recordar o recordar esta lista vacía. Entonces por eso vamos a acceder a ellos usando el por menos uno. Entonces eso es todo. Básicamente esta es la razón por la que usamos yo minos1 aquí, aquí, y también aquí cuando accedemos a los valores en I menos 1. Entonces así es como podemos cambiarlo. Y aún tenemos la última condición, que es si estas dos condiciones no se satisfacen con acaba de hacer un retorno son. Coloque en ella el mismo valor que arriba. Y eso es todo básicamente. Ahora cada vez que terminemos este bucle while, sólo vamos a devolver el valor en y, y mayúscula W. Entonces eso es todo básicamente para este problema. Ahora vamos a seguir adelante y probarlo aquí mismo. Entonces lo que voy a hacer es crear una función principal donde voy a tener un valor. Entonces supongamos que asignamos valores como lista. Voy a tener un 2345 dividido. Entonces voy a tener pesas. Lo siento, acabo de subir. Entonces aquí tenemos los pesos. Y los valores deben ser los siguientes, 11182028. Y por supuesto, vamos a necesitar el w, que es diez. Y luego vamos a tener n, que es valores longitud de punto. Entonces eso es todo básicamente ahora todavía tenemos que llamar a la mochila. Entonces voy a devolverlo a resultados de problema de mochila con, junto a éstos, todos estos. Ahora lo que voy a hacer es simplemente imprimirlo aquí mismo. Entonces voy a imprimir el resultado. Ahora si sigo adelante y lo ejecuto aquí mismo, y voy a conseguir como el valor 57, que en realidad es el mismo valor que obtuvimos de este. Es justo aquí, 57 usando este ejemplo y usando nuestra crianza con donde tenemos 57 también usando tres más dos más cinco. Entonces eso es todo básicamente para este problema. Si quieres ver estos dos, la matriz, simplemente puedes crearla o devolverla ahí mismo, lo siento. Por lo que simplemente podemos devolverlo aquí mismo en una matriz 2D. Y en lugar de devolver este específico, uno, simplemente puede eliminar esto y devolver aquí esta matriz 2D como se sigue. Y por supuesto, en realidad que lo que vamos a hacer es almacenarlos en un resultado. Entonces podemos entrar en un bucle for empezando por el resultado, esa longitud. Y vamos a sumar resultado a por la longitud. Entonces simplemente vamos a imprimirlos. Entonces resultado. Y luego agrega j más algo de espacio, y luego imprime algo de línea r1. Y vamos a conseguir esta matriz 2D. Y por supuesto, si revisamos este que construimos justo aquí, se ve exactamente igual. Entonces tenemos 000 todo el camino hasta el 11, luego tenemos 001111, y luego 929, 000, 011, 820, 29, 31, y luego treinta y ocho treinta y ocho, cuarenta y nueve. Cuarenta y nueve. Entonces es correcto. Y el final con 46, 4957, y los tenemos aquí mismo. Entonces esta es la matriz 2D exacta que tenemos manualmente. Entonces nuestra solución es correcta, y esta es la forma adecuada de implementar este problema usando Java. Vende el problema mochila sin repetición. Entonces eso es todo básicamente para este video. Nos vemos en el siguiente. 25. Knapsack sin repetición: De acuerdo, Entonces en este video vamos a implementar nuestra función para el problema de la mochila sin repetición usando JavaScript. Entonces lo primero que voy a hacer es crear nuestra función, que es mochila. Y va a tomar los siguientes parámetros. Entonces el W, el peso, los valores reales de peso. Y entonces podemos abrirla. Ahora lo que vamos a hacer es definir ambos índices que vamos a utilizar. Entonces vamos a crear nuestra matriz funcional o la 2D. Y en este caso será una matriz y más uno, como dijimos. Entonces podemos empezar con nuestro for loop. Entonces seré igual a 0, como dijimos, irá todo el camino hasta el final. Y luego voy a salir, luego vamos a tener p w En este caso, w es igual a 0, luego todo el camino hasta la W mayúscula y actualizada. Ahora cada vez que entramos a este bucle, pero lo vamos a hacer es crear una nueva matriz en un índice específico de I. Así que será un nuevo array de longitud w más uno para llenarlo. Y ahora en este caso, vamos a comprobar si yo es igual a 0 o w es igual a 0. Lo que vas a hacer es simplemente agregar en esto y yo W un valor de 0. Ahora la segunda condición es si los pesos en un índice específico y voy a denotar por I menos 1. Vamos a hablar de ello en la cama, es menor o igual a w Este es el caso. Entonces necesitamos actualizar esta W en una de dos cosas. Por lo que el máximo entre el valor por encima de él. Entonces es, ¿soy menos 1 w? O la segunda cosa que es, como dijimos, vamos a ir arriba y luego ir a la izquierda usando w menos los pesos en el índice específico, lo que es en I menos 1. Y por supuesto lo que vamos a hacer es agregarle el valor. Entonces los valores a I menos uno. Y entonces esto es con lo que vamos a terminar. El último condicionante es en estas dos condiciones no están satisfechas, pero vamos a hacer es simplemente dar esta posición específica, el valor por encima de ella. Entonces menos 1 w Entonces eso es todo básicamente. Ahora hablemos de por qué usamos el I menos 1 en lugar de yo en este caso. Y la respuesta es que, recuerda que aquí usamos una matriz vacía. Por lo que un criterio de lista vacía. Y lo que realmente hicimos es que tenemos el índice de 0 para esto, entonces tenemos el índice de uno para esto, uno, índice de dos para esto, y así sucesivamente y así sucesivamente. No obstante, cuando tengamos los insumos, vamos a conseguir de la siguiente manera. Entonces a 11 tiene el valor del índice de 0. Y si lo miras a este caso, lo tenemos como índice de uno y la matriz 2D. Entonces qué vamos a hacer si queremos acceder a ella, vamos a usar I menos 1, que es 1 menos 1. Vamos a tener 0 y podemos agregar set correctamente. Lo mismo, lo mismo aplica para todos ellos. Entonces si estamos en el índice 2 justo aquí, cómo podemos acceder a él usando dos menos uno, que es índice uno. Entonces eso es todo Básicamente esta es la razón por la que usamos por minús1 aquí, aquí y allá. Entonces eso es todo básicamente para este problema, lo último que vamos a hacer es simplemente devolver el último aquí, que es en y, y el gran w Ahora vamos a probarlo. Entonces voy a crear valores de 2345, lo siento. El peso. Entonces voy a tener los valores de 11182028. Entonces voy a tener el peso de diez. Y finalmente, al final de esa longitud, así valora esa longitud. Y ahora vamos a llamar a mochila. Entonces voy a iniciar sesión en ella mochila. Y al lado de estos, así que w pesos, luego valores, y luego, acuerdo, así que ahora gastemos este problema o programa. Entonces lo que vamos a hacer es navegar a este directorio y vamos a llamar, Déjenme llamarlo aquí mismo. Entonces nodo mochila sin repetición, ab.js lo va a ejecutar y voy a conseguir 57 como valor definitorio, que es lo mismo que tenemos aquí. Y por supuesto aquí. Entonces esto es todo, así es como podemos resolverlo. Ahora, lo último que voy a hacer es visualizar toda la matriz 2D. Entonces, en lugar de devolver un entero específico, voy a devolver toda la matriz. Ahora, si lo vuelvo a ejecutar y voy a conseguir es una matriz y tenemos el primer golpe, segundo, tercero, cuarto, y 550. Ahora lo que vamos a hacer es simplemente compararlos. Entonces para trazo, en realidad todos los ceros, que es básicamente lo que esperábamos aquí mismo. Entonces tenemos 000 y luego todos son 11. Oye, tenemos el resto son 29, así que vamos a ponernos correctos. Entonces tenemos un gráfico 3849 aquí. Y finalmente tenemos 46, 4957. Y aquí están. Entonces eso es básicamente por este problema. Es así como podemos asegurarnos de que es correcto y nuestra implementación de nuestro código es realmente correcta. Entonces eso es todo para el Knapsack sin repetición usando JavaScript. Dicho esto, este es el final de este video. Nos vemos en el siguiente. 26. Knapsack sin repetición: De acuerdo, Entonces en este video, vamos a resolver la mochila sin problema de permutación usando Python. Entonces el primer paso que voy a dar es crear una función y simplemente puede nombrarla mochila. Y era un gong grande tomar algunos parámetros como el peso, los valores de peso y n. Así que vamos a abrirla. Y lo primero que vamos a hacer es crear nuestra matriz 2D. Y esta matriz debería tomar dos parámetros. Ahora, ¿cómo podemos construirlo usando una línea de código? Simplemente queremos especificar eso para la fila. Por lo que para x en rango de W más uno. Y luego en cuanto a las columnas, lo siento, esto es para las columnas y en cuanto a la fila, lo voy a hacer para rango y plus1, como dijimos. Ahora, podemos empezar con nuestro bucle for. Por lo que el primer bucle for debe comenzar en 0 y terminar con n más 1. Entonces para I en rango y más uno, entonces el segundo for loop debería iniciar un rango de 0 a W más uno. Lo sentimos, tenemos mayúscula W. Y empecemos con nuestro código. Entonces lo primero que vamos a hacer es comprobar si soy igual a 0 o w es igual a 0. Este es el caso. Entonces simplemente vamos a querer actualización o simplemente vamos a agregar 0 a este valor. Entonces eso es todo básicamente ahora lo demás. Entonces lo que vamos a hacer es comprobar si los pesos a I menos 1. Vamos a hablar de yo minús1 Lebanon bit. Pero por ahora pensémoslo así. Entonces si es menor o igual a w, lo que vamos a hacer es actualizar el ojo, la matriz 2D en los índices específicos en el máximo entre dos cosas. El primero es el valor real que tenemos por encima de él. Por lo que minos1 como es, yo indico el camino y w o algo más, ese es el MA a I menos uno. Y en cuanto a la columna, dijimos que hay que restar a W, el desperdicio que vamos a obtener. Por lo que este Pi menos uno en este caso. Y por supuesto vamos a sumar el valor de la misma, que está en yo menos uno también. Y por último, este no es el caso. Además, vamos a hacer otra cosa. Eso es sólo tomar el valor por encima de él y agregarlo a éste de aquí. Entonces estoy en yo menos uno que está por encima de él. Entonces eso es todo básicamente ahora sumar puntuación este me minos1 en el, espera. ¿ Por qué lo usamos? Porque si volvemos a nuestro pseudocódigo, como podemos ver, dijimos que aquí tenemos una matriz vacía. Y si pensamos en nuestros pesos y valores, tenemos pesos, valores y sus índices son los siguientes, 0123. No obstante, en nuestro array 2D, si desea acceder a éste, no está en el índice 0, index1. Aquí tenemos el índice 0, 1, 2, 3, 4, y 5. Entonces si quieres acceder a esto, está en el índice 2 aquí. No obstante, está en el índice uno y nuestro insumo. Entonces, por eso si queremos acceder a éste, simplemente restamos de uno. Entonces si estamos en el índice 3, eso supongamos que así tenemos 0, 1, 2, y 3, estamos aquí. Entonces en el índice 3, cómo acceder a esto por usar nuestra empatía. Por lo que hacemos índice 3 menos 1, que es 2. Ahora podemos acceder a ella con el uso de pesos y valores en el índice dos. Entonces esta es toda la idea sobre el i1 x1 y cómo usarlos. Y por supuesto, si estás confundido con esto, simplemente podemos agregar siempre 0 aquí y aquí. Por lo que esto comenzará en 0, y esto comenzará en 1, 2, 3. Pero por no ser complejo o no, hacerlo complicado, simplemente agregué i menos uno en lugar de I. Así que esto es en este momento lo que vamos a hacer es simplemente devolver la MA en el AND real, y w Entonces esta es la última entrada. Ahora probémoslo. Entonces los valores aquí son en realidad, como dijimos, tenemos 11182028. Entonces tenemos los pesos que son 2, 3, y 4, y 5. Entonces tenemos la W, el peso que vamos a necesitar para igualar a 10, y solo la longitud de los valores. Ahora, probémoslo. Entonces voy a imprimir la mochila. En este caso, voy a tener pesos w, luego valores, entonces. Y ahora si seguimos adelante y nos dirigimos a nuestro CMD, lo que vamos a hacer es ejecutar la mochila de Python sin repetición. Yo lo ejecuto. Y aquí tenemos entonces índice válido. Tienes un refrán estrecho que 0 para x y ganancias de 0. De acuerdo, así que aquí tenemos, no nos hemos comprometido, solo se han comprometido. Ahora intentémoslo de nuevo. Esto es un tipográfico. Tenemos una longitud, nos olvidamos de sumar el n aquí igual a ahora creo que estamos bien. Ahora magnético de nuevo, vamos a conseguir este resultado de 57, como se puede ver aquí. Por lo que esto indica que logramos nuestro objetivo. Ahora lo que vamos a hacer es visualizar toda la matriz 2D. Entonces, en lugar de devolver este último valor, solo voy a devolver toda la matriz. Ahora si sigo adelante y vuelvo a intentarlo, voy a conseguir esto como dijimos. Por lo que tendremos la primera fila, segunda columna. Y por supuesto, si quieres asegurarte de que esto sea correcto, lo que no hacemos es simplemente compararlos con estos. Entonces la primera fila, como dijimos, debería ser todos ceros. La segunda fila es 0, 0, todo el camino hasta las 11. Y el tercero sería 000 011, 1818, y luego todos ellos, 29, entonces tenemos 000 011, 1820, 29. Después terminaremos con 49 y 49. Y la última fila terminará con cuarenta y seis, cuarenta y nueve, y cincuenta y siete. Si lo miramos, tenemos 46 4957. Por lo que esto indica que nuestra solución es correcta. Entonces eso es todo básicamente para este video. Nos vemos en el siguiente. 27. Número de subsets que se agregen a un número específico: Hola y bienvenidos de nuevo. En este video, vamos a discutir el problema de encontrar el número de subconjuntos que pueden sumar un número específico. Ahora en este ejemplo tenemos un conjunto de cuatro números, 1345, y tenemos el número nueve, que vamos a utilizar en este momento. Entonces lo que vamos a hacer es comprobar si tenemos un subconjunto o más de un subconjunto que pueda sumar hasta nueve. Y en este ejemplo, tenemos dos subconjuntos. El primero es 135, y el segundo es para N5. Y ambos suman 90. Si suma todos los índices de elementos dentro del subconjunto, y obtendrá nueve como valor finito. Ahora, pensémoslo un segundo. El primer enfoque que podemos hacer es tenerlo todo resuelto usando recursión. Y la razón por la que digo eso es porque si quieres pensarlo o lo resolvemos usando un trozo de papel. Entonces, por ejemplo, pensémoslo. Si tenemos un conjunto vacío aquí mismo. Entonces déjame dibujarlo aquí mismo. Lo que vamos a hacer es atravesar cada elemento e incluirlo una vez y deshacernos de él el otro. Entonces por ejemplo, Al principio tenemos un conjunto vacío. Vamos a comprobar si esto es igual a 9. No lo es. Lo que vas a hacer es añadir éste desde aquí. Entonces déjame cambiar el color. Vamos a sumar este número 5200 a la vez. Y lo vamos a mantener como está por segunda vez. Ahora lo que vamos a hacer es comprobar también tener esto es igual a 9. No lo es. Lo que vamos a hacer es ir al otro número, que es cuatro. Vamos a sumarlo una vez. Y sólo quédate con cinco, el otro término. Y aquí lo vamos a agregar y mantenerlo vacío. Ahora, podemos pasar al tercer número, que es el 3. Y obras que vamos a hacer es exactamente lo mismo. Entonces aquí tenemos 5, 4, 3, y aquí tenemos lo siento. Sí. Está bien. Por lo que 54. Y claro que vamos a tener aquí 53 y vamos a mantenerlo cinco, aquí mismo, y así sucesivamente y así sucesivamente hasta conseguir todas las combinaciones posibles que podamos conseguir. Y por supuesto, vamos a revisar en cada vez que hayamos construido una pantalla, vamos a comprobar si esto es igual a cuatro. 29 por ejemplo, o esto es igual a nueve. Entonces tenemos 54 es igual a nueve. Entonces incremento el contador. Entonces tal vez tengas un contador variable o algo así, y esto se incrementará. Entonces tenemos nueve por ahora. Entonces vamos a revisar, por ejemplo, la otra solución que es 1, 3, y 5, incluye cinco, está aquí, cinco, 53. Y vamos a tener un 531, que también va a ser cierto. Y vamos a incluir o incrementar el contador. Y como podemos ver para construir este q, necesitamos usar recursión o es la forma más lógica de hacerlo. Ahora lo que vamos a hacer es escribir el pseudocódigo para este método de recursión. Entonces vamos a intentar optimizarlo usando programación dinámica o memorización. Entonces sigamos adelante y lo hagamos aquí mismo. Muy bien, entonces una función tomará tres parámetros. El primero es la lista que vamos a tener. Por lo que sólo lo nombro lista. Entonces vamos a llevarnos un total. Se lo voy a explicar en un segundo. Y luego finalmente, un índice I. Así que pensémoslo un segundo. ¿ Qué vamos a hacer? Al principio, vamos a construir esta matriz que está vacía o menos, que está vacía. Y luego vamos a sumar 52 a la vez y vamos a mantenerlo como es para esto. ¿ Y cómo vamos a hacer eso? Déjame ponerlo justo aquí. Entonces déjenme borrar esto y sigamos. Entonces lo que vamos a tener es un índice que está señalando en este número cinco. La primera vez que empezamos, entonces lo que vamos a hacer es agregar este archivo, por ejemplo, a la lista. Entonces después de eso, lo que vamos a hacer, vamos a retroceder uno por uno hasta recorrer todos los elementos. Y supongamos que agregamos este elemento, que es cuatro. Entonces déjame simplemente denotado en rojo. Entonces supongamos aquí lo que vamos a hacer es comprobar si podemos construir una lista o construir este número nueve usando esta lista, sólo los elementos que incluye cuatro y antes. Entonces lo que vamos a hacer es revisar o crear una función que nos conceda este número exacto, cuántos conjuntos que podemos hacer y que puedas tener dos para que podamos conseguir este número nueve usando sólo estos elementos. Entonces si el índice es sumar estos tres justo aquí, tenemos la lista de 13 solamente. Por lo que queremos incluir 45. Entonces esto es lo que estamos entendiendo por que lo voy a decrementar. Y. Consulta cuántas listas podemos tener una orden para tener este número nueve. Ahora respecto al total, pero no queremos hacer es decrementar cada vez por el número en el índice específico. Y se puede entender en un segundo una vez nos sentamos con la escritura del código. Y lo que pretendemos hacer es finalmente conseguir el número de lo posible tal que podamos tener una orden para conseguir este número nueve. Entonces déjame simplemente borrar esto. Y empecemos con nuestro código walkthrough. Y vamos a hablar y explicarlo mientras lo atravesamos. Entonces lo primero que voy a hacer es, así que esta es nuestra función. Entonces permítanme simplemente denotar estos parámetros como este. Y lo que vamos a hacer es comprobar una vez que lleguemos a un total de 0, esto significa que consumimos todo este número. Tenemos un total de 0, entonces está bien. Podemos devolver uno. Ya que esto es como un caso base. Por ejemplo, aquí, si llegamos al total de 0, que es cinco más cuatro, es igual a nueve, entonces el total de esto se quedará o será 0 en este caso, ya que vamos a disminuir nueve por cinco, luego decrementado por cuatro, vamos a conseguir un total aquí, que es igual a 0. Lo que vamos a hacer es simplemente parar aquí y acrecentar nuestra función. Entonces déjenme simplemente nombrarlo recursión. Por lo que nombra se repite. Y en este caso, si el total es igual a 0, esto significa que pudimos llegar a un subconjunto que suman nueve. Y este caso, lo que vamos a hacer para simplemente devolver uno. Ahora, pensemos si el total es menor a 0 en este caso, como este ejemplo, o tal vez este de aquí. De acuerdo, Así que no tratamos ningún punto donde el total sea menor a 0 que no sea éste. Entonces tal vez sólo tomemos este 5 más 4, que es igual a nueve más tres, que es igual a 12. Y este caso, si el total es menor a 0, entonces lo que vamos a hacer es simplemente devolver 0. Entonces si el total es menor a 0, no podemos devolver 0. Ahora ten en cuenta, queremos, realidad lleguemos a este punto. Podríamos llegar a un punto donde el total es menor a 0 y otros casos donde 54 no son subconjunto de un posible subconjunto. Entonces por ejemplo, tal vez tengamos otro, tal vez sexo justo aquí y nos dieron 6 más 5. Más 6 más 5 en realidad es 11 y esto es mayor que cuatro, mayor que nueve, lo siento. Entonces en este caso, vamos a devolver 0. Entonces eso es todo. Esto es para el segundo caso base. Ahora pasemos al tercer caso base, que es si llegamos a un punto donde llegamos índice mínimo en tener el índice es menor a 0, yo menos a 0. Lo que vamos a hacer es simplemente también devuelve 0, lo que indica que llegamos al extremo izquierdo de nuestra matriz. Y en este caso no encontramos ningún subconjunto que pueda sumar hasta nueve. Entonces si yo es menor que 0, simplemente devuelve 0. Entonces esto es todo para los casos de base. Ahora podemos empezar con nuestra función de recursión. Entonces lo que voy a hacer es simplemente colocarlos aquí mismo. Y este también, voy a colocar como su heredero. Y ahora pasemos a la segunda o La parte divertida aquí mismo. Esa es la recursión en realidad. Entonces ahora lo que vamos a hacer es comprobar como lo haré, el total es menor que un número específico. Entonces, por ejemplo, si estamos en este número cuatro, está bien, entonces lo que vamos a hacer es comprobar si el total que nos queda, que es nueve menos cinco, que es cuatro, es menor que este número. Ahora bien, si este es el caso, entonces no podemos sumar cuatro. No obstante, cuatro no es menor que cuatro, en realidad es igual. Por lo que podemos incluir una tendencia aquí. Entonces tenemos dos casos. El primero es si este número es menor a cuatro, por lo que n es menor al número que tenemos en total. Entonces déjame escribirlo y luego explicarlo más. Entonces si el número total que nos queda es menor al número real dentro de esta lista, así es menor que la lista en un índice específico I. Y así es. Esto significa que podemos sumar nuestro, podemos agregar este número 4 a nuestra lista o a nuestro subconjunto. Entonces lo que vamos a hacer es simplemente mover la flecha hacia los otros elementos. ¿ Cómo se hace eso? Simplemente devolvemos la misma función. Entonces. Recursión en la lista. El mismo total ya que no usamos este total y yo minús1 indicando que ya no necesitamos esto. Ahora bien, si este no es el caso, lo que vamos a hacer es devolver dos cosas. Lo primero es que agregamos esto para el segundo es que no lo sumamos como dijimos aquí. Entonces por ejemplo, si estás en este momento específico donde tenemos cinco y luego llegamos al índice que está en este elemento para lo que vamos a hacer es al principio agregado y luego solo mantener la lista tal como está. Y lo que vamos a hacer es obtener los posibles subconjuntos de esta parte del árbol y todos los subconjuntos posibles de esta k positiva. y luego agregarlos, sumarlos y obtener todos los subconjuntos posibles. En este caso, tenemos aquí uno. Entonces tenemos uno aquí y tenemos uno aquí. Lo que vamos a hacer es agregar uno más uno y esto tomará dos. Y luego vamos a volver a como el posible valor final de calidad que tenemos. Entonces, ¿cómo hacemos eso? Vamos a llevar a funciones de recursión y sumarlas juntas. El primero es que incluimos este cuatro y el segundo es que solo damos la lista tal como está. Entonces lo que vamos a hacer es que lo siento, sólo podemos decir otra cosa. Pero vamos a hacer es devolver dos cosas. Esa es la recursión en esta lista. La primera vez que lo vamos a incluir, sólo vamos a decrementar a partir del total. Entonces vamos a decrementar lista en i y simplemente también decretar nuestro contador. Entonces lo que vas a hacer es incluirlo y luego ir a estos tres aquí mismo. Y vamos a hacer exactamente lo mismo a todos los elementos aquí mismo. Entonces este es el primero y lo vamos a sumar a la misma recursión. No obstante, esta vez vamos a mantener la lista add es, ¿cómo haríamos eso? Simplemente regresamos total en lugar de decrementado por este elemento. Entonces vamos a dar cinco, que son nueve menos uno, total se quedará para, y este caso, también vamos a decrementar. Entonces esa es básicamente esta es nuestra fórmula. Ahora si lo piensas, lo que estamos diciendo es que vamos a pasar por toda esta lista de derecha a izquierda. Y luego vamos a comprobar si se aplica alguno de los casos base. Si este es el caso, vamos a devolver el número apropiado según. Entonces si el total es igual a 0, como este caso, lo que vamos a devolver es uno. De lo contrario no puedes devolver 0. Ahora para la recursión, parte de recursión, pero vamos a hacer es comprobar si nuestro total es menor que el total aquí, el elemento justo aquí. Entonces supongamos que tenemos un total de tres y tenemos el número cuatro. Entonces no hay manera de que podamos agregar nada a forma que pueda conformar este total tres porque tres es menos de cuatro. Entonces lo que vamos a hacer es simplemente mover este índice o esta flecha hacia el anterior. Entonces esto es lo que hicimos aquí. Y si este no es el caso, si sólo podemos poner esto para nuestro set. Pero vamos a hacer es sumar dos cosas y el uno al otro. El primero que está haciendo realmente incluido en nuestro set, y el segundo es realmente sólo mantener el set tal como está. Y luego vamos a ver los números reales desde aquí y aquí y sumarlos. Vamos a obtener el número final usando este método recursión. Entonces eso es todo básicamente para este problema. Ahora lo que vamos a hacer en el siguiente video es tratar de optimizarlo usando programación dinámica y memorización. Entonces nos vemos. 28. Número mejorado: De acuerdo, entonces en este video vamos a tratar de optimizar nuestra solución para esto. Encontrar el número de subconjuntos que pueden adaptarse a un problema de número específico. Entonces el principal inconveniente de nuestra solución recursiva es que vamos a llamar a la misma función recursiva, recursiva una y otra vez. ¿ Y por qué es eso? Porque piénsalo. Si estamos en el número específico, por ejemplo, aquí a las cinco, lo que vamos a hacer es llamarlo una vez más por 54, luego llamarlo una vez más, 45403. Entonces lo que básicamente estamos haciendo es que vamos a sumar estos cuatro aquí. Entonces lo vamos a agregar aquí. Y entonces por supuesto lo vamos a sumar todas y cada vez que pasemos por este, por ejemplo, estos tres, nos van a llamar aquí, aquí. Y luego tenemos a estos zurdos Dr. Chris. Y en este caso se va a llamar una y otra vez. Entonces lo que vamos a hacer es almacenar estos valores dentro tal vez una lista, un diccionario hashmap, cualquier cosa con lo que podamos resolverlo. Y lo que vamos a hacer es en cada momento que vamos a ejecutar esta función o llamarla, vamos a comprobar si este parámetro específico o estos parámetros específicos están realmente incluidos en la lista. Entonces si este es el caso, entonces ya los incluimos y ya calculamos el número de subconjuntos. Y en este caso realmente no necesitamos repasarlo de nuevo. Entonces una forma de hacerlo es, entonces por ejemplo, si estamos aquí y agregamos cinco, entonces agregamos para los tres invadidos. En este caso, cuando sumamos estos tres aquí mismo, lo que vamos a hacer es agregarlos a la lista, por ejemplo. Y luego cada vez que llamamos a este 3, por ejemplo, aquí mismo, si esto es en realidad los tres estaban en la lista, entonces ya calculamos Es número de subconjuntos, entonces realmente no necesitamos volverlo a calcularlo. Y esto es, esto nos permitirá realmente ahorrar mucho tiempo. Porque por ejemplo, si estamos agregando, por ejemplo, si usted está aquí y estamos listos, nos enteramos de que ya hicimos este. Lo que vamos a hacer es simplemente ignorar el resto del árbol que está aquí mismo. Entonces para empezar con ello, en primer lugar, necesitamos definir un nuevo parámetro dentro de nuestra función, es decir, el HashMap real o la lista que vamos a usar. En este caso, simplemente lo nombraré aquí y lo nombraré como memorización. Entonces lo nombro memo. Entonces lo que vamos a hacer es crear una clave y un valor y almacenarlos dentro de este memo. Por lo que será ya sea un diccionario o un HashMap que incluya una clave y un valor. Entonces lo que vamos a hacer es almacenar la clave como el total y el subtotal índice. ¿ Y vamos a encontrar una manera de ordenarlos en la llave? Y el valor debe ser el número de subconjuntos que podemos tener un dado este número específico. Entonces supongamos que sumamos en este. Lo que vamos a hacer es guardar una llave para esto. Y por supuesto vamos a almacenar al valor, por ejemplo, que es 0 para esto porque realmente no conseguimos esto y nueve del subconjunto. Entonces para hacer eso, con lo que vamos a empezar es construir nuestro memo en el punto específico. Entonces si llamamos a esta función, vamos a hacer es construir la clave al principio. Y la clave, lo que voy a usar como cuerda. Entonces voy a usar una cuerda. Además voy a almacenar la coma total, el ojo, que es el índice. Entonces en el esquema debe ser como el, entonces por ejemplo, lo que vamos a tener dentro de esta clave es a Supongamos que estamos en este punto que es aquí, lo que vamos a conseguir es nueve menos cinco, por lo que el total es cuatro. Entonces vamos a almacenar cuatro, subir y el índice es 0, 1 al índice es dos. Entonces esta es nuestra clave. Y nuestro valor debería ser en realidad el número de subconjuntos que podemos hacer contar este punto dado. ¿ Y cómo podemos computar? Y se irá todo el camino de regreso en este número, número uno específico. Y entonces así es como funciona la recursión. Entonces lo que vamos a hacer es comprobar al principio, si esta clave está en realidad dentro de nuestro memo, entonces ya lo computamos. Por lo que realmente no necesitamos repasarlo, así que simplemente lo devolvemos. Entonces para hacer eso, simplemente vamos a agregar aquí si la llave, así que déjame hacer esto un poco más pequeño. Y lo que vamos a hacer es comprobar si la clave es un memo. Pero vamos a hacer es simplemente devolver el valor dentro del esquema, dentro del memo. Entonces devolver memo en clave específica que creamos. Ahora bien, si este no es el caso, entonces continuamos, vamos a continuar nuestra función recursiva. No obstante, lo que vamos a hacer aquí es en lugar de devolverlos enseguida, sólo los vamos a almacenar en un valor y lo voy a nombrar para que regresen. Entonces los vamos a almacenar en un retorno de dos, que es una variable simple. Y luego antes de devolverlos, los vamos a almacenar dentro del memo. Entonces, ¿cómo hacemos eso? Seguimos escribiendo el código aquí. Entonces vamos a almacenar en este memo, en clave. Vamos a almacenar lo que tenemos, así que lo vamos a almacenar para regresar. Y luego después de eso, simplemente podemos regresar. Por lo tanto, volver a regresar. Entonces eso es básicamente ahora lo que realmente hicimos es que construimos una llave. Entonces comprobamos si nuestro valor o lo que pretendemos hacer está en realidad ya en el memorándum. Si este es el caso, entonces simplemente lo devolvemos. Que este no es el caso, lo vamos a calcular. Y entonces por supuesto, sumado a nuestro memo que antes de devolverlo de nuevo. Entonces eso es todo. Básicamente, esto es lo que hay que hacer. Y esto nos ahorrará mucho más tiempo y disminuirá mucho la complejidad porque no lo hicimos, realmente no estamos llamando a la misma función una y otra vez. Ahora, en cuanto al tiempo de ejecución real para este problema, Pensemos en ello. Entonces para todos estos casos base, el tiempo de ejecución real es O de uno. Por lo que realmente no nos importan. En cuanto a esta específica, aquí tenemos las funciones que estábamos llamando a una aquí y estamos viniendo a escribirle. Entonces es o éste uno o dos. Ahora vamos a tomar vamos a asumir que vamos a conocer a Stan. Entonces, ¿lo que vamos a hacer es comprobar cuántas llamadas estamos haciendo? Y la solución real? O la respuesta es bastante simple porque estamos usando este memo, así que no llamar mucho. Entonces pensémoslo. Pero en realidad llamamos es que cada vez que decrementamos por lista yo, lo siento, cada vez que estamos decrementando por yo menos uno. Y en este caso, vamos a llamarlo el número. Dice veces totales el número real de artículos en esta lista. Entonces, ¿por qué hicimos eso? Entonces pensémoslo de esta manera. El número de causas potenciales que venimos a hacer está relacionado con el total y n. porque recuerden que tenemos una lista como tiempos opuestos. Este es el índice 0 y todo el camino a 0123. Entonces lo que vamos a hacer es tener la clave y el valor de acuerdo a esto. Entonces la clave es en realidad lo que hicimos aquí, que es el total más el ojo. Por lo que es justo asumir que tenemos n veces para el ojo porque Annual Great, yo variaría de 0 a tres. Entonces tenemos cuatro y el total en realidad será, si, supongamos que tenemos nueve, en realidad serán nueve veces cuatro posibilidades que podamos obtener este par de valores clave. Y en este caso, esto es tiempos totales n. y vamos a asumir el peor de los casos donde vamos a llamarlo dos veces. Entonces lo vamos a multiplicar por dos. Y este es nuestro tiempo de ejecución que son cuatro. Ahora, siempre podemos quitar esta constante y vamos a conseguir 0 de tiempos totales. Y entonces eso es básicamente por este problema. Ahora en los próximos videos los vamos a implementar fueron en los idiomas que tenemos para verte. 29. Número de la implementación de subsets Java: Muy bien, entonces en este video vamos a implementar nuestra función usando Java. Entonces lo primero que voy a hacer es crear una función con los cuatro parámetros de los que hablamos. Entonces sólo voy a nombrarlo como dijimos. O en este caso, tal vez puedas cambiarlo en memoránimos. Está bien, Así que me lo quedaré por ahora. Tan público, estático. Y esto debería devolver un entero y se volverá a repetir. Y los parámetros del Parlamento son la lista que tenemos, el total, el ojo y el memo. Y por supuesto, nuestra lista debe estar en un ArrayList o menos. Voy a ir con, lo siento, ya sea una lista de array o una matriz. Voy a ir con una lista de array. Así lista de matriz. Y será de tipo entero en este caso. Después está nuestra lista. El total debe ser un número, el final, también un número a un entero. Y finalmente aquí tenemos el mapa hash en este caso. Y tomará una clave y un valor. Por lo que el alkeno será una cadena y el valor real será un entero. Entonces eso es todo básicamente ahora podemos empezar con nuestro código. Lo que vamos a hacer al principio es comprobar, como dijimos, vamos a acumular la clave y comprobar si esta memoria real y nuestra demostración a menos que se llame. Entonces, ¿cómo se hace eso? Simplemente no podemos construir la clave al principio. Entonces déjame simplemente deshacerme de esto. Devuelve 0. Y tenemos, lo que vas a hacer es construir las fortalezas clave de fuerza k igual a cadena del total más la coma más el número real I, que tiene el índice. Ahora, esta clave es en realidad está dentro de nuestro memo. Vamos a devolverlo alguna vez escrito su valor de nuestro memorándum. ¿ Y cómo lo comprobamos? Vamos a utilizar el memo que contiene método clave. Y en este caso, si es cierto, simplemente vamos a devolver el memo a la clave específica. Y lo siento, necesitamos memorizar eso. Consigue el portón específico. Ahora bien, este no es el caso. Lo que vamos a hacer es comprobar si el total es igual a 0. Y este caso, lo que vamos a hacer es simplemente devolver 0. Entonces vamos a comprobar si el total es igual a 0. Lo siento, necesitamos devolver uno indicando que encontramos una lista o un subconjunto que pueda adaptarse al número específico. Ahora si el total es menor a 0, pero no tenemos que hacer es simplemente devolver 0, indicando que no encontramos ninguna cantidad ni menos que pueda sumar nueve. Es más grande que nueve. Ahora, el índice I es menor a 0 también devolverá 0. Y por último, podemos comenzar con nuestras funciones de recursión o causa de recursión. Y la primera es comprobar si el total es menor que esta lista en un índice específico que es i Si es así, entonces no podemos incluirlo. Simplemente vamos a saltar por un índice. ¿ Y cómo hacemos eso? Lo vamos a almacenar en una variable. Entonces permítanme empezar por crear esta variable aquí. Por lo que es un entero a devolver y se inicializará a ceros primero. Ahora lo que vamos a hacer es asignar, volver a esta función recursiva. Y tomará los siguientes parámetros. El primero es el total de lista, y luego yo menos 10, y luego memo. Y por último, una vez que vamos a hacer es revisar o es la última condición. Por lo que realmente no necesitamos comprobar cuáles luego se agregan a la devolución. Entonces regrese, debería ser una de dos cosas. Es o la lista con el número específico en la lista sin ella. Entonces con total me minos1 memo más lista de recursión con total menos menos menos a ojo específico. Y luego vamos a hacer lo mismo yo menos 1 y memo. Ahora antes de devolver esto para regresar de aquí o de aquí, lo que vamos a hacer es guardarlo dentro de nuestro memo. Entonces, ¿cómo se hace eso? Vamos a escribir memoránimos. Y luego vamos a poner dentro de este memo, esta clave, y el valor es en realidad regresar. Ahora, finalmente, podemos simplemente devolver nuestro entero de retorno, que es el número de subconjuntos, pero puedes usar. Entonces eso es todo básicamente para esta función. Ahora lo que vamos a hacer es acumular el frío, la función principal donde vamos a llamar, llamó a ésta y obtener nuestro resultado. Entonces, ¿cómo hacemos eso? Simplemente voy a crear una función principal. Lo siento. Entonces vamos a crear de nuevo. Y dentro de nuestra función principal, lo que vamos a hacer es crear un HashMap. Y tomará una cadena y un entero, y este será nuestro memo para ser igual a nuevo HashMap. Ahora lo que vamos a hacer es crear nuestra lista que incluya el ejemplo que hicimos. Entonces voy a escribir lista de matriz, y esto será agregar un entero. Y luego le vamos a nombrar listas, que es igual a una nueva lista de array. Y voy a añadir algunas cosas. Entonces enlistar eso. Voy a agregar los mismos números exactos aquí para comprobar si obtenemos el mismo resultado exacto. Por lo que 1345. Entonces simplemente voy a sumar 1345. Entonces lo que vamos a hacer es tener nuestro total. Entonces para ser un entero llamado total, para ser igual al total que necesitamos para elegir eso básicamente nueve. Y finalmente lo que nosotros, finalmente, cuando tenga como índice con el que vamos a empezar, que es i, será igual a la lista, ese tamaño menos uno. Entonces eso es básicamente para nuestros parámetros ahora podemos llamar a nuestra función recursiva e imprimirla. Entonces y simplemente imprimirlo directamente. Por lo que se repite en una lista específica, total yo y memo. Y después de eso vamos a ejecutar nuestro código. Y veamos qué vamos a conseguir por un alcaloide. Y vamos a conseguir dos como el valor final o el número final de subconjuntos que podemos usar con el fin de número específico que es 9. Entonces eso es básicamente para la memoización, que en realidad es recursión sin repetición. Como podemos ver, sí usamos exactamente la misma lógica de recursión. obstante, realmente no necesitábamos calcular todas y cada vez que necesitamos un valor específico, podemos almacenarlos dentro de una matriz y luego, por supuesto, volver a ellos más tarde cuando necesitemos usarlos. Y esto ahorrará, nos ahorrará mucho tiempo, y disminuirá mucho la complejidad. Entonces eso es todo básicamente para este llamado walkthrough. Nos vemos en el siguiente video. 30. Número de la implementación de subsets: Muy bien, entonces en este video vamos a implementar una función usando JavaScript. Entonces, empecemos con definir nuestra función. Entonces voy a nombrarlo recurrente, como dijimos. Se llevará una lista y luego se tiene el total, tenemos el índice y el mamífero que vamos a utilizar. Ahora vamos a abrirla. Y lo primero que voy a hacer es realmente crear nuestra clave. Y esto será una cuerda. Entonces simplemente voy a sumar pérdida total, esta coma más I. Ahora lo que vamos a hacer es comprobar si esta clave está dentro de nuestro memo. Entonces, ¿cómo harías eso? Simplemente podemos usar la función. Si este memo que tiene la clave específica, este es el caso, entonces lo que vamos a hacer es simplemente devolver el memo en este caso específico. Entonces, ¿cómo hacemos eso? Vamos a tomar memo que lleguen a la clave específica. Y entonces lo vamos a hacer es simplemente continuar con nuestro código. Entonces como tenemos la función recursiva, dentro de ésta, tenemos el total que es igual a 0. Entonces si el total es igual a 0, entonces simplemente no podemos ignorarlo y simplemente devolver uno como el valor de retorno. Porque esto significa que llegamos a un punto donde nos enteramos de que tenemos un subconjunto que devuelve un total de 0, lo que cumplió nuestra meta en primer lugar. Entonces en este caso vamos a devolver 0. De lo contrario, si el total es menor a 0, esto significa que dentro de una forma devolverá 0. Y entonces lo que vamos a hacer es comprobar si tengo menos de 0, entonces también devuelve 0. Ahora podemos empezar con nuestras funciones recursivas. Entonces si el total es menor a esta lista en un índice específico I. En este caso, lo que vamos a hacer es simplemente devolver la función se repite como dijimos, e ignorar, tendremos total yo minos1 y memo. Y no hay una razón que sea minús1, como dijimos antes, simplemente vamos a saltar. Porque si por ejemplo tenemos la lista en i que es igual a 4, y tenemos el total que es igual a dos. Y en este caso, el total es menor que este valor aquí mismo. Por lo que realmente podemos poner este valor en el subconjunto. Entonces lo vamos a ignorar. Entonces esta es la razón ahora lo que vamos a hacer es simplemente volver una etapa definitoria, volver a repetir a menos total yo minos1 memo más la recursión agregar menos total menos B. Lista a i minos1 lámparas están en I. Y entonces vamos para decretarlo me minús1 y mamífero. Ahora, qué, lo que no hay que hicimos esto aquí mismo es porque vamos a regresar las dos últimas veces. El primero es que incluimos el 5. Por ejemplo, si estás a las cinco, si incluimos los cuatro y el segundo, si no lo incluimos. Entonces esto es lo que vamos a hacer. Simplemente vamos a devolver el total peligroso. Esto significa que no incluimos a los cuatro, y esto significa que incluimos a los cuatro aquí mismo. Entonces eso es todo básicamente ahora lo que vamos a hacer es cambiar esto en una variable. Entonces en lugar de escribir para volver, voy a nombrar una variable aquí mismo para regresar y será igual a 0. Entonces en este caso, volver debe ser igual a esta función. Y claro que vamos a hacer exactamente lo mismo aquí. Debe ser igual a esto. Y por último, antes de regresar a esta variable, voy a almacenar en Zion dentro de este memo, voy a usar memo que decía, y voy a ponerla en este chico va a poner la variable de retorno y luego voy a simplemente devolverlo. Entonces básicamente para esta función ahora lo que vamos a hacer es simplemente probarlo. Entonces voy a tener una lista de 1345 y tenemos un total de nueve. Y tenemos el yo, que es igual a tres en este caso. Y luego tenemos nuestro memo con jazz y nuevo mapa. Entonces mapa de la memoria, y estamos bien. Entonces estas son todas variables, así que déjame solo colocar una barra. Y estamos bien. Esto también es variable. Ahora lo que vamos a hacer es llamar a esta función. Voy a tener el resultado variable. Tenga en cuenta que para mí, llame a esta función con estos parámetros, por lo que el total y la memoria. Y por último, lo voy a cerrar la sesión. Por lo que consola registra los resultados que tenemos. Ahora si vamos aquí y escribimos número de nodos de formas que JS, a quién puedo llegar según lo definido por el número de formas que podemos tener para llegar a este nueve o al valor específico que tenemos. Entonces esto es todo para la implementación del número de formas usando la memoización y JavaScript. Nos vemos en el siguiente video. 31. Número de subsets Python: Muy bien, entonces en este video vamos a implementar nuestra función usando Python. Entonces lo primero que voy a hacer es crear nuestra función y nombrarla. Preparar. Como dijimos, tomaremos los siguientes parámetros. El primero es la lista. Entonces vamos a tener el índice profundo total real y el memo que será el HashMap que utilizamos o el diccionario en este caso. Entonces lo primero que voy a hacer es crear realmente la clave que vamos a usar. Ese es el índice total de comas. Entonces, ¿cómo hacemos eso? Simplemente voy a nombrarlo clave. Y voy a simplemente escribir STR del total plus convertirse en un plus index I. Así STR acti. Y entonces lo que vamos a hacer es comprobar si esto está en el diccionario. Si esto es un memo, entonces F clave y memo, ese caso. Entonces lo que vamos a hacer es simplemente devolver el memo al memo de retorno iso específico, la clave específica y terminamos con ello. Este no es el caso. Lo que vamos a hacer es simplemente buscar los otros casos base. Entonces el primer caso base, si realmente logramos y llegamos al punto donde el total es igual a 0, vamos a devolver uno porque nos escapamos donde tenemos un subconjunto que puede sumar al número específico. Ahora si el total es menor a 0, entonces no llegamos a un punto donde tenemos un subconjunto que suman 0, entonces vamos a devolver 0. De lo contrario, también podemos, también necesitamos revisar la IA, es menos de 0. Entonces vamos a regresar también 0, indicando entonces no encontramos un subconjunto en esta rama de este árbol que estamos construyendo. Ahora, podemos empezar con nuestra función recursiva. Funciones. Y la primera es comprobar si el total es menor que el índice del valor que al final excepto agregamos, si es así, entonces lo que vamos a hacer es devolver una función recursiva sin el índice específico. Entonces recordemos que si estamos, por ejemplo, a las cuatro y nuestro total es de dos, en este caso la puntuación es mayor a 2 dice que esto significa que no podemos sumar este cuatro a nuestro subconjunto con el fin de tener ese total que pretendemos tener. En este caso, lo que vamos a hacer es simplemente devolver este menos total yo menos 1 con nuestro memo. Entonces, ¿cómo se hace eso? Simplemente me dejamos simplemente crear una variable aquí mismo. Y esta variable debería simplemente inicializarse por 0. Y luego vamos a sumar a regresar lo cual será igual a las funciones recursivas que estamos usando lista hija I, minús1 y mamíferos. Entonces si este no es el caso, entonces esto nos dejará con dos. Porque por supuesto el primero es dejar la lista tal como está, sólo disminuir el índice por uno. Y el otro es simplemente tomar la lista y disminuir el total por la lista en lo específico. Lo siento, se me olvidó o t Ahora me minús1 y mamíferos. Entonces lo que estamos diciendo aquí en realidad es que sólo vamos a usar esto por una vez y simplemente ignorarlo la segunda vez. Y esto es lo que realmente estamos haciendo aquí, por ejemplo, aquí vamos a sumar este cuatro al subconjunto. Y no lo va a agregar con simplemente ir a devolver el subconjunto o llamarlo de nuevo sin antes. Y ya veremos uno. Es común después. Entonces ese es el básicamente para nuestra función. Ahora, por fin, lo que realmente necesitamos hacer es simplemente agregarlo a nuestro memo. Por lo que memo a este medidor es igual a regresar. Y luego finalmente nuestro regreso. Ahora probémoslo. Lo que voy a hacer es crear nuestra lista, que es exactamente lo mismo que construimos aquí, 1345. Entonces lista en 1345, entonces vamos a tener un total de nueve. Y también vamos a tener el índice que es un tres. Se va a iniciar en el último elemento, que han sido tres extra. Entonces vamos a tener el memo, que es básicamente un diccionario. Ahora podemos llamar a nuestra función, lo voy a almacenar en un resultado y llamarlo resultado, que va a ser una recursión menos total y mamífero, entonces simplemente puedes imprimirlos. Entonces ahora si seguimos adelante y nos dirigimos a CMD, ve al escritorio. Y luego por programación dinámica. Y luego simplemente voy a ejecutar este código python número de maneras que por me voy a poner un desordenado. Entonces tenemos un error de sintaxis inválido. Y esto en realidad es porque nos olvidamos de agregar aquí la columna y de ponerles fin criterios. Entonces ahora si regresamos y regresamos número de vías, lo siento, así que aquí tenemos anuncios. Entonces eso es todo. Ahora podemos volver a correr y nos dieron dos como el número de formas en que podemos tener subconjuntos también que pueden sumar al número específico nueve. Entonces ese es el básicamente para esta implementación de este problema usando Python para verte en el siguiente video. 32. Subsecuencia común: Hola y bienvenidos de nuevo. En este video vamos a discutir el problema de la subsecuencia común más larga en la fuerza S2. Entonces lo que vamos a tener en realidad es a la fuerza y sólo los escribimos ahí abajo. Entonces vamos a tener x, y, z, w. Y entonces la otra será x, la a w Ahora, a la respuesta de esto es en realidad la longitud de la subsecuencia común más larga. En este caso es igual a tres. ¿ Cómo lo conseguimos? Tenemos x z w, x z, W. Así que como podemos ver, x, z y w es la subsecuencia común más larga dentro de estas dos cuerdas. Y podríamos tener algunas letras entre ellos, pero el orden es el mismo, entonces tenemos hacha que Z y W. Entonces, ¿cómo resolvemos este problema? En realidad, nuestro primer pensamiento entraríamos en recursión ya que necesitamos encontrar las formas posibles o las posibles combinaciones de que podríamos tener una subcadena cada. Y luego vamos a comprobar que esta subcadena coincide con el otro extremo, la segunda cadena. Y si los partidos iban a encontrar su longitud y luego simplemente devolverla como resultado. Y por supuesto vamos a encontrar la longitud máxima que podemos tener dentro de estas dos cuerdas. Entonces, ¿cómo se resuelve este problema usando sólo el papel? Lo que vamos a hacer es comprobar si las dos últimas letras son iguales. Si este es el caso, como pueden ver, W es igual a W, pero lo vamos a hacer es simplemente eliminarlos de nuestras fortalezas y vamos a incrementar nuestro contador en uno. Entonces aquí tenemos uno. De acuerdo, entonces ahora lo que nos queda es en realidad x, y, y z, y la primera cuerda y Ax y Ay y y la otra. Ahora si quieres comparar los dos últimos personajes, podemos ver que no coinciden. Lo que vamos a hacer es probarlo con dos formas posibles. El primer modo es eliminar ese mareado y continuar nuestra solución usando x, y y t de primera mano y B x, z y a por otro lado. Y entonces vamos a hacer lo mismo. No obstante, ahora nos vamos a deshacer de un, así que nos vamos a quedar con x, y, z, y z Ahora, si sigues este camino, como puedes ver, tenemos x, y, z, y a. Y este caso, vamos a seguir con ya sea x y z y a, y la otra solución debe ser x, y, y la x. Así que la primera vez que vamos a quitar la y y la otra vamos a quitar a. Ahora, recuerda es que necesitamos encontrar un título específico que está al final de estos dos hilos y a debe ser igual. Ahora en este caso, si seguimos aquí mismo, vamos a terminar con x y x en un extremo. Y este caso encontramos uno que coincide. Entonces lo que vamos a hacer es acentuar nuestro contador aquí. Y entonces por supuesto si seguimos, Hey, también vamos a terminar con x y x Así que ahora tenemos 11. Lo que vamos a hacer en realidad es comprobar en este punto, por ejemplo. Entonces supongamos que estamos aquí. Lo que vamos a hacer es comprobar el máximo entre los subárboles izquierdo y derecho. Y este caso son iguales, así que sólo vamos a devolver un 1. Ahora, vamos a hacer exactamente lo mismo en esta posición. No obstante, aún no terminamos esta rama. Entonces déjame simplemente terminarlo. Vamos a seguir aquí. Tenemos x, y, z, y z Son iguales. Lo que vamos a hacer es simplemente eliminar estos mareos del heno e incrementar el contador en uno. Y por supuesto vamos a terminar con x, y, y x en la primera, y vamos a tener x y x Y por otro lado, lo siento, déjame simplemente eliminarlos. Entonces vamos a tener una vez, x y x en la segunda vez, que tener XY y nada. Y siempre que no tengamos nada o una cadena vacía, solo devolveremos 0 ya que acabamos de entrar en un lugar en el que no queda tal cadena o caracteres. Y una de las fortalezas, así que sólo vamos a devolver 0, indicando que no encontramos nada hasta que tengamos X y X. Son iguales, por lo que debemos caber en uno. Entonces si estamos en esta posición, x, y, y x, sólo vamos a tomar el máximo entre estas dos fortalezas y en realidad es igual a una. Entonces aquí tenemos uno. Y si estamos en esta fase, X, Y, y Z, vamos a devolver el máximo entre el que está debajo, que en realidad es sólo x, y y agrega, y vamos a tener uno. Por lo que 1 más 1 debe igual, debe ser igual a dos. Y en este caso vamos a devolver el máximo entre estas dos ramas. Entonces tendrás uno y aquí tenemos dos. Entonces vamos a tener que hacerlo, y por supuesto, vamos a terminar con 2 más 1, que en realidad es igual a tres. Entonces eso es todo. Básicamente, este es el árbol que podemos construir. Y lo que en realidad estamos diciendo es que cada vez que tenemos dos fortalezas que, eso coincide juntos. Dos caracteres que son iguales entre sí. Pero lo que vamos a hacer es simplemente quitarlos y continuar con nuestro trabajo. No obstante, tenemos dos pasos para hacerlo. O simplemente eliminamos ocupado o eliminamos el a. y vamos a averiguar cuál está en la subcadena máxima o subsecuencia que se puede devolver usando ya sea x, y, z y a, o X, Y, Z y X, Z y el otro caso. Y yo sólo voy a devolver el máximo. Y por supuesto, siempre que tengamos dos cuerdas o dos caracteres que coincidan, vamos a incrementarlo en uno. Entonces eso es todo básicamente para esta solución Just, solución recursiva. Y lo que vamos a hacer ahora es escribir realmente un pseudocódigo que nos ayude. Y la siguiente fase donde vamos a optimizarlo. Y vamos a encontrar una solución usando programa dinámico. Entonces, antes de hacer eso, permítanme simplemente pensar en la complejidad del tiempo aquí. Si pensamos en las posibles combinaciones en una cadena y usando estadísticas, lo que vamos a averiguar es que si tienes una cadena de cuatro letras, Digamos X, Y, Z, y W. Entonces vamos a encontrar las posibles combinaciones que podrías tomar de aquí. Podemos tener ya sea x, X, Y, XYZ, entonces tenemos y, y, z, y, w, y así sucesivamente y así sucesivamente. Y este caso, lo que vamos a tener es en realidad una combinación de unas cuantas cosas. Entonces, por ejemplo, si tienes una combinación de solo x, vamos a tener una combinación de uno y c1. Y luego si tienes dos letras, X e Y van a tener y C2. Y luego NC3 todo el camino hasta b y c. Y vamos a incluir todas las letras dentro de la cuerda. Entonces, y esto en realidad es igual a dos al poder n. y como se puede ver, Exponencial. Ahora bien, esto es solo para computar las posibles combinaciones en una cadena. Por lo que tenemos dos fortalezas. Tenemos que multiplicarlo por dos. Y entonces lo vamos a multiplicar por n. y este n es porque tenemos que computar la subsecuencia si es común en las dos cadenas. Entonces vamos a averiguar si esto es común, las dos hebras. Entonces vamos a tener de 0 todo el camino a n. y en este caso, realidad es al poder n veces n. que podamos deshacernos de estos dos. Entonces la complejidad del tiempo es y dos. Y como puedes ver, y esto bastante grande y tener dos cuerdas largas, realmente podemos trabajar con ella y tener un tiempo mínimo. Entonces lo que vas a hacer ahora es escribir el pseudocódigo y luego vamos a encontrar la manera de optimizar la solución. Entonces déjame solo deshacerme de estos y los voy a borrar también. Ahora lo que voy a hacer es empezar con pseudocódigo. No obstante, déjame sólo tomar todas estas y más pequeñas, ponlas aquí mismo. Por lo que ahora podemos empezar con pseudocódigo. Lo que vamos a hacer en realidad es empezar con los parámetros. Por lo que sólo voy a nombrar a la función como subsecuencia común más larga. Y en este caso tomará cuatro parámetros. El primero es Pingüino, la segunda cuerda 2, y luego tenemos la posición o los índices que agregamos. Entonces cada vez que decimos vamos a borrar esto o vamos a pasar a éste. Vamos a tomar un índice que sólo señala que esto o esto, o cualquier personaje específico dentro de estas dos hebras. Entonces para s1 vamos a tener hacha y para que tengamos yY lo primero que vamos a empezar es nuestro caso base. Entonces el caso base es en realidad donde simplemente vamos a deshacer y nuestra función, y en realidad será lo que sea que tengamos una cadena vacía. Entonces, ¿cómo encuentras si tienes una cadena vacía? Como dijimos, si x o y es igual a 0, como este caso donde tenemos X, Y, y aquí tenemos una cadena vacía. Entonces el que está indicando la posición de que estamos en S2. Por lo que estamos en la posición 0 o menos uno en este caso. Y si tenemos el, nosotros, si estamos en esta posición, lo que vamos a hacer es simplemente devolver 0. Entonces fx igual a 0 o y igual a 0. Sólo vamos a devolver 0. Ahora, podemos empezar con nuestras llamadas recursivas. Entonces tenemos dos cosas a las que debemos prestar atención. Entonces f, el último carácter es igual. Entonces si el último carácter S1 a x menos uno y es igual a S2 en y menos 1. Este es el caso. Entonces sólo vamos a continuar con nuestro trabajo. Por supuesto, podemos incrementar nuestro contador, que es lo que vamos a regresar. Por lo que esto debería estar escrito en realidad de entero. Entonces vamos a devolver uno. Además vamos a llamar a la función. No obstante, sólo vamos a retirar el petróleo, disminuir nuestros contadores por uno. Entonces si estamos en esta posición, w y w sólo va a decretar sería en z y a en este caso. Entonces, ¿cómo hacemos eso? Simplemente vamos a regresar la subsecuencia común más larga en S1, S2. Como de costumbre, sin embargo, tenemos x menos 1 e y menos 1. Ahora si este tampoco es el caso, tenemos dos cosas entre las que elegir. Dijimos que necesitamos computar el máximo entre el árbol izquierdo y el árbol derecho. Entonces, ¿cómo hacemos eso? Simplemente va a devolver el máximo entre dos cosas. Esa es la subsecuencia común más larga. Tan largo sub común S1, S2 x menos 1 y Así que el primero, sólo vamos a quitar el primer y último personaje y lo primero. Y el segundo, vamos a quitar al último personaje de la segunda fuerza, por lo que la subsecuencia común más larga. Y en este caso vamos a devolver S1, S2, y luego tenemos x e y menos uno. Entonces déjame escribirlas aquí. Entonces tenemos S1, S2, y luego tenemos x e y menos uno en este caso. Entonces eso es todo básicamente para nuestra solución recursiva. Y como podemos ver, tomará demasiado tiempo ya que vamos a computar lo mismo una y otra vez. Entonces por ejemplo, aquí vamos a terminar con x y x, y x y x, x y x. Y claro que continuarás aquí. También vamos a terminar con x y x. Así que vamos a calcularlo al menos cuatro veces en este caso. Y como podemos ver, sólo vamos a computar muchas cosas varias veces. Por lo que nuestra segunda solución debe basarse en la programación dinámica, y podemos simplemente deshacernos de computar estos una y otra vez. Entonces eso es todo básicamente para este problema usando recursión. En el siguiente video, sólo lo vamos a optimizar. Entonces nos vemos. 33. Pseudo-Code común: De acuerdo, entonces ahora en este video vamos a discutir nuestra implementación dinámica de programación del problema de sublevación común más largo. Entonces en realidad vamos a usar la tabulación para esta solución. Entonces, lo que vamos a hacer en realidad es almacenar nuestros valores son nuestros resultados en una matriz 2D, y luego usarlos cada vez que necesitemos mirarlos. Por lo tanto, permítanme empezar por eliminar el pseudocódigo de la función pasada. Y en realidad vamos a hacer es crear una matriz 2D. Y te explicaré por qué en un segundo. Pero esta matriz 2D en realidad contendría nuestras dos cadenas. Entonces como dijimos, tenemos x, y, z y w, y luego Z y W. Así que aquí tenemos impulsos simplemente vamos a asumir que tenemos una cadena vacía. Entonces tenemos x, y, z, w Entonces vamos a tener una cadena vacía x, z, a, y W. Entonces lo que vamos a hacer es empezar asumiendo que aquí tenemos una cadena vacía y aquí tienes una cadena vacía. Y sólo vamos a conseguir la sublevación común más larga. Y en este caso, la sublevencia común más larga es una cadena vacía, que es la longitud 0. Ahora bien, si pasamos al segundo lugar aquí, tenemos una cuerda vacía y actos que podemos ver. La sublevencia común más larga que puedes tener es en realidad de longitud 0 también. Y aquí tenemos, vamos a seguir con cuerdas y y vacías al final de la cadena y W y cuerda vacía. Y lo vamos a rellenar con ceros y simplemente computar lo mismo aquí, cadena vacía con todas estas letras. Entonces vamos a terminar con ceros en ambos lados. Ahora vamos a continuar, vamos a llegar a este punto donde tenemos hacha y hacha. Y lo que en realidad vamos a hacer es, si tenemos X y X, pero vamos a hacer es quitar esta x de aquí y de aquí como hicimos con esta w Entonces si tienes w y w, y en realidad lo hicimos es quitar los w y luego comprobar la x, y, z y precisión. Entonces, la primera vez que vamos a tener esto, por ejemplo. Entonces si este es el caso donde tenemos X y X, entonces sólo vamos a quitar esto y comprobar el que no contiene el último carácter. Entonces, ¿cómo hacemos eso? Sólo vamos a revisar diagonalmente, porque si quitamos X de aquí y x de aquí, vamos a terminar con vacío y vacío, que es aquí. Entonces vamos a sumar uno al valor desde aquí, que es 0. Entonces vamos a terminar con uno aquí. Ahora vamos a continuar. Tenemos x ahora y x, y en este caso. Entonces estamos en esta, vamos a tener x, y, y x. Entonces la subsecuencia común más larga es en realidad, acuerdo a nuestra regla que se nos ocurrió antes, es si tenemos dos personajes que no coinciden, en este caso tenemos x, y, y Ax. Lo que vamos a hacer es revisar por un primero de todo, x y x. Y entonces tenemos, Entonces tendrá x, y, y x La primera vez que vamos a quitar el cable. Y la segunda vez vamos a quitar el xo. Tenemos X y X y X, Y y cuerda vacía. Entonces, ¿cómo acabamos de obtener esta información? vamos a sacar del anterior. Entonces si miramos el anterior, vamos a averiguar que tenemos X y X. Y si miramos hacia arriba, vamos a averiguar que tenemos x, y, y una cuerda vacía. Entonces vamos a computar el máximo entre estos dos según nuestra regla. Entonces tenemos 10, el máximo es uno, así que vamos a llenarlo con uno. Vamos a hacer exactamente lo mismo para XYZ y Ax, vamos a tener uno aquí y uno aquí. Entonces si quieres repasar este x, y, z, y w. Y así si tienes x, y, z, y w y x, lo que vamos a conseguir en realidad, porque los últimos personajes de estas dos cadenas no coinciden. Vamos a continuar con X, Y, Z, y X. Y el otro debe ser x, y, z, w, y una cuerda vacía. Y en este caso, ¿cómo los miras? Vamos a mirar a la izquierda y vamos a terminar con XYZ y actúa como podemos ver, esto es todo. Entonces es 1. Y también tenemos x, y, z, y w, y una cadena vacía que en realidad es 0. Entonces el máximo entre ellos es en realidad uno. Entonces solo implementando nuestro grupo y encontrando lo que queremos de cómputos anteriores. Ahora vamos a seguir con xy y x En este caso, lo que vamos a hacer es mirar a la izquierda y justo por encima de 0 o uno soviético, vamos a seguir con una misma cosa aquí. Tenemos 1 y 1, 1, 1. Y por supuesto aquí tenemos x z y x, y, z, en este caso z y los partidos. Entonces lo que vamos a hacer es agregarle uno y mirar el que es diagonal. En este caso tenemos uno y vamos a sumar uno. Entonces uno más uno, sólo vamos a almacenar dos en este caso en lugar de uno. Y si lo miras, la forma en que lo estábamos tratando antes, si tienes x, y, y z. Y entonces tenemos x, z, pero en realidad lo hicimos es quitar esta z y z, vamos a terminar con x, y, y x Sólo vamos a terminar con también actos y muertes en la etapa final donde tenemos aquí uno y aquí uno, vamos a terminar con dos como respuesta finita. Entonces, ¿cómo hacemos eso? Simplemente miramos los cómputos anteriores sin computar x, y, y x. Una vez más, sólo vamos a tomar el valor que vimos a. Entonces es 2. Y por supuesto vamos a terminar aquí con todo el SO2. Ahora aquí tenemos 0 o 1, que es 1, 1 o 1, 2 también queremos que uno o dos vayan a terminar con 22 o dos. Simplemente va a terminar con también. Ahora vamos a ir hasta el final. Ahora si miramos esto, tenemos x, z, a, w x, y, z, y w. y en este caso, como podemos ver, w y w que igual. Entonces sólo podemos sumar 12, la diagonal, hacerlo, que son dos. Entonces vamos a terminar con tres como valor final en este caso. Entonces lo que realmente hicimos es que usamos la solución recursiva. No obstante, sólo lo almacenamos nuestro trabajo, los resultados, en este caso matriz 2D, y sólo los usamos cuando queríamos. Entonces en lugar de computarlo, todas y cada vez que queremos algo, vamos a almacenarlo insiste array. Y como podemos ver, podemos usarlo aquí o aquí, o aquí. Entonces recuerda que tenemos dos llamadas recursivas. En la solución anterior, tenemos la que si coinciden, y este caso es diagonal y tenemos la que si no coinciden, vamos a tomar el máximo entre ésta o ésta. Entonces al principio vamos a eliminar un elemento de esta matriz o de esta cadena. Y luego eliminaremos un elemento de esta cadena y vamos a computar el máximo y devolverlo aquí. Entonces, básicamente para este problema ahora, lo que vas a hacer es implementar usando pseudo-código. Y entonces por supuesto lo vamos a implementar en nuestros idiomas. Entonces haz eso, déjame simplemente borrar esto y minimizar éste. Y por supuesto, lo que voy a hacer es borrar esto. Y me voy a llevar todo esto y colocarlo aquí mismo. Ahora podemos empezar con pseudocódigo. Lo primero que vamos a hacer es llamar a una función. Voy a nombrarlo más largo. Subsistencia común como de costumbre. Ahora, vamos a tener que ArrayList o array o una lista. Entonces solo voy a computarlas ya que solo S1 es una lista. Guarda eso y se puso como lista. Y claro que vamos a tener los índices en los que estamos. En este caso, lo nombraré x e yAhora , lo primero que vamos a hacer es construir nuestra matriz 2D de matriz y acaba de nombrar la subsecuencia común más larga, LTS. Y será 2D. Y por supuesto lo que vamos a hacer es asumir que tenemos en ceros y cuerdas vacías. Por lo que la longitud de esto debe ser de longitud o tamaño x más 1. Entonces x más uno, y más 1. Ahora podemos empezar con nuestros bucles for. Vamos a llenarlo esta matriz 2D. Y así tenemos el primero en ir de 0 todo el camino a x, o la longitud de ésta. Por lo que será todo el camino hasta x más 1. Y entonces tenemos yo más 1, yo plus, plus, así que yo de 0 a esto. Y luego tenemos cuatro j de 0 a y más 1. Por supuesto y más 1, uno no está incluido, o tampoco es x más 1. Y luego tenemos j plus. Y ahora podemos empezar con solución M. Entonces lo primero que vamos a hacer es si o i o j es igual a 0 solo los va a llenar de ceros. I igual a 0 o j es igual a 0. Lo que vamos a hacer es llenar el LCS i, j con 0. Entonces vamos a comprobar si x en una posición específica como igual. En este caso, lo que vamos a hacer es retroceder por uno y luego vamos a almacenar la posición específica. Entonces, ¿cómo se hace eso? Ahora, recuerda que tenemos a S1 y S2 como compañero como lista. Y este caso lo que vamos a tener tan S1 como este x, y, z, y w. S2 debería ser de x, z, a y w Ahora como puedes ver aquí, tenemos el índice de este eje es 0. No obstante, si desea calcularlos en esta matriz 2D, está en el índice uno. Entonces aquí tenemos 0, 1, 2, 3, 4. Por lo que siempre que queramos trabajar con esto, sólo deberíamos decrementar por uno. Entonces para hacer eso, lo que vamos a hacer es realmente comprobar si, déjame solo hacer esto un poco más pequeño y solo despegar esto también hacerlo más pequeño. Y ahora podemos trabajar. Entonces lo primero que vamos a hacer es comprobar si lo contrario. Este carácter específico que somos, ADH es en realidad igual al carácter específico que teníamos y la segunda cadena. Entonces si s1 a una x x menos 1 específica es igual a S2 en una y específica menos 1. Este es el caso. Lo que vamos a hacer es llenar en LCS x, y, lo siento, aquí tenemos yo y j. Así que i y j. Y por supuesto aquí tenemos yo y j Así que si son iguales, vamos a hacer es tomar el uno. Ellos lo van a hacer. Entonces, ¿cómo se hace eso? A I menos 1, j menos 1 e incrementado en uno. Y no hay eso. Estamos asumiendo que estamos tomando la condición en un cisne I menos 1. J menos 1 es porque en realidad nuestras listas pensaron con el índice 0. No obstante, nuestra matriz 2D estamos calculando al principio para la cadena vacía. Entonces x aquí está a la una y está en 0 justo aquí. Entonces, ¿cómo hacemos eso? Simplemente tomamos yo minos1, que es si estás en este índice I, que es igual a uno, y solo toma esto, vamos a tomar 0 menos 1, que es 1 menos 1. Nos vamos a llevar 0 y podemos sacar esta X de la lista como uno. Por lo que tenemos j menos y y dy menos uno. Si este es el caso, entonces sólo lo vamos a computar desde la posición diagonal. Ahora, si este no es el caso, vamos a terminar con lo último que vamos a hacer es computar el máximo entre dos cosas. El primero es el de la posición izquierda y el segundo es el de arriba. Entonces, ¿cómo hacemos eso? ¿ Quién sólo va a tomar y almacenar en el LCS i y j Así que LCS, déjame simplemente escribirlo aquí. Yo sólo voy a mover esto aquí. Y voy a escribir que SES a I y J igual al máximo entre dos cosas. Entonces el máximo entre el LCS a I menos 1 y j tal como está, o el máximo, o el segundo que es LCS a I y j menos 1. Entonces eso es básicamente para Dios, esta es nuestra solución de programación dinámica. Acabamos de computar todas las implementaciones posibles usando solo una matriz 2D. Ahora si pensamos en la complejidad del tiempo, si tenemos m como, tenemos x e y como la longitud de S1 y S2, y construimos nuestra matriz 2D. Entonces como podemos ver, tenemos x, y, una complejidad temporal de nuestro código. Y entonces nuestra solución debería ser la última y nuestra matriz 2D, que es tres en este caso. Entonces eso es todo básicamente para este problema. Y el siguiente video lo vamos a implementar usando nuestros idiomas. Entonces nos vemos. 34. Aplicación de la subsecuencia común: Muy bien, entonces en este video vamos a implementar nuestra función usando Java. Entonces lo primero que voy a hacer es crear la función. Debe ser público, estático, entero. Y lo voy a nombrar subsecuencia común, y tomará los siguientes parámetros. El primero es un array llamado S1. Entonces tenemos otro es tener los índices x o x e y. ahora lo que vamos a hacer es crear nuestra matriz 2D y será de tamaño y nombrarlo a lo largo. Y en este caso, la longitud debe ser x más 1 e y más 1. Ahora podemos empezar con nuestros bucles for. Entonces como dijimos, vamos a hacer es pasar por todos estos de 0 a x y de un 0 a y. entonces para un create a for loop. Y en este caso, para ir hasta el final el acto, sí, ¿quién podría haber usado el tamaño de contenido largo o la longitud? Y el segundo en realidad estaría todo el camino hasta y Ahora lo que vamos a hacer es comprobar si soy igual a 0 o j igual a 0 adivinaría simplemente establece que el Islam debe estar en I y j debe ser igual a 0. En este caso, podríamos haberlo ignorado porque cada vez que creamos una matriz 2D a la matriz o una matriz en Java, el valor predeterminado es en realidad 0, por lo que podemos simplemente ignorar eso, pero haremos como nuestro pseudocódigo. Así que solo guárdalo aquí mismo. Ahora bien, este no es el caso. Vamos a comprobar si el S1 en I menos 1 es igual a S1 agregar j menos 1. De lo contrario, si S1 en I menos 1 es igual a la S2 en j menos uno. Si este es el caso, lo que vamos a hacer es colocar anuncios largos yo y j, el que diagonalmente a ello. ¿ Cómo lo haces? I menos 1, j menos 1. Y luego le vamos a sumar uno. Y por supuesto, si este no es el caso, todavía tienen la última condición, que es comprobar el máximo entre el de la izquierda y el de arriba. Entonces vamos a empezar a largo plazo I y j. el máximo a. Entonces math.max, el pulmón a I menos una j y largo plazo a I j menos 1. Entonces eso es todo. Básicamente este es nuestro código real. Ahora lo que vamos a hacer es simplemente devolver el último valor, que está en los X y W. Así que después de terminar de estos dos para bucles que simplemente van a devolver el pulmón, el x y Y Ahora, para probarlo, Voy a hacer es crear una función principal donde vamos a implementar o así nuestras variables entonces vamos a llamar a la función. Entonces vamos a tener S1 para que básicamente sea igual a una lista o una matriz de x. Entonces y, lo siento, solo los voy a poner como personajes, así que x, y, y luego tenemos z y w. z y w. ciérralo , y nosotros tienen S2, que también es una matriz de X, Z y W. Así que x, z, y luego tenemos a y w Ahora estamos bien. Podemos continuar con las x e y reales Así que estos son los índices que deben estar en. Entonces esta es la longitud que es de cuatro en este caso. Por lo que tanto x como y igual a 4. Ahora me olvidé de hacer es imprimir la función. Entonces voy a almacenar el resultado, la función real, y luego por supuesto voy a imprimirlo. Entonces voy a imprimir el resultado. Tenemos un tipográfico, esto es w Ahora si seguimos adelante y ejecutamos este código, lo que vamos a hacer para conseguir un CI es de tres, lo que indica que este es el número de caracteres o la longitud de su subsecuencia que tenemos. Ahora para visualizarlo, lo que vas a hacer es simplemente imprimir cada vez que entremos a este bucle. Entonces imprimo nuestra posición. Y por supuesto voy a tener espacio aquí y línea impresa aquí. Ahora si seguimos adelante y ejecutamos este código, obtenemos el mismo resultado exacto que construimos aquí mismo. Tenemos ceros, unos, dos, y el último es en realidad tres, lo que indica que este es nuestro resultado aquí mismo. Entonces eso es todo para este ejemplo. Esta es la implementación de este código usando Java. 35. Aplicación de la subsecuencia común: De acuerdo, Entonces en este video, podemos implementar nuestra función usando JavaScript. Entonces lo primero que voy a hacer es crear la función. Voy a emitir la subsecuencia común más larga. Y tomará los siguientes parámetros. Entonces tenemos S1, S2, estas son dos listas y matrices. Y también tenemos los índices y los nombramos x e yAhora podemos abrir esta función. Y ahora lo que vamos a hacer aquí, tenemos un tipográfico. Entonces esto es función. Ahora lo que vamos a hacer es crear nuestra matriz. Entonces lo nombraré. A lo mejor. Y en este caso podría ser una nueva matriz de tamaño x más 1. Y por supuesto vamos a tener una nueva matriz dentro de cada posición y hacerlo. Lo haré en un segundo. Entonces nuestro primer bucle for debería estar empezando en I igual a 0, luego todo el camino a x incluido y luego incrementado. Ahora el segundo for loop debe ser, debe comenzar en j igual a 0. J es menor o igual a y e increment j. Y por supuesto cada vez que lleguemos a una posición de I, vamos a crear una nueva matriz, y más 1. Ahora lo que vamos a hacer es comprobar si soy igual a 0 o x es, lo siento, o j es igual a 0. Entonces este es el caso. Lo que vamos a hacer es simplemente almacenar en I y j al valor de 0. Ahora bien, si este no es el caso, lo que vamos a hacer es comprobar si en las posiciones S1 y S1, S2 J menos uno. Si son iguales, entonces vamos a hacer algún tensor como si disposición, que es S1 en I menos 1 es igual a S2 en J minos1. Este es el caso. Lo que vamos a hacer es incrementar i y j por un valor más d, que está en esta posición, yo menos 1, j menos 1, que es la posición diagonal del valor específico. Ahora como vas a hacer, si no es así, vamos a tomar el máximo entre dos cosas. El primero está en la posición que está a la izquierda, y el segundo que está en la anterior. Entonces lo que vamos a hacer es empezar en esta posición específica, que es yo j El máximo entre la primera que es un largo plazo en yo menos uno y, y lo siento j. Y luego el largo yo y j menos 1, este caso. Ahora este es nuestro código. Por último, después de terminar estos dos para bucles, lo que vas a hacer es simplemente devolver el último valor que tenemos, que es el largo, ven a x e y. ahora si seguimos adelante y lo imprimimos, déjame acaba de empezar creando listas de x, y. Entonces vamos a tener z y w. Z. Entonces tenemos w. y tenemos lista de, déjame sólo nombrar las variables. Entonces tenemos variables. Y en este caso, el segundo debe ser de x, y a, lo siento, x, z y a y W. Entonces x, z, a y W. Y ahora finalmente, lo que vamos a hacer es tener los índices que están en posición 4 por ahora. Entonces var x es igual a 4, y, que también es igual a cuatro. Ahora lo que vamos a hacer es simplemente llamar a la función y bloquearla. Entonces lo voy a almacenar en el resultado. Sube y lo vamos a llamar S1, S2, x, e y. y luego finalmente, voy a cerrar sesión para que ese set. Ahora lo que vamos a hacer es dirigirnos a nuestro cmd. Y por supuesto podemos agregar nuestra programación dinámica de escritorio y JavaScript. Esto es tan malo. Y entonces por supuesto vamos a ejecutar nuestro código usando Node C dot js. Si ejecutamos nuestro código, vamos a conseguir tres como el valor final que obtuvimos de esta función. Y esta es la subsecuencia común más larga que podemos obtener. Eso es x, y, y w nada que vamos a hacer es visualizar esta función o esta matriz 2D que acabamos de crear aquí. Entonces en lugar de devolver el último valor, voy a devolver toda la matriz 2D, matriz 2D. Y si lo volvemos a ejecutar, vamos a obtener el mismo resultado exacto que construimos a mano aquí mismo. Como se puede ver, tenemos ceros, unos, y todo el camino hasta el último, que en realidad es un tres que decía, por ejemplo, por este ejemplo, esta es la implementación de este problema usando JavaScript. 36. Aplicación de la subsecuencia común: Muy bien, entonces en este video, vamos a hacer es realmente crear la función usando un Python. Entonces solo voy a crear esta subsecuencia de archivo. Y a estas alturas lo que vamos a hacer es empezar con nuestra definición o la función que vamos a usar, simplemente yendo a imagen del cáncer de pulmón y a tomar los siguientes parámetros. Por lo que tenemos S1, S2. También tienes x e y como los parámetros o los índices que vamos a utilizar. Ahora lo primero que voy a hacer es simplemente crear el sub común más largo. Y esta será la lista que vamos a usar. Y para ser realmente una lista de listas. Y el primero debe ser para I en rango de x más 1. Y entonces por supuesto, la segunda unidad estará en rango de y más 1. Entonces eso es todo. Ahora lo que vamos a hacer es empezar con nuestro for loop. Por lo que estar en el rango de 0 todo el camino hasta x más uno, ya que x más 1 no está incluido. Por lo que este es el primero, ya que para el segundo se arraigaría de 0 todo el camino hasta y más 1. Ahora lo que vamos a hacer es comprobar si i o j son iguales a 0. Si yo es igual a 0 o j es igual a 0, este es el caso. Lo que vamos a hacer es simplemente implementar o agregar en esta posición, la posición específica en I y j tiene un valor de 0. Ahora bien, si este no es el caso, vamos a comprobar si en Asuán High menos 1 es igual a S2 menos S1. Entonces S1 I menos 1 igual a S2 en j menos uno. Entonces si este es el caso, lo que vamos a hacer es simplemente tomar el valor diagonal que tenemos y almacenarlo incrementando uno por sí mismo. Subsecuencia común más larga a I menos 1, j menos 1, y vamos a añadir una a ella, y eso es todo. Ahora la última condición que vamos a tener es que si estas dos condiciones no se aplican, sólo vamos a almacenar el máximo entre dos cosas. El primero estando a la izquierda. Por lo que será el máximo entre la subsecuencia común más larga, me minos1 y j, que es la vertical, por lo que está arriba. Y el segundo será a I y luego j menos 1. Entonces eso es todo básicamente ahora, después de terminar de cavar esto a la izquierda o a la matriz, lo que vas a hacer es simplemente devolver los valores en los índices específicos. Ahora probarlo cuando vas a hacer es simplemente crear la lista. Entonces tenemos x, y, luego tenemos z y w Entonces tenemos S2, que consiste en x. tenemos z, luego tenemos a, y luego tenemos w Eso es básicamente ahora como para el hacha igual a cuatro, y igual a 4. Ahora vamos a imprimirlo. Vamos a imprimir s1, S2, x, e y Así que ahora vamos a comprobarlo. Voy a dirigirme aquí y voy a ir a por programación dinámica. Cinco, lo siento, tan dinámico, lo siento, tenemos algún error tipográfico y lo vamos a hacer es simplemente ejecutar el código. Entonces ahora lo vamos a ejecutar usando Python y Python. Tan larga subsecuencia común punto py. Entonces aquí tenemos un error. Entonces lo siento, aquí tenemos conjunto de usar LCF, tenemos LF y Python. Entonces LF, Python. Por lo que también necesitamos pagar y lo que realmente hicimos esto, llamamos a la función e imprimimos. Entonces déjame simplemente guardarlo, lo siento. Y como resultado, así que sólo voy a colocarlo y resultados de error y luego simplemente llamarlo o imprimirlo después de haber terminado de computar el valor de la sal. Ahora, después de eso, lo que vamos a hacer es simplemente ir aquí y arrastrar de nuevo. Y como podemos ver, tenemos tres, el valor final, que es la subsecuencia común más larga que podemos obtener. Ahora en lugar de devolver toda esta lista o el último elemento de la lista, voy a devolver esta matriz 2D. Ahora si retrocedes y refrescas, y como puedes ver, tenemos nuestra función, nuestra matriz 2D, y como podemos ver, es exactamente lo mismo a menos que acabemos de construirla a mano. Entonces eso es todo básicamente para este problema, el último valor es en realidad lo que nos interesa. Por lo que esta es la implementación de esta función de subsecuencia común más larga usando Python. Entonces nos vemos en el siguiente video. 37. Subsecuencia más: Hola y bienvenidos de nuevo. En este video vamos a discutir el problema de la subsecuencia creciente más larga. Entonces la idea de este problema es que se nos da una lista de enteros y vamos a devolver la longitud de la subsecuencia creciente más larga. Entonces, por ejemplo, si tenemos esta lista aquí mismo, tenemos 15, 7283, entonces lo que vamos a devolver es el número cinco, indicando la subsecuencia creciente más larga en este caso, es decir, O157 que ocho y 10. Entonces esta es la subsecuencia común más larga y vamos a devolver la longitud de la misma. Ahora, la primera vez que tengo al resolver este tipo de problemas suele ser la recursión. Dado que necesitamos encontrar la subsecuencia creciente más larga, podemos pensar en la idea de encontrar la subsecuencia creciente más larga para cada índice. Entonces, por ejemplo, si estamos aquí, la subsecuencia creciente más larga para este elemento específico es en realidad una. Ahora, aquí, lo que vamos a conseguir son dos, porque tenemos 15. Después a las siete, son tres, luego un dos. Vuelvo a dos. Ya que tenemos 12 podemos lidiar con. Entonces aquí a las ocho van a ser cuatro. Y luego por supuesto a las tres y va a ser 1, 2, y 3, que es 3, y a las diez serán cinco. Entonces esta es básicamente la idea sobre este problema. Ahora lo que vamos a hacer es comprobar cómo podemos implementarlo usando recursión. Entonces lo primero que vamos a hacer es construir el CI que vamos a tener. Entonces recordad que siempre que queramos resolver este problema, supongamos que estamos en la posición específica, que está en el número de índice 0, 1, 2, 3 y 4. Entonces estamos en el índice cuatro. ¿ Cómo podemos resolver esto para el clima específico? ¿ Cómo podemos saber que la subsecuencia común más larga para este elemento es en realidad cuatro. Entonces lo primero que vamos a hacer es crear la condición o la función para el índice para. Y lo que vamos a hacer en realidad es comprobar el máximo entre todos estos antes este índice específico y luego agregarle uno si es mayor que los números reales. Entonces, ¿cómo hacemos eso? Vamos a sumar uno al máximo entre F3 y F2, F1 y 0. Y por supuesto, todos deberían ser menores o iguales a este elemento específico en un índice específico. Entonces esto es una necesidad, y por supuesto, esta es la función que vamos a hacer ahora recuerda que esto es sólo para, uh, para, ahora si quieres computar f 0, F1, F2, y F3, vamos a hacer exactamente lo mismo aquí. Entonces por ejemplo, tenemos esto y entonces tenemos aquí tendrá que computar para F1 y F2. Y como pueden ver, lentamente estamos construyendo un árbol donde vamos a encontrar sólo para este elemento específico de cuatro, vamos a computar todos estos y luego calcularlos una y otra vez y otra vez. Y claro que vamos a hacer exactamente lo mismo para todos estos índices aquí mismo en nuestra lista. Entonces como puedes ver, esto tomará un enfoque exponencial y el tiempo de ejecución será exponencial. Entonces déjame solo mostrarte tal vez el pseudocódigo de esto. Jim. Y por supuesto vamos a tratar de optimizarlo usando programación dinámica. Entonces lo primero que vamos a hacer en este enfoque recursivo es construir la función. Por lo que simplemente lo nombraré más largo aumentando y tomará los siguientes parámetros. Voy a tener la matriz o la lección. Voy a ponerle el nombre de la lista. Y voy a tener el entero e indicando la longitud de esta lista. Ahora lo que no queremos hacer es revisar el caso base. Ahora, recuerda que debemos devolver la longitud máxima. Entonces tal vez pueda crear una variable global afuera. A lo mejor le llamaré Longitud máxima. Y en este caso, lo voy a actualizar dentro de nuestro código aquí mismo. Entonces lo que vamos a hacer es comprobar si estás en el caso base, que es n igual a 0 o 1 en este caso, lo que vamos a suponer es que vamos a empezar con uno. Por lo que realmente no necesitamos calcular 500. Vamos a empezar con F1, F2, y así sucesivamente. Entonces un fan igual a 1 es igual a uno que vamos a hacer es simplemente devolver uno, ya que es el primer elemento de la lista y debemos devolver su longitud, que básicamente es igual a uno. Y si este no es el caso, recuerda que debemos computar todos estos cuatro. Índice específico. Entonces si estamos en la U4, necesitamos calcular F3, F2, y F1. Entonces en este caso necesitamos un bucle for para hacer eso. Y para cada uno de ellos, vamos a comprobar el valor de retorno. Y si es mayor que el máximo que ya tenemos, debemos actualizar nuestro máximo. Entonces, ¿cómo hacemos eso? Simplemente vamos a definir dos variables. Nuestro resultado que vamos a conseguir. Y por supuesto, el máximo, que es el máximo actual. Entonces sólo lo llamaré Current Max. Y ahora lo que vamos a hacer es calcular esto. Entonces, ¿cómo hacemos eso? Vamos a llamar a esta función para estos índices específicos. Entonces para, vamos a empezar con el ojo todo el camino desde uno hasta el valor de n. y por supuesto podemos incrementarlo a medida que pasemos. Entonces lo que vas a hacer es obtener los resultados de esta función. Por lo que vamos a almacenar en el resultado la función de aumentar con nuestra lista y los índices. Ahora, lo siento, el índice es en realidad, ahora lo que vamos a hacer es comprobar si esta lista en el índice específico yo menos 1 y n menos uno. Si esto es menos de n menos uno, entonces deberíamos actualizarlo. Entonces, ¿cómo hacemos eso? Déjame simplemente agarrar esto y hacerlo más pequeño. Y veámoslo así. Los alimentos están en esta posición específica donde necesitamos calcular este lujo. Lo que vamos a hacer básicamente es pasar por todos estos F1, F2, y F3. Y vamos a comprobar si la posición específica es el elemento en esta lista es menor que el elemento de lujo. Entonces, por ejemplo, si estamos en esta F1 y permítanme asumir que se trata de una cuarta. Entonces este es el índice 4, 1234. Y lo que vamos a hacer en realidad es comprobar si esta posición específica es menor que ésta. Lo es. Entonces lo que vamos a hacer es comprobar la longitud máxima en este caso, cuál es? Menor a la longitud máxima en esta posición específica, que es básicamente 0 en este caso. Y así si éste es mayor que éste, si lo es, entonces podemos tomar esto incrementado en uno y ponerlo justo aquí, que es básicamente dos. Vamos a hacer exactamente lo mismo aquí cuando calculemos este. Entonces la longitud aquí es de dos. ¿ Es mayor o igual a 2? Sí, lo es. Entonces sólo tomamos dos más uno e incrementamos si este es el caso. Ahora, como pueden ver, cinco es menos que, lo siento, es mayor que dos, entonces podemos hacer eso. Por lo que tenemos dos pasos o dos condiciones a cumplir para que actualicemos este máximo actual. Entonces déjame simplemente escribirlas. lo primero que vamos a comprobar si la lista en la posición específica, que es yo menos uno, porque estamos empezando en uno y estos índices empiezan con 012, 34, etcétera. Entonces si esta lista yo menos 1 es menor que la lista específica al final que estamos tratando. Entonces n menos uno, si este es el caso y nuestro resultado más uno. Por lo que necesitamos recordar que si estás en la posición específica, solo tomamos los resultados del final incrementados en uno y luego verificamos. Entonces si este resultado es mayor que el máximo actual que tenemos, actual max, entonces lo que vamos a hacer es simplemente actualizar el máximo actual. Por lo que el máximo actual sería, en este caso, su resultado debería ser igual al resultado más 1. Entonces eso es lo básicamente así es como podemos actualizar nuestro máximo actual. Ahora, después de terminar de todo este for loop, que es de esto. De acuerdo, así que déjame dibujarlo. Lo que vamos a hacer es simplemente comprobar si el máximo actual que acabamos de obtener en este caso es mayor que la longitud máxima de la matriz total o lista total P. Si este es el caso, entonces necesitamos actualizar esta longitud máxima. Entonces F total, lo siento, si el máximo actual es mayor, entonces el maxlength. Necesitamos actualizar el deslizador. Por lo que la longitud máxima debe ser igual al máximo actual. Entonces esto es básicamente este es todo nuestro código y código. Ahora, después de terminar todos estos, lo que debemos devolver, esta función en realidad no es la maxlength, es el máximo actual. Y la razón por qué es eso? Porque déjame solo tomar todas estas y hacerlas un poco más pequeñas. Lo siento. Entonces déjame hacerlo desde aquí. Voy a tomar loop y simplemente minimizarlo y colocarlo justo aquí como antes. Y no hay que vamos a devolver este máximo actual es porque nuestra función es sobre este partido actual. Entonces recuerda, si estamos en este bucle de cuatro, lo que vamos a hacer es tomar este máximo actual de todos y cada uno de estos elementos, por lo que debemos devolver el máximo actual. No obstante, cuando tengamos que llamar a esta función no se interesará básicamente en este tipo de matemáticas. Nos interesa la versión actualizada de la maxlength con la que nos ocupamos. Entonces para decir que básicamente para este pseudocódigo, y como se puede ver, esto corre de manera exponencial ya que estamos computando este pulmón. Gracias a todas y cada vez que terminamos esto for loop y lo estamos llamando tantas veces porque es un recursivo. Entonces eso es básicamente para este video. En el siguiente video vamos a tratar de optimizarlo usando programación dinámica. Entonces nos vemos. 38. Pseudo-Code 1: De acuerdo, Entonces en este video vamos a tratar de optimizar nuestra función recursiva y usando programación dinámica. Entonces la cosa es que cada vez que estamos usando recursión es llamar a esta función una y otra vez. Por ejemplo, si estamos en esta posición específica de siempre por lo que básicamente estamos haciendo es codificar F1, F2, y F3. Y en este caso un F2, vamos a llamar a F1 y F3 vamos a llamar de nuevo a F1 y F2. Entonces, en lugar de hacer todo eso, lo que vamos a hacer es simplemente crear un bucle for que recorra todos estos juntos. Por lo que F1 y F2 y F3 y comprueba el máximo entre ellos. Y después de eso, lo vamos a devolver o simplemente colocarlo en este F4. Y por supuesto vamos a incrementarlo en uno. Entonces en lugar de usar este pseudocódigo donde voy a hacer es simplemente deshacerme de él y empezar de nuevo. Entonces con lo que vamos a empezar es realmente construir la función donde vamos a tener la lista y el índice. Y así voy a llamarlo más largo servidor SQL creciente. Tomará una lista y el entero. Y ahora lo que vamos a hacer es crear una lista donde vamos a almacenar la subsecuencia creciente más larga hasta el punto de estos índices. Entonces, por ejemplo, si estás en esta posición específica, que es el índice uno, pero vamos a almacenar en la otra lista que vamos a crear es la subsecuencia creciente más larga a este caso, que en realidad son dos . Está bien, así que déjame hacer eso aquí. Esta es nuestra segunda lista, así que la voy a nombrar L I, S, indicando que esta es la subsecuencia creciente más larga. Y será de tamaño. Y en este caso, como de costumbre, ahora ir a hacer es inicializar nuestros índices yo y nuestro máximo valor. Entonces tenemos yo, J, y Max. Y todos estos deben inicializarse a 0, por lo que máximo para estar en 0. Ahora lo que vamos a hacer es empezar con nuestro for loop, Salem, el LINCS con uno. Ya que en cada índice tenemos, por ejemplo, si estamos en el índice dos, el número mínimo aquí es uno. Por lo que la longitud de la subsecuencia mínima posible en realidad es una, y sólo incluye este número en sí. Entonces, por ejemplo, si estás en esta posición específica cinco, la longitud mínima que podríamos tener es en realidad una, que es en este cinco justo aquí. Entonces para hacer eso, voy a permitirme mirar desde todo el camino hasta n y simplemente almacenar y LINCS en la posición específica I, el valor de uno. Entonces lo que vamos a hacer en realidad es crear a un activo para bucles, pasar por todos estos elementos o todos estos elementos dentro de esta lista. Y luego en cada elemento. Entonces supongamos que estamos en esta posición específica, esa es la posición específica 3. Pero vamos a hacer es pasar por 012, conseguir el máximo entre estos. Y mientras el valor dentro de estas posiciones sea menor que el valor en dos y el máximo aquí sea mayor que éste, entonces podemos actualizarlo. Entonces lo que vamos a hacer es dejarme simplemente escribirlo aquí, pero antes de eso, déjame minimizar esto y luego continuar. Entonces lo que vamos a decir es que vamos a tener un bucle for de I till n. Y luego dentro de este for loop, vamos a empezar desde 0 todo el camino hasta I. Por supuesto, debería empezar a 0. Entonces lo que vamos a hacer es comprobar, como dijimos, si la lista en esta posición específica es mayor que la lista en, lo siento, aquí tenemos j desde 0 todo el camino hasta ISO, j igual a 0 el camino hasta i. Y aquí nos tener igual a 0 todo el camino hasta n y es menos en I es mayor que la lista. Entonces si estamos, por ejemplo, a esta derecha de aquí y tenemos un igual a 3 que supongamos que lo que vamos a hacer es mirar a través de todos estos elementos de 0 a. Y lo que vamos a hacer es comprobar si estos artículos son menores al artículo que tenemos. Entonces si este es el caso, qué vamos a hacer. Entonces lo vamos a terminar con la subsecuencia creciente más larga. Entonces supongamos que estamos en esta posición específica donde tenemos una. Vamos a tomar uno y añadir a él uno. Por lo que esto hará dos. Y recuerda que inicializamos todos estos a uno. Entonces si eres la posición específica que está en el índice tres, y vamos a tener un AD como la subsecuencia creciente más larga. Por ahora, vamos a tomar 1 más 1, que es igual a dos. Vamos a comprobar si dos son mayores que uno. Si este es el caso, entonces necesitamos actualizarlo. Entonces para hacer eso, vamos a revisar en una posición específica, que es j más 1 es mayor que el LINCS en la posición de I. Si este es el caso, entonces necesitamos actualizar nuestro LAS en atoi. Por lo que estare en, debería ser igual a S en j uno. Entonces eso es todo básicamente ahora vamos a tener una lista de estos aquí mismo. Entonces vamos a tener 1, 2, 3, 2, 4, 3, y 5. Y por supuesto, para conseguir el máximo, vamos a crear otro for loop que nos ayude a obtener el máximo de esta lista de Elias. Entonces para hacer eso, déjame solo hacer esto aquí. Y lo que vamos a hacer ahora es crear otro for loop, buceando por yo igual a 0 todo el camino hasta el final. Y vamos a encontrar un máximo sin distorsión y la variable máxima aquí mismo. Entonces si Elias en I es mayor que máximo, vamos a almacenar y al máximo este valor de Elias en I. Así que eso es todo básicamente ahora lo que vamos a devolver es simplemente devolver el máximo que acabamos de computar, que es en realidad la longitud de la subsecuencia creciente más larga que tenemos escritura. Entonces simplemente regresamos max, y ahora estamos bien. Entonces esta es nuestra función. Ahora, si queremos llamarlo, simplemente podemos ejecutarlo usando la matriz o menos que tengamos y es índice o el tamaño de la misma. Entonces eso es todo básicamente ahora, pensando en la complejidad del tiempo. Aquí, usamos dos bucles para anidados, comenzando desde 0 todo el camino hasta n. y también tenemos desde I igual j igual a 0 todo el camino hasta i, que está básicamente en el peor de los casos, vamos a tener n, Así que nosotros tienen m cuadrado aquí mismo. Y lo que realmente hicimos en el espacio auxiliar es que los vendimos en una matriz o una lista, y tomará un espacio de n. Entonces la complejidad del tiempo es O n cuadrado y la complejidad del espacio es O de n. Entonces eso es todo básicamente para este problema. En el siguiente video, lo vamos a implementar usando nuestros idiomas. 39. Aplicación de la subsecuencia: Oh, hey, entonces en este video vamos a implementar nuestra función usando Java. Entonces lo primero que voy a hacer es crear la función que podamos usar. Entonces es estática pública, y voy a nombrarla la más larga, creciente. Y se llevará el gris. Y ahora lo que vamos a hacer es crear la subsecuencia creciente más larga, que también será una matriz de tamaño n, como dijimos. Entonces vamos a inicializar nuestros índices. Y por supuesto vamos a inicializar el máximo que vamos a utilizar. Después de eso. El primero que vamos a hacer, como dijimos, es llenar la lista la subsecuencia creciente más larga con unas. Entonces vamos a empezar con yo igual a 0. Yo es menor o igual a n, y vamos a incrementarlo. Entonces lo que vamos a hacer es llenar la subsecuencia creciente más larga en la posición específica I, el valor de una. Después de eso, vamos a seguir con nuestro for loop. Por lo que tenemos dos anidados para bucles yo menos de n y yo plus. Entonces vamos a continuar con j igual a 0, j menor que i, e implementar j Como dijimos en nuestro pseudocódigo, vamos a comprobar si estos valores en la lista o la matriz en I es mayor que la matriz en j. Y vamos a comprobar si la subsecuencia creciente más larga en j más uno es mayor que la subsecuencia creciente más larga en que tengo. Este es el caso. Necesitamos actualizar la subsecuencia creciente más larga en una posición específica. Entonces si la matriz en I es mayor que la matriz en j, y como dijimos, la subsecuencia creciente más larga en j uno es mayor que la subsecuencia creciente más larga en tengo este es el caso, entonces necesitamos actualizar ella. Tan larga subsecuencia creciente, debería ser igual a la de j más uno. Entonces, básicamente, así es como podemos construir nuestro array. Ahora, después de la presión de estos dos bucles anidados para, necesitamos encontrar el máximo y almacenarlo y el valor máximo. Entonces vamos a mirar a través I igual a 0 menos que n y luego incrementar I. Entonces vamos a comprobar si el máximo es menor que la subsecuencia creciente más larga en la posición específica que este es el caso, entonces deberíamos actualizar el máximo para ser el valor que tenemos aquí mismo. Ahora después de eso, pero lo vamos a hacer es simplemente devolver el máximo que tenemos. Ahora, probémoslo. Lo que voy a hacer es crear una función principal donde voy a crear la matriz que queremos. Ahora. Entonces sea la aireación, déjame usar el mismo ejemplo exacto. Tenemos 15 728310, por lo que 157283. Y entonces tenemos la longitud n, que es básicamente la longitud, la longitud de esta matriz, 1, 2, 3, 4, 5, 6, 7. Por lo que n igual a siete. Ahora y voy a hacer es almacenar el resultado en un entero llamado resultado. Y voy a llamar a esta función, que es la secuencia creciente más larga. Y por supuesto, voy a imprimir el resultado ya que aquí, alfa, adelante y ejecutar este código. Voy a conseguir cinco como la subsecuencia creciente más larga. Y si volvemos aquí, se puede encontrar que nuestro menos consta de cinco elementos que indican que la longitud de esta lista es en realidad cinco. Entonces eso es todo básicamente ahora 400 van más allá en él y visualizan esto. Enumero la subsecuencia creciente más larga que consiste en 1232435. Lo que voy a hacer simplemente es devolver una lista o una matriz en lugar de esto. Y simplemente voy a regresar aquí la subsecuencia creciente más larga. Entonces lo que voy a hacer es almacenarlo en un resultado como este. Y voy a crear un bucle for. Y por supuesto, voy a imprimirlo como este algún espacio. Y si seguimos adelante y volvemos a ejecutar este código, vamos a conseguir 1232435. Ahora. Necesitamos justo ahí. Entonces tenemos 1232435 y como podemos ver, tenemos 1232435. Por lo que los resultados se corresponden con nuestras expectativas. Y esta es la documentación de la subsecuencia creciente más larga usando Java. 40. Aplicación de la subsecuencia en la subsecuencia: Cómo k. Entonces en este video vamos a implementar nuestra función usando JavaScript. Entonces lo primero que voy a hacer es crear nuestra función y la voy a nombrar. Voy a conseguir una lista y el entero e indicando el tamaño de esta lista. Ahora lo que vamos a hacer es crear otra lista que sea la subsecuencia creciente más larga. Voy a nombrarlo aliado. Y una matriz de y este es el tamaño. Y yo lo iba a llenar con un 1s. Entonces eso es todo básicamente. Ahora inicialicemos los índices I y j. Y luego vamos a inicializar un máximo que vamos a usar, que será igual a 0. Entonces vamos a empezar de I a 0. Lo siento, de yo igual a uno hasta yo igual a y, y recién implementado. Entonces vamos a tomar J, que es igual a 0. Entonces j de 0 a I, y por supuesto vamos a incrementarlo. Ahora vamos a hacer es lo mismo que el pseudocódigo. Vamos a comprobar si la lista en i es mayor que la menor que j. Entonces si la lista en i mayor que a, menos que j, y necesitamos comprobar si el Elias en j más uno es mayor que DALYS en i Si este es el caso, nosotros necesidad de actualizar esta alianza en I para ser igual a Ls en j más 1. Entonces después de eso, podemos devolver el máximo. Ahora, lo que vamos a hacer es buscar el máximo dentro de la lista. Entonces vamos a empezar desde 0 todo el camino hasta y, y actualizado. Entonces vamos a comprobar si max es menor que los Elias en la posición específica en la que vamos a actualizarlo. Entonces max debería ser Elias en I. Y por supuesto después de eso simplemente deberíamos devolver el máximo. Entonces eso es todo. Esto es todo. Esta es la función que vamos a usar ahora, voy a hacer es crear nuestra lista, así que ejecutarla, así que ejecutarla, así que vamos a igualar a la misma lista exacta que usamos. Tenemos 15, 7283, y 10. Por lo que 157283 y 10. Entonces tenemos n que es igual a 7, básicamente. Entonces después de eso, voy a almacenar el resultado en una variable llamada resultado. Y dos serán los más largos, aumentando como menos de 10. Después de eso, voy a cerrar sesión. Entonces voy a cerrar sesión los resultados después de eso. Lo que voy a hacer es dirigirme al mi directorio, que es la programación dinámica de JavaScript. Y luego voy a ejecutar este código usando el script Java Node. Lo siento, nodo. Y el nombre del archivo más largo aumentando sub-secuencia dot js. Y así tenemos un error aquí. Entonces veamos, dentro del módulo no encontrado. Entonces creo que lo escribí mal. La subsecuencia creciente más larga. Por lo que está aumentando nodo sub-secuencia aprender aumentando sub secuencia que no tiene forense y vamos a conseguir cinco como la subsecuencia creciente más larga que tenemos. Y si quieres visualizar realmente esta lista de la subsecuencia creciente más larga, que es 1, 2, 3, 2, 4, 3 y 5. Simplemente podemos devolver los Elias en lugar del máximo aquí. Y ahora si sigo adelante y vuelvo, lo leo de nuevo, voy a conseguir 1232435 como el resultado que esperábamos y como el resultado que realmente generamos por fin aquí. Entonces eso es todo básicamente para este problema es, es que para la subsecuencia creciente más larga usando JavaScript. 41. Aplicación de la subsecuencia: De acuerdo, Entonces esta es la implementación de Python del problema de subsecuencia en aumento más largo. Entonces lo primero que voy a hacer es definir la función. Voy a nombrar el aumento más largo. Y tomará la matriz o la lista que vamos a tener una lista simplemente nombrada. Entonces vamos a tener el índice n o el tamaño de esta lista. Lo que vamos a hacer en realidad es almacenar y una nueva lista. Voy a emitir aliado con nosotros. Nosotros vamos a almacenar una vez y ellos no lo van a ser. Y una vez. Después de eso podemos empezar con rangos o los dos para bucles. Entonces para I en rango de 1 n, Vamos a ir de j en rango de 0 hasta i. Y vamos a revisar, como dijimos antes, dentro de pseudocódigo, podemos comprobar si la lista en i es mayor que la listada j Así que déjame escribirla abajo muy rápido. Por lo que menos en yo es mayor que la lista L, j. Y también tenemos, lo siento, y vamos a tener el LINCS. J plus 1 es mayor que el sombrero LAS I. J más 1 es en realidad mayor que el Elias al i f Este es el caso. Entonces lo que vamos a hacer es actualizar el ALS en L2. Añadiré j más 1. Después de eso, podemos definir el máximo que vamos a utilizar. Por lo que el máximo debe ser al primero 0. Entonces vamos a echar un vistazo a toda la lista de Elias, que tiene la subsecuencia creciente más larga para cada uno. Y eso es, y en este caso para yo en rango de 0 todo el camino. Y así simplemente voy a escribir, y si el máximo es igual, último más grande que la variable máxima real que tenemos aquí, entonces necesitamos actualizar esta aquí. Entonces, ¿cómo hacemos eso? Simplemente podemos escribir el máximo es menor que el LSAT. Voy a actualizar el máximo para estar en una posición específica i. Después de eso, lo que simplemente vamos a volver como el máximo que creamos en este momento. Ahora para comprobarlo, lo que voy a hacer es crear una lista, que es exactamente lo mismo que nosotros, oye, Así que tenemos 15728310. Entonces vamos a tener dentro de esta lista 15, 7283, y 10. Entonces vamos a tener n, que es igual a 7. Después de eso, voy a almacenar un resultado, la subsecuencia creciente más larga con menos y n. y por supuesto voy a imprimir el resultado. Ahora, echa un vistazo. Lo que voy a hacer es simplemente dirigirme al escritorio CMD y al directorio de programación dinámica de Python. Y voy a ejecutar este código. Por lo que el aumento más largo de subsecuencia punto py. Entonces aquí tenemos un error porque creamos un resultado variable y no podemos usarlo en Python. Entonces ahora si retrocedemos y refrescamos, como pueden ver aquí, vamos a conseguir cinco como la subsecuencia creciente más larga dentro de esta subsecuencia de enteros. Ahora si queremos ver toda la lista, eso es lo que, el 1, 2, 3, 2, 4, 3 y 5. Simplemente podemos volver de nuevo el máximo, sólo el aliado como, tal y como es. Ahora si regresas y lo vuelves a ejecutar, vamos a conseguir esta lista 1, 2, 3, 2, 4, 3 y 5. Por lo que estas son la subsecuencia creciente real más larga para todos y cada uno de los índices dentro de nuestra lista de entrada. Por lo que no tenía 0 en los ingredientes más largos. El músculo oblicuo es uno, índice , uno, es 23. Y aquí tenemos dos porque nosotros, en la posición específica, que es que somos, tenemos que hacerlo, la subsecuencia creciente más larga es 12 y su longitud es en realidad 2. Entonces eso es todo básicamente ahora lo que realmente hicimos al final es computar el máximo de estos, que son cinco, y devolverlo como nuestro resultado. Entonces eso es todo básicamente para este problema. Esta es la implementación de la subsecuencia creciente más larga usando Python. 42. Proyecto: De acuerdo, Entonces en el último problema, resolvimos la longitud de la subsecuencia creciente más larga usando una complejidad de tiempo de O n cuadrado, como se puede ver aquí. Entonces lo que realmente hicimos es encontrar la longitud de la subsecuencia más larga dentro de una lista de enteros como este, y es el más largo es 15, 7, 8, 10, y su longitud es en realidad 5. Ahora lo que se supone que hay que hacer es mejorar la hora de solución para encontrar una manera mejorada en cuanto a la complejidad del tiempo. Por lo que nuestra complejidad del tiempo es O n cuadrado. Tu tarea es mejorarlo en o e iniciar sesión. Entonces lo que debes hacer es pensar en un método e implementado usando tu lenguaje de programación favorito y mejorar la solución en términos de complejidad del tiempo. Ahora bien, ten en cuenta a la hora de lidiar con tal problema, puedes sacrificar la complejidad del espacio para tener una mejor complejidad del tiempo. Entonces, por ejemplo, si no estamos usando una matriz o si usamos una lista, podemos usar más. Puedes usar matriz 2D, un HashMap o cualquier cosa de ese tipo con el fin de mejorar tu complejidad del tiempo. Por lo que solo nos estamos centrando en la complejidad del tiempo e ignorando el espacio por ahora. Entonces eso es todo. Esta es tu tarea. Espero que lo disfruten. Puntuación, y no te olvides de dejar caer tu proyecto en la sección de proyectos. Y buena suerte y disfruta. 43. Conclusión: Entonces engratos, Acabas de terminar este curso. Esto es sólo una recapitulación rápida sobre lo que cubrimos en él. Entonces lo primero que hicimos fue usar la secuencia de Fibonacci para definir la memorización y la tabulación y aprender las diferencias entre ellas. Entonces resolvemos algunos de los algoritmos de programación dinámica más famosos. Y al principio dibujamos los árboles, sus IRA o matriz 2D junto al pseudocódigo que vamos a utilizar. Después de eso los implementamos usando nuestros idiomas. Entonces ahora, solo consejos rápidos. Siempre que vendiste este tipo de problemas de programación dinámica, necesitas resolverlo por un 100 sediento tratado de llegar a la solución que funciona, tal vez por recursión. Y por supuesto, después de eso, puedes empezar optimizándolo y encontrando una mejor solución ya sea usando la memoización y la tabulación. Entonces con eso dicho, este es el final de nuestro curso. Espero que lo hayan disfrutado. Por último, si tiene alguna pregunta o sugerencia o mejoras, entonces yo puedo hacer el discurso. O si quieres que cubra problemas extra, por favor pregúntalo en la sección de preguntas y respuestas. Y sería genial dejar una reseña para poder mejorar este curso. Entonces gracias por estar aquí y buena suerte en tu próximo viaje.