Sesión 41: CTCI 8.11 & Grokking Cap. 9 (Parte 2) — Coin Change y Mochila Ilimitada (LC 322 & LC 518)#

Navegación rápida:

• ← Sesión 40: Grokking Ch9 — DP: Knapsack 0/1 y Subset Sum
• Sesión 42: Grokking Ch9 — DP: LCS, LIS y Box Stacking →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_41.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión profundizamos en el arquetipo de la *Mochila Ilimitada (Unbounded Knapsack) a través del clásico problema de Coin Change (Dar Cambio)*, desmitificando cómo una simple inversión en el orden de los bucles transforma combinaciones únicas en permutaciones ordenadas. Consulta el Glosario Maestro y la Guía de Diagramas.

Mochila Ilimitada (Unbounded Knapsack)#

• (a) En palabras simples (intuición): En una tienda de abarrotes hay dispensadores automáticos con monedas de \1,2 y \5. Las monedas nunca se acaban: puedes sacar tantas monedas de5 como necesites, o todas de \$1 si lo prefieres. A diferencia de la Mochila 0/1 donde cada objeto era único y se agotaba al meterlo, aquí la disponibilidad de cada elemento es infinita.
• (b) Definición técnica paso a paso: Variante del problema de la mochila donde la multiplicidad de cada elemento es un entero no negativo arbitrario xᵢ ∈ {0, 1, 2, …}. En la tabulación unidimensional, el bucle de acumulación de monto itera en sentido directo (ascendente, desde el valor de la moneda hasta el objetivo A), permitiendo que el estado dp[a] consulte y encadene valores ya actualizados con esa misma moneda en dp[a - c].
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con un vector plano Vec<usize> o Vec<u64> de longitud A + 1, actualizándose mediante iteradores estándar: for a in coin..=amount { dp[a] += dp[a - coin]; }.
• (d) Error típico de Junior: Usar un bucle en reversa .rev() por reflejo condicionado tras haber aprendido Mochila 0/1; en la Mochila Ilimitada el bucle en reversa impediría usar la misma moneda más de una vez.

Problema del Mínimo Número de Monedas (LC 322)#

• (a) En palabras simples (intuición): Tienes que pagar \11 en la caja y quieres entregar la menor cantidad de monedas metálicas para no cargar peso en tu bolsillo. Con monedas de1, \2 y5, podrías entregar once monedas de \1, pero lo óptimo es dar solo 3 monedas: dos de5 y una de \$1.
• (b) Definición técnica paso a paso: Problema de optimización donde se busca minimizar la cardinalidad del multiconjunto de monedas cuya suma sea exactamente igual a A:

Se inicializa con dp[0] = 0 y dp[a] = ∞ (o centinela A + 1) para a > 0. Si al finalizar dp[A] > A, se retorna None o -1 indicando imposibilidad matemática.

• (c) Cómo funciona en Rust (memoria y tipos): Se modela de manera idiomática retornando Option<usize>, evitando valores centinela mágicos como -1 o flotantes infinitos.
• (d) Error típico de Junior: Intentar resolverlo con un algoritmo codicioso (greedy), ordenando de mayor a menor denominación; esto falla con sistemas de monedas no canónicos (por ejemplo, con denominaciones [1, 3, 4] para monto 6, Greedy entrega 4 + 1 + 1 = 3 monedas, cuando la solución óptima es 3 + 3 = 2 monedas).

Número de Formas / Combinaciones Únicas (CTCI 8.11 / LC 518)#

• (a) En palabras simples (intuición): Le preguntas al cajero: "¿De cuántas formas distintas puedo pagar \3 con monedas de1 y \2?". El cajero responde: "De 2 formas: pagar con tres de1, o pagar con una de \2 y una de1". El orden en que pongas las monedas sobre el mostrador no cambia la forma: poner \1 y luego2 es la misma transacción que poner \2 y luego1.
• (b) Definición técnica paso a paso: Conteo de combinaciones no ordenadas cuya suma acumulada iguala A. Se logra forzando una relación de orden canónica sobre las monedas, garantizando que cada moneda solo se procese en una fase única del algoritmo sin reintroducir denominaciones menores.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con un vector dp: Vec<u64> de tamaño A + 1 inicializado con dp[0] = 1, procesando las monedas en el bucle externo.
• (d) Error típico de Junior: Colocar el monto en el bucle externo, contando permutaciones y obteniendo conteos inflados que provocan fallos en pruebas unitarias.

