DP de mochila ilimitada y cambio de monedas
Use los elementos cualquier número de veces
DP de mochila ilimitada y cambio de monedas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Objetos ilimitados
En la mochila ilimitada, cada objeto puede tomarse tantas veces como desee. Piense en monedas de una máquina expendedora, no en un montón fijo de objetos.
El pequeño cambio
En comparación con 0/1, solo cambia la dirección del bucle. Para objetos ilimitados, recorra la capacidad hacia delante, de menor a mayor.
La reutilización hacia delante es la clave
Al avanzar hacia delante, dp[w - coin] puede incluir ya este mismo objeto. Esta reutilización intencionada es precisamente lo que permite tomarlo de nuevo.
Conozca el cambio de monedas
El clásico problema de cambio de monedas pide el menor número de monedas cuya suma sea una cantidad. Es una DP ilimitada con un mínimo en lugar de un máximo.
Defina el estado
Sea dp[a] el menor número de monedas necesario para obtener la cantidad a. Comience estableciendo dp[0] = 0, ya que para obtener cero no se necesitan monedas.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Use infinito para lo imposible
Inicialice con infinito las cantidades inalcanzables. Si una cantidad sigue siendo infinita al final, ninguna combinación de monedas puede formarla.
La transición
Para cada moneda, intente mejorar todas las cantidades que pueda alcanzar. Use una moneda más que la cantidad menor restante.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Por qué se usa el orden hacia delante
Recorrer las cantidades de menor a mayor permite que dp[a - coin] ya cuente esta moneda. Así es como una sola moneda contribuye varias veces.
Cuente las formas en su lugar
Sustituya mínimo+1 por una suma para contar el número de formas de obtener cada cantidad. Colocar el bucle de monedas en el exterior evita contar dos veces los órdenes.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Lea el resultado
La respuesta se encuentra en dp[amount]. En la versión de mínimo, un valor infinito significa que es imposible formar el objetivo.
0/1 frente a ilimitada
Recuerde el único cambio: recorrer la capacidad hacia atrás significa usar cada objeto una vez; hacia delante, un número ilimitado de veces. La misma tabla, con recorridos opuestos.
Comprobación rápida
Ponga a prueba qué hace que una mochila sea ilimitada.
Resumen
Ha cambiado el bucle hacia delante para permitir la reutilización ilimitada y ha creado el cambio de monedas con mínimo para obtener el menor número de monedas o con suma para contar todas las formas. 💰
Preguntas frecuentes
¿La lección «DP de mochila ilimitada y cambio de monedas» es gratis?
Sí — el texto completo de «DP de mochila ilimitada y cambio de monedas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «DP de mochila ilimitada y cambio de monedas»?
Use los elementos cualquier número de veces Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «DP de mochila ilimitada y cambio de monedas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Mochila 0/1: elegir o dejar
- Mochila optimizada en espacio
- DP de mochila ilimitada y cambio de monedas
- Suma de subconjuntos y partición