Cambio de monedas y escalera de coste mínimo
Formule las recurrencias de coin-change y min-cost-climbing-stairs, elija la dirección correcta de DP y siga manualmente la tabla.
Cambio de monedas y escalera de coste mínimo es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 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.
Coin Change: El problema
Coin Change (LeetCode #322) le proporciona denominaciones de monedas y una cantidad objetivo. Encuentre el número mínimo de monedas necesario para formar exactamente esa cantidad. Tiene monedas ilimitadas de cada denominación. Esta es una variante de la mochila ilimitada: cada elemento (moneda) se puede usar cualquier número de veces. Es uno de los problemas de DP más importantes porque pone a prueba su capacidad para formular una recurrencia desde cero.
# Problem examples:
# coins=[1,5,6,9], amount=11 -> 2 (5+6 or 2+9? no: 5+6=11 YES)
# coins=[2], amount=3 -> -1 (impossible)
# coins=[1,2,5], amount=11 -> 3 (5+5+1)
# coins=[186,419,83,408], amount=6249 -> 20
# Key choices:
# - Try each coin denomination at each step
# - Minimum coins = 1 + minimum(coins to make amount - coin)
# - If amount < 0: impossible
# - If amount = 0: done (0 coins)
print('Coin change: unbounded knapsack, find minimum count')Coin Change: Derivación de la recurrencia
Defina dp[i] como el número mínimo de monedas necesarias para formar la cantidad i. Para cada cantidad i, pruebe a usar cada moneda c: si i >= c, entonces dp[i] = min(dp[i], 1 + dp[i-c]). El «1» representa la moneda que acabamos de usar; dp[i-c] es la solución óptima para la cantidad restante. Esto supone que hay monedas infinitas. Caso base: dp[0] = 0. Inicialice todas las demás entradas con infinito para representar que todavía «no se pueden alcanzar».
def coin_change(coins, amount):
# dp[i] = min coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin and dp[i - coin] != float('inf'):
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2
print(coin_change([2], 3)) # -1
print(coin_change([1, 2, 5], 11)) # 3
# Trace dp for coins=[1,5] amount=6:
# dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1, dp[6]=2Coin Change: Por qué falla greedy
Greedy (elegir siempre la moneda de mayor valor que encaje) falla en Coin Change. Ejemplo: coins=[1, 3, 4], amount=6. Greedy elige 4 y después 1+1, lo que da 3 monedas. La solución óptima es 3+3, con 2 monedas. Greedy funciona con denominaciones estándar (1, 5, 10 y 25 centavos) porque casualmente cumplen la propiedad greedy. Pero para conjuntos de monedas arbitrarios se necesita DP. Este es un punto clásico en las entrevistas: afirmar que greedy falla y explicar por qué demuestra una sólida capacidad de análisis.
# Greedy failure example:
# coins=[1,3,4], amount=6
# Greedy: 4 (rem=2), 1 (rem=1), 1 (rem=0) -> 3 coins
# Optimal: 3 (rem=3), 3 (rem=0) -> 2 coins
def coin_change_greedy_wrong(coins, amount):
coins_sorted = sorted(coins, reverse=True)
count = 0
for coin in coins_sorted:
while amount >= coin:
amount -= coin
count += 1
return count if amount == 0 else -1
print('Greedy:', coin_change_greedy_wrong([1,3,4], 6)) # 3 (WRONG)
print('DP: ', coin_change([1,3,4], 6)) # 2 (CORRECT)Coin Change II: Contar las formas
Coin Change II (LeetCode #518) pide el número de formas de formar la cantidad, no el número mínimo de monedas. La recurrencia cambia: en lugar de usar min, se usa una suma. dp[i] += dp[i-coin] para cada moneda. El orden de llenado es importante: para contar cada combinación una sola vez, recorra las monedas en el bucle externo y las cantidades en el bucle interno. Invertir los bucles cuenta permutaciones en lugar de combinaciones (un problema diferente).
def coin_change_ii(coins, amount):
# dp[i] = number of ways to make amount i
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0: use no coins
# Outer loop: coins -- ensures each coin type processed once
for coin in coins:
# Inner loop: amounts
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
print(coin_change_ii([1, 2, 5], 5)) # 4: [1,1,1,1,1],[1,1,1,2],[1,2,2],[5]
print(coin_change_ii([2], 3)) # 0: impossible
print(coin_change_ii([10], 10)) # 1
# Key: coin outer, amount inner = COMBINATIONS (unordered)
# Reverse (amount outer, coin inner) = PERMUTATIONS (ordered)Min-Cost Staircase: El problema
Min Cost Climbing Stairs (LeetCode #746) presenta una escalera en la que cada escalón tiene un coste. Puede subir 1 o 2 escalones cada vez. Encuentre el coste mínimo para llegar a la cima (un escalón más allá del último). Puede empezar gratis en el escalón 0 o en el escalón 1. Este problema combina elegantemente la recurrencia de subir escaleras con el patrón de minimización de costes de Coin Change, por lo que constituye un puente natural entre ambos.
# cost = [10, 15, 20]
# Pay cost[i] to leave step i
# You can step to i+1 or i+2
# Goal: reach top (index 3) with minimum cost
# Path options:
# Start at 0: cost 10, go to 2: cost 20, done -> 30
# Start at 1: cost 15, go to 3: done -> 15 <- OPTIMAL
# Start at 0: cost 10, go to 1: cost 15 -> 25
cost = [10, 15, 20]
# Optimal: start at step 1, pay 15, jump to top -> cost = 15
print('Expected:', 15)Min-Cost Staircase: La recurrencia
Defina dp[i] como el coste mínimo para llegar al escalón i. Llega al escalón i pagando cost[i-1] (desde el escalón i-1) o cost[i-2] (desde el escalón i-2). Por tanto, dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Casos base: dp[0] = 0 (se empieza antes de la escalera, gratis), dp[1] = 0 (también se puede empezar en el escalón 1, gratis). La respuesta es dp[n], donde n = len(cost).
def min_cost_climbing_stairs(cost):
n = len(cost)
# dp[i] = minimum cost to reach step i
# Steps 0 to n; step n is the top (goal)
dp = [0] * (n + 1)
# dp[0] = 0 (free to start here)
# dp[1] = 0 (free to start here)
for i in range(2, n + 1):
dp[i] = min(dp[i-1] + cost[i-1], # step from i-1
dp[i-2] + cost[i-2]) # jump from i-2
return dp[n]
print(min_cost_climbing_stairs([10, 15, 20])) # 15
print(min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1])) # 6Min-Cost Staircase: Optimización del espacio
Como dp[i] solo depende de dp[i-1] y dp[i-2], podemos reducir el espacio a O(1) usando dos variables, igual que en Fibonacci. Sustituya el array por prev2 y prev1. Actualícelas en cada paso. Esta es una optimización estándar de una sola línea que los entrevistadores esperan después de presentar la solución con la tabla O(n). Menciónela siempre de forma proactiva: «Podemos reducir esto a un espacio O(1) porque solo necesitamos los dos últimos valores».
def min_cost_optimised(cost):
n = len(cost)
prev2, prev1 = 0, 0 # dp[0] and dp[1]
for i in range(2, n + 1):
curr = min(prev1 + cost[i-1], prev2 + cost[i-2])
prev2, prev1 = prev1, curr
return prev1
print(min_cost_optimised([10, 15, 20])) # 15
print(min_cost_optimised([1,100,1,1,1,100,1,1,100,1])) # 6
# Alternative: directly use cost array as rolling storage
def min_cost_v2(cost):
n = len(cost)
for i in range(2, n):
cost[i] += min(cost[i-1], cost[i-2])
return min(cost[-1], cost[-2])
from copy import deepcopy
cost_test = [10,15,20]
print(min_cost_v2(deepcopy(cost_test))) # 15Formulación alternativa de DP
Algunos problemas tienen varias formulaciones de DP válidas. Para Min-Cost Staircase, puede definir dp[i] como el coste mínimo para SALIR del escalón i (pagar cost[i] y elegir pasar a i+1 o i+2). Entonces dp[i] = cost[i] + min(dp[i+1], dp[i+2]), llenando la tabla de derecha a izquierda, y la respuesta es min(dp[0], dp[1]). Ambas formulaciones son correctas. Practique explicar qué formulación ha elegido y por qué; esto demuestra fluidez con DP.
def min_cost_alternative(cost):
n = len(cost)
# dp[i] = min cost when starting FROM step i
# Fill right to left
dp = cost[:] + [0] # dp[n] = 0 (already at top)
for i in range(n - 1, -1, -1):
# Pay cost[i], then choose i+1 or i+2
if i + 2 <= n:
dp[i] = cost[i] + min(dp[i+1], dp[i+2])
else:
dp[i] = cost[i] + dp[i+1]
# Can start at step 0 or step 1
return min(dp[0], dp[1])
print(min_cost_alternative([10, 15, 20])) # 15
print(min_cost_alternative([1,100,1,1,1,100,1,1,100,1])) # 6Relación entre Coin Change y Min-Cost Staircase
Coin Change y Min-Cost Staircase son casos del mismo patrón de DP: en cada paso, se elige una opción de un conjunto finito y se optimiza un objetivo a lo largo de la secuencia de decisiones. Las diferencias son meramente superficiales: Coin Change registra una cantidad (suma 1 por cada moneda) y la escalera registra un coste (suma cost[i] por cada paso). Reconocer esta estructura compartida permite resolver nuevos problemas de DP relacionándolos con plantillas conocidas.
# Shared pattern:
# dp[state] = optimise(dp[prev_state_1] + cost_1,
# dp[prev_state_2] + cost_2, ...)
# Coin change: dp[amount] = min(1 + dp[amount - coin] for coin in coins)
# Min stair: dp[step] = min(cost[step-1]+dp[step-1], cost[step-2]+dp[step-2])
# Max path sum: dp[cell] = max(dp[top], dp[left]) + grid[cell]
# House robber: dp[house] = max(dp[house-1], dp[house-2] + value[house])
# All four are the SAME pattern with different:
# - State representation
# - Number of choices per state
# - Objective (min/max)
# - Transition cost
print('DP pattern: state + choices + objective + cost = template')Número mínimo de cuadrados perfectos
Perfect Squares (LeetCode #279) pide el número mínimo de cuadrados perfectos (1, 4, 9, 16, ...) cuya suma sea n. Es exactamente Coin Change, donde las «monedas» son números cuadrados perfectos. Genere todos los cuadrados perfectos hasta n y después ejecute Coin Change. DP ofrece un tiempo O(n * sqrt(n)). El teorema de los cuatro cuadrados de Lagrange nos dice que la respuesta es como máximo 4, lo que también permite un enfoque matemático O(sqrt(n)); pero la solución esperada es DP.
import math
def num_squares(n):
# Generate all perfect squares up to n
squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)]
# Coin change with squares as 'coins'
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
for sq in squares:
if i >= sq:
dp[i] = min(dp[i], 1 + dp[i - sq])
return dp[n]
print(num_squares(12)) # 3: 4+4+4
print(num_squares(13)) # 2: 4+9
print(num_squares(1)) # 1: 1Depuración de DP: Errores comunes
Errores comunes de DP: caso base incorrecto (dp[0] se establece incorrectamente), orden de llenado incorrecto (se accede a un valor que todavía no se ha calculado), desfase en la definición del estado (dp[i] es el coste PARA llegar a i frente al coste para salir de i) y no devolver -1 cuando queda infinito (casos imposibles). Pruebe siempre los casos más sencillos (entrada vacía, un solo elemento, target=0) antes de probar entradas más grandes.
# Common DP debugging checklist:
# 1. Base case: what is dp[0]? dp[1]? Are they correct?
# 2. State definition: write it in English before coding
# 3. Recurrence: trace manually on a 3-element example
# 4. Fill order: dependency arrows point left/up? Fill left/up first
# 5. Infinity check: return -1 or 0 when dp[target] == inf?
# 6. Array bounds: dp has size n+1 for 0..n, or n for 0..n-1?
# Quick test template:
def test_coin_change():
assert coin_change([1], 0) == 0 # base case
assert coin_change([1], 1) == 1 # single coin
assert coin_change([2], 3) == -1 # impossible
assert coin_change([1,5,6,9], 11) == 2
print('All tests passed!')
test_coin_change()Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: DP de mínimo de monedas para Coin Change (mochila ilimitada) y por qué falla greedy, Coin Change II para contar combinaciones con las monedas en el bucle externo y las cantidades en el interno, y Min-Cost Staircase con formulaciones tanto de izquierda a derecha como de derecha a izquierda. A continuación exploraremos patrones de DP 1D con House Robber, el algoritmo de Kadane y Word Break.
Preguntas frecuentes
¿La lección «Cambio de monedas y escalera de coste mínimo» es gratis?
Sí — el texto completo de «Cambio de monedas y escalera de coste mínimo» 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 «Cambio de monedas y escalera de coste mínimo»?
Formule las recurrencias de coin-change y min-cost-climbing-stairs, elija la dirección correcta de DP y siga manualmente la tabla. 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 4 de 4.
¿Cuánto tiempo toma la lección «Cambio de monedas y escalera de coste mínimo»?
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
- Reconocimiento de DP: subproblemas superpuestos
- DP top-down con memoización
- DP bottom-up con tabulación
- Cambio de monedas y escalera de coste mínimo