Permutaciones Ordenadas de Monedas (LC 377 / Combination Sum IV)#

• (a) En palabras simples (intuición): Imagina que en un videojuego disparas ráfagas de botones para acumular 3 puntos de daño. Si tienes combos de 1 punto y 2 puntos, presionar [Golpe 1, Golpe 2] activa una animación distinta a presionar [Golpe 2, Golpe 1]. Aquí el orden secuencial importa y se cuentan como 2 caminos diferentes.
• (b) Definición técnica paso a paso: Conteo de todas las secuencias ordenadas de elementos que suman exactamente A. Para cada monto intermedio a, cualquier moneda c ≤ a puede constituir el último elemento de la secuencia, por lo que:

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa colocando el monto en el bucle externo y recorriendo todas las monedas en el bucle interno para cada monto a.
• (d) Error típico de Junior: Confundir el nombre del problema en LeetCode ("Combination Sum IV" es en realidad un problema de Permutaciones ordenadas).

El Dilema del Bucle Externo vs Interno (Combinaciones vs Permutaciones)#

• (a) En palabras simples (intuición):
• Monedas Afuera: Abres la caja de monedas de \1 y repartes1 a todos los montos posibles. La cierras con llave y abres la caja de \2. Como la caja de1 ya está cerrada, jamás podrás poner un \1 después de un2. Todo queda ordenado naturalmente.
• Monto Afuera: Para cada monto de dinero, tienes todas las cajas abiertas frente a ti y pruebas lanzar cualquier moneda al final.
• (b) Definición técnica paso a paso: Principio algebraico de programación dinámica:
• Monedas en Bucle Externo: Proyecta el espacio de estados a través de una cadena de Markov donde el índice de moneda es monótonamente creciente (c₁ ≤ c₂ ≤ … ≤ cₖ), eliminando simetrías permutacionales ⟹ Combinaciones.
• Monto en Bucle Externo: El grafo de estados evalúa todos los arcos entrantes hacia el nodo a desde los predecesores a - c, sumando todos los caminos dirigidos en el DAG ⟹ Permutaciones.
• (c) Cómo funciona en Rust (memoria y tipos): Ambas variantes consumen exactamente la misma memoria (O(A) en Heap), pero el orden de los ciclos anidados produce salidas matemáticas enteramente diferentes.
• (d) Error típico de Junior: Pensar que la diferencia requiere estructuras de datos complejas (árboles o backtracking con HashSet), cuando solo radica en la inversión de dos líneas for.

Reconstrucción de Monedas con Vector de Predecesores (last_coin)#

• (a) En palabras simples (intuición): Cada vez que logras romper un récord y alcanzar un monto usando menos monedas, anotas con lápiz en una ficha: "Para llegar aquí, la última moneda que tiré fue la de \5". Al final, solo tienes que leer la última ficha, restar5, mirar la ficha a la que llegaste y seguir las pistas hacia atrás.
• (b) Definición técnica paso a paso: Técnica de rastreo de trayectorias óptimas. Se mantiene un vector paralelo last_coin: Vec<usize> de tamaño A + 1. Cuando la relajación dp[a - c] + 1 < dp[a] tiene éxito, se registra last_coin[a] = c. Al finalizar, se reconstruye la solución iterando curr = amount; while curr > 0 { path.push(last_coin[curr]); curr -= last_coin[curr]; }.
• (c) Cómo funciona en Rust (memoria y tipos): Requiere O(A) espacio adicional para el vector de predecesores y produce un Vec<usize> con las monedas exactas en tiempo O(k) donde k ≤ A.
• (d) Error típico de Junior: Intentar deducir la moneda sobre la marcha probando monedas aleatorias sin registrar explícitamente cuál fue la moneda que originó la transición mínima.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

¿Por qué Falla el Algoritmo Codicioso (Greedy) en Coin Change?#

En sistemas monetarios modernos como el Dólar o el Euro, el sistema de denominaciones es un sistema monetario canónico, donde la estrategia codiciosa de elegir la moneda más grande siempre da el mínimo de monedas.

Sin embargo, en sistemas monetarios arbitrarios, Greedy fracasa por completo.

Contraejemplo Canónico:

• Denominaciones: coins = [1, 3, 4]
• Monto a formar: amount = 6

Ejecución Codiciosa (Greedy):

1. Toma la moneda más grande que cabe: 4 ≤ 6 ⟹ toma una moneda de 4. Monto restante: 6 - 4 = 2.
2. La moneda de 4 no cabe (4 > 2). La de 3 no cabe (3 > 2).
3. Toma una moneda de 1. Monto restante: 2 - 1 = 1.
4. Toma otra moneda de 1. Monto restante: 1 - 1 = 0.

• Resultado Greedy: Monedas [4, 1, 1] ⟹ 3 monedas.

Ejecución Óptima con Programación Dinámica:

• Si tomamos dos monedas de 3: 3 + 3 = 6.
• Resultado DP: Monedas [3, 3] ⟹ 2 monedas.

Greedy cayó en un óptimo local al elegir 4, dejando un residuo de 2 que requirió dos monedas de 1. La Programación Dinámica evalúa todas las transiciones posibles y descubre que dos monedas de tamaño intermedio logran una solución estrictamente superior.

La Demostración Visual del Dilema de los Bucles#

Veamos el cálculo de coins = [1, 2] para amount = 3:

A. Monedas en Bucle Externo ⟹ Combinaciones (LC 518)#

dp inicial: [1, 0, 0, 0]

Fase Moneda 1:
a = 1: dp[1] += dp[0] (1) -> dp = [1, 1, 0, 0]   (Formas: {1})
a = 2: dp[2] += dp[1] (1) -> dp = [1, 1, 1, 0]   (Formas: {1,1})
a = 3: dp[3] += dp[2] (1) -> dp = [1, 1, 1, 1]   (Formas: {1,1,1})

Fase Moneda 2:
a = 2: dp[2] += dp[0] (1) -> dp[2] = 1 + 1 = 2   (Formas: {1,1}, {2})
a = 3: dp[3] += dp[1] (1) -> dp[3] = 1 + 1 = 2   (Formas: {1,1,1}, {1,2})

Resultado final dp[3] = 2 combinaciones.
¡NUNCA se pudo generar {2, 1} porque la fase de la moneda 1 ya había concluido!

B. Monto en Bucle Externo ⟹ Permutaciones (LC 377)#

dp inicial: [1, 0, 0, 0]

a = 1:
- Probar moneda 1: dp[1] += dp[0] (1) -> dp[1] = 1   (Rutas: [1])

a = 2:
- Probar moneda 1: dp[2] += dp[1] (1) -> dp[2] = 1   (Rutas: [1,1])
- Probar moneda 2: dp[2] += dp[0] (1) -> dp[2] = 2   (Rutas: [1,1], [2])

a = 3:
- Probar moneda 1: dp[3] += dp[2] (2) -> dp[3] = 2   (Rutas que terminan en 1: [1,1,1], [2,1])
- Probar moneda 2: dp[3] += dp[1] (1) -> dp[3] = 2 + 1 = 3 (Rutas que terminan en 2: [1,2])

Resultado final dp[3] = 3 permutaciones ([1,1,1], [2,1], [1,2]).

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Flujo y Relajación en Coin Change#

Consulta el diagrama vectorial:

flowchart TD
    START(["dp[0] = 0, resto = centinela (amount + 1)"]) --> LOOP_A["Para a desde 1 hasta amount"]
    LOOP_A --> LOOP_C["Para cada moneda c in coins"]
    LOOP_C --> CHECK{"¿c <= a?"}
    CHECK -->|Sí| RELAX{"dp[a - c] + 1 < dp[a]"}
    RELAX -->|Sí: Mejor combinación| UPDATE["dp[a] = dp[a - c] + 1<br/>last_coin[a] = c"]
    RELAX -->|No: Peor o igual| PASS["Continuar"]
    CHECK -->|No: Moneda excede monto| PASS
    UPDATE --> NEXT_C{"¿Más monedas?"}
    PASS --> NEXT_C
    NEXT_C -->|Sí| LOOP_C
    NEXT_C -->|No| NEXT_A{"¿Más montos?"}
    NEXT_A -->|Sí| LOOP_A
    NEXT_A -->|No| DONE(["dp[amount] contiene el mínimo"])

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Analicemos la memoria durante coin_change_min_coins(&[1, 2, 5], 6):

PASO 1: Asignación e Inicialización en Heap
Stack: coins = &[1, 2, 5], amount = 6, sentinel = 7
Heap:
Índices:        0   1   2   3   4   5   6
dp:            [0,  7,  7,  7,  7,  7,  7]

PASO 2: Procesando montos a = 1 a 4
- a = 1: dp[1] = dp[0] + 1 = 1
- a = 2: dp[2] = min(dp[1]+1, dp[0]+1) = 1
- a = 3: dp[3] = min(dp[2]+1, dp[1]+1) = 2
- a = 4: dp[4] = min(dp[3]+1, dp[2]+1) = 2
Heap actual:   [0,  1,  1,  2,  2,  7,  7]

PASO 3: Procesando a = 5
- con c = 1: dp[5] = min(7, dp[4]+1) = min(7, 3) = 3
- con c = 2: dp[5] = min(3, dp[3]+1) = min(3, 3) = 3
- con c = 5: dp[5] = min(3, dp[0]+1) = min(3, 1) = 1 (¡Relajación óptima con moneda de 5!)
Heap actual:   [0,  1,  1,  2,  2,  1,  7]

PASO 4: Procesando a = 6
- con c = 1: dp[6] = min(7, dp[5]+1) = min(7, 2) = 2
- con c = 2: dp[6] = min(2, dp[4]+1) = min(2, 3) = 2
- con c = 5: dp[6] = min(2, dp[1]+1) = min(2, 2) = 2
Heap final:    [0,  1,  1,  2,  2,  1,  2]

Resultado retornado: Some(dp[6]) = Some(2).
Costo de memoria en Heap: 7 elementos usize = 56 bytes.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: El Desbordamiento Silencioso al Usar Centinelas con Sumas Aritméticas#

• El error: Usar usize::MAX como valor inicial de "infinito" en dp:

  let mut dp = vec![usize::MAX; amount + 1];
  dp[0] = 0;
  for a in 1..=amount {
      for &c in coins {
          if c <= a {
              dp[a] = dp[a].min(dp[a - c] + 1); // ¡PÁNICO POR DESBORDAMIENTO!
          }
      }
  }

• Por qué falla: Si dp[a - c] aún vale usize::MAX, hacer dp[a - c] + 1 desborda el tipo entero, provocando un pánico inmediato en modo debug (attempt to add with overflow) o un comportamiento erróneo envolvente (wrap-around a 0) en modo release.
• La solución: Usar como centinela un valor finito estrictamente inalcanzable, como amount + 1, o comprobar previamente:

  if dp[a - c] != sentinel {
      dp[a] = dp[a].min(dp[a - c] + 1);
  }

Trampa 2: Invertir el Orden de los Bucles en Problemas de Conteo#

• El error: Colocar el bucle de montos en el exterior cuando el problema pide "número de formas distintas" (CTCI 8.11 / LC 518).
• Por qué falla: Transforma silenciosamente un problema de combinaciones en un problema de permutaciones. Si el monto es 5 con monedas [1, 2, 5], el resultado correcto de combinaciones es 4 ([5], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]). El bucle incorrecto devolverá 9 permutaciones distintas.
• La solución:
• ¿Piden Combinaciones (orden no importa)? ⟹ for coin in coins AFUERA.
• ¿Piden Permutaciones (orden sí importa)? ⟹ for a in 1..=amount AFUERA.

Trampa 3: No Manejar el Caso amount = 0 con Coherencia Semántica#

• El error: En LC 322 (mínimo de monedas), devolver -1 o 1 para amount = 0.
• Por qué falla: Para formar \$0 se requieren exactamente 0 monedas. No entregar ninguna moneda es una solución perfectamente válida y de costo cero.
• La solución: Garantizar en los casos base:
• En minimización (LC 322): if amount == 0 { return Some(0); }.
• En combinaciones (LC 518): dp[0] = 1.

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_41.rs)#

/// LeetCode 322: Mínimo número de monedas para formar amount en O(N * amount) tiempo.
pub fn coin_change_min_coins(coins: &[usize], amount: usize) -> Option<usize> {
    if amount == 0 {
        return Some(0);
    }

    let sentinel = amount + 1;
    let mut dp = vec![sentinel; amount + 1];
    dp[0] = 0;

    for a in 1..=amount {
        for &coin in coins {
            if coin <= a {
                let candidate = dp[a - coin] + 1;
                if candidate < dp[a] {
                    dp[a] = candidate;
                }
            }
        }
    }

    if dp[amount] > amount {
        None
    } else {
        Some(dp[amount])
    }
}

/// Reconstrucción de la lista de monedas exactas óptimas.
pub fn coin_change_min_coins_path(coins: &[usize], amount: usize) -> Option<Vec<usize>> {
    if amount == 0 {
        return Some(Vec::new());
    }

    let sentinel = amount + 1;
    let mut dp = vec![sentinel; amount + 1];
    let mut last_coin = vec![0usize; amount + 1];
    dp[0] = 0;

    for a in 1..=amount {
        for &coin in coins {
            if coin <= a && dp[a - coin] + 1 < dp[a] {
                dp[a] = dp[a - coin] + 1;
                last_coin[a] = coin;
            }
        }
    }

    if dp[amount] > amount {
        return None;
    }

    let mut path = Vec::new();
    let mut curr = amount;
    while curr > 0 {
        let coin = last_coin[curr];
        path.push(coin);
        curr -= coin;
    }

    path.sort_unstable();
    Some(path)
}

/// CTCI 8.11 / LC 518: Combinaciones únicas con monedas en bucle externo.
pub fn coin_change_ways(coins: &[usize], amount: usize) -> u64 {
    let mut dp = vec![0u64; amount + 1];
    dp[0] = 1;

    for &coin in coins {
        for a in coin..=amount {
            dp[a] += dp[a - coin];
        }
    }

    dp[amount]
}

/// LC 377: Permutaciones ordenadas con monto en bucle externo.
pub fn coin_change_permutations(coins: &[usize], amount: usize) -> u64 {
    let mut dp = vec![0u64; amount + 1];
    dp[0] = 1;

    for a in 1..=amount {
        for &coin in coins {
            if coin <= a {
                dp[a] += dp[a - coin];
            }
        }
    }

    dp[amount]
}

Implementación en Python de Referencia (practica/dia_41_dp_coin_change_unbounded.py)#

from typing import List, Optional


def coin_change_min_coins(coins: List[int], amount: int) -> int:
    """LeetCode 322: Mínimo número de monedas en O(N * amount)."""
    if amount < 0:
        return -1
    if amount == 0:
        return 0

    dp = [float("inf")] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)

    return int(dp[amount]) if dp[amount] != float("inf") else -1


def coin_change_ways(coins: List[int], amount: int) -> int:
    """CTCI 8.11 / LC 518: Combinaciones únicas con monedas afuera."""
    if amount < 0:
        return 0
    if amount == 0:
        return 1

    dp = [0] * (amount + 1)
    dp[0] = 1

    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]

    return dp[amount]


def coin_change_permutations(coins: List[int], amount: int) -> int:
    """LC 377: Permutaciones con monto en bucle externo."""
    if amount < 0:
        return 0
    if amount == 0:
        return 1

    dp = [0] * (amount + 1)
    dp[0] = 1

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] += dp[a - c]

    return dp[amount]

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Denominaciones con Moneda de 1 Incluida: - Si la lista de monedas incluye la moneda de 1 (coins = [1, ...]), cualquier monto entero A ≥ 0 es alcanzable. Demuestra por qué dp[amount] nunca puede ser None.
2. Paso Límite 2: Monto Inalcanzable Pequeño: - Monedas: [5, 10], Monto: 3. - Verifica que el bucle interno nunca ejecuta actualizaciones porque todas las monedas superan el monto, retornando None.
3. Paso Límite 3: Reducción a Minimum Cost For Tickets (LeetCode 983): - Dado un calendario de días de viaje y pases de 1, 7 y 30 días, formula la relación de recurrencia como una variante de Unbounded Knapsack donde el costo se minimiza saltando los días cubiertos por la validez del pase.

Navegación final:

• ← Sesión 40: Grokking Ch9 — DP: Knapsack 0/1 y Subset Sum
• Sesión 42: Grokking Ch9 — DP: LCS, LIS y Box Stacking →
• Glosario Maestro
• Guía de Diagramas de Arquitectura