Skip to content

Simulacro 03 Coin Change

Jump to bottom
Joel Alvarez edited this page Jul 12, 2026 · 1 revision

Simulacro 03: Coin Change

Objetivo

Practicar programación dinámica de minimización, definiendo estado, transición y centinela antes de codificar.

Duración total: 45 minutos.

Reglas

  • No consultar src/patterns/dynamic_programming.rs antes de terminar.
  • Escribir primero los casos de prueba.
  • Definir explícitamente qué significa dp[amount].
  • Al terminar, registrar retro en notes/review-queue.md.

Enunciado

Dado un arreglo de denominaciones coins y un amount, devolver el menor número de monedas necesario para formar ese monto.

Si no se puede formar el monto, devolver -1.

Se puede usar cada moneda tantas veces como sea necesario.

Ejemplos

coins = [1, 2, 5]
amount = 11
resultado = 3

coins = [2]
amount = 3
resultado = -1

coins = [1]
amount = 0
resultado = 0

Preguntas de Clarificación

Antes de codificar, responder:

  • ¿Las monedas pueden repetirse ilimitadamente?
  • ¿Puede amount ser 0?
  • ¿Puede haber monedas con valor 0 o negativo?
  • ¿Se necesita devolver combinación o solo cantidad mínima?

Plan Esperado

  1. Definir dp[x] como la menor cantidad de monedas para formar x.
  2. Inicializar dp[0] = 0.
  3. Usar un centinela mayor que cualquier respuesta posible.
  4. Para cada monto, probar cada moneda que no exceda el monto.
  5. Convertir el centinela final a -1 si el monto sigue inalcanzable.

Invariantes

  • dp[0] siempre es 0.
  • Si dp[x] es centinela, x todavía no es alcanzable.
  • La transición dp[x] = min(dp[x], dp[x - coin] + 1) solo es útil si x - coin ya es alcanzable.

Tests Mínimos

Crear o reescribir tests equivalentes a:

#[test]
fn returns_minimum_number_of_coins() {
    assert_eq!(coin_change(vec![1, 2, 5], 11), 3);
}

#[test]
fn returns_minus_one_when_amount_cannot_be_formed() {
    assert_eq!(coin_change(vec![2], 3), -1);
}

#[test]
fn returns_zero_for_zero_amount() {
    assert_eq!(coin_change(vec![1, 2, 5], 0), 0);
}

Señales de Buena Solución

  • Complejidad temporal: O(amount * coins).
  • Complejidad espacial: O(amount).
  • Usa centinela claro para estados inalcanzables.
  • No confunde este problema con knapsack 0/1.

Retro Después del Simulacro

Completar:

Dimensión Puntaje 1-5 Evidencia
Clarificación
Enfoque
Implementación
Pruebas
Comunicación

Notas:

  • Qué salió bien:
  • Qué falló:
  • Error que se repite:
  • Acción de repaso:
  • Fecha para repetir:

Clone this wiki locally