Escaleras y combinaciones de monedas
Construya desde cero recurrencias clásicas unidimensionales
Escaleras y combinaciones de monedas es una lección gratuita de Competitive Programming Academy 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 Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Conozca el problema de las escaleras
Puede subir 1 o 2 escalones cada vez. ¿De cuántas formas se puede llegar al escalón n? Esta clásica DP 1D es Fibonacci disfrazado.
Encuentre la recurrencia
Para estar en el escalón i, tuvo que llegar desde i-1 o desde i-2. Por tanto, dp[i] = dp[i-1] + dp[i-2], sumando los dos últimos movimientos.
dp[i] = dp[i-1] + dp[i-2]Establezca los casos base
Hay una forma de permanecer en el suelo y una forma de llegar al escalón 1. Esos casos base inicializan toda la tabla.
dp[0], dp[1] = 1, 1Rellene la tabla y lea la respuesta
Avance hacia arriba con un bucle y la última celda contendrá el recuento. La solución completa es un pequeño bucle de tabulación.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Reduzca a dos variables
Solo necesita los dos últimos valores, así que puede eliminar el arreglo. Esta versión con espacio O(1) es la favorita en los concursos.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bPase a las combinaciones de monedas
Dado un conjunto de valores de monedas, cuente las formas de obtener la cantidad A. Aquí el orden no importa, así que contamos combinaciones, no secuencias.
coins = [1, 2, 5]La tabla de combinaciones
Sea dp[x] el número de formas de formar x. Comience con una forma de obtener cero: el conjunto vacío de monedas.
dp = [0]*(A+1)
dp[0] = 1Coloque las monedas en el bucle exterior
Coloque el bucle de monedas en el exterior del bucle de cantidades. Este orden cuenta cada combinación exactamente una vez, nunca las permutaciones.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Combinaciones frente a permutaciones
Cambie el orden de los bucles y, en su lugar, contará formas ordenadas. La anidación de los bucles, por sí sola, cambia el significado de la respuesta.
Variante de cambio de monedas mínimo
Para obtener el menor número de monedas, guarde un mínimo en lugar de una suma. Inicialice con infinito y tome 1 más el mejor subproblema.
dp[x] = min(dp[x], dp[x-c] + 1)Un patrón, muchas formas
Las escaleras y las monedas comparten una estructura: cada estado suma o minimiza entre algunos estados anteriores. Si detecta eso, el código prácticamente se escribe solo.
Comprobación rápida
Al contar combinaciones de monedas, ¿qué orden de bucles evita los duplicados?
Resumen: sume los últimos movimientos
Ahora puede resolver las escaleras y el recuento de monedas con una recurrencia 1D. Cada respuesta suma algunos estados anteriores, y el orden de los bucles decide entre combinaciones y permutaciones.
Preguntas frecuentes
¿La lección «Escaleras y combinaciones de monedas» es gratis?
Sí — el texto completo de «Escaleras y combinaciones 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 Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Escaleras y combinaciones de monedas»?
Construya desde cero recurrencias clásicas unidimensionales Practicas Competitive Programming Academy 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 Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy 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 «Escaleras y combinaciones 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 Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy 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
- Memoización frente a tabulación
- Defina el estado y la transición
- Escaleras y combinaciones de monedas
- Subsecuencia creciente más larga