Sesión 39: CTCI Capítulo 8 (Parte 3) — Programación Dinámica 1D y 2D: Triple Step y Robot in a Grid (CTCI 8.1 & 8.2)#

Navegación rápida:

• ← Sesión 38: CTCI Ch8 — Backtracking: Permutaciones y N-Reinas
• Sesión 40: Grokking Ch9 — DP: Knapsack 0/1 y Subset Sum →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_39.rs

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

En esta sesión inauguramos el bloque de Programación Dinámica (DP), pasando de la fuerza bruta exponencial al procesamiento lineal y cuadrático mediante la reutilización sistemática de memoria. Consulta el Glosario Maestro y la Guía de Diagramas.

Programación Dinámica (Dynamic Programming - DP)#

• (a) En palabras simples (intuición): Imagina que escribes en una pizarra 1 + 1 + 1 + 1 + 1 y le preguntas a alguien cuánto da: responderá 5. Si luego agregas otro + 1 a la derecha, no vuelve a sumar todos los unos desde cero; simplemente recuerda el 5 anterior y le suma 1 para obtener 6. Recordar el pasado para no repetir trabajo innecesario es la esencia de la programación dinámica.
• (b) Definición técnica paso a paso: Paradigma de diseño algorítmico formulado por Richard Bellman para resolver problemas complejos descomponiéndolos en una colección de subproblemas más sencillos, resolviendo cada subproblema exactamente una vez y almacenando sus soluciones en una estructura de datos (tabla o variables). Requiere dos propiedades formales indispensables:

1. Subestructura Óptima: La solución óptima del problema global contiene en su interior las soluciones óptimas de los subproblemas.
2. Superposición de Subproblemas: El árbol de llamadas recursivas recalcula idénticos subproblemas decenas o miles de veces.

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante tablas contiguas en el heap (Vec<T> o Vec<Vec<T>>) o variables primitivas en el stack (u64, usize). Al operar sobre vectores indexados por posición, el compilador y la CPU aprovechan las líneas de caché L1/L2 mediante patrones de acceso secuencial y prefetching automático.
• (d) Error típico de Junior: Confundir DP con Divide and Conquer (como MergeSort). En Divide and Conquer los subproblemas son independientes y disjuntos (no se superponen); en DP los subproblemas se solapan masivamente.

Subestructura Óptima (Optimal Substructure)#

• (a) En palabras simples (intuición): Para saber la ruta más corta desde la Ciudad A hasta la Ciudad C pasando por B, esa ruta necesariamente debe estar formada por la ruta más corta entre A y B unida a la ruta más corta entre B y C. Si existiera un atajo mejor entre A y B, la ruta global mejoraría.
• (b) Definición técnica paso a paso: Propiedad matemática donde la solución óptima a una instancia de tamaño N puede construirse directamente combinando algebraicamente las soluciones óptimas de instancias menores (N-1, N-2, …). En problemas de conteo (como caminos o saltos), el total global es la suma aditiva de las soluciones de las etapas inmediatamente anteriores.
• (c) Cómo funciona en Rust (memoria y tipos): Se expresa como una relación de recurrencia determinista, por ejemplo: dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3].
• (d) Error típico de Junior: Asumir que todo problema tiene subestructura óptima; por ejemplo, encontrar el camino simple más largo entre dos nodos de un grafo NO tiene subestructura óptima.

Superposición de Subproblemas (Overlapping Subproblems)#

• (a) En palabras simples (intuición): En una empresa, cinco departamentos distintos le piden al mismo empleado que calcule el balance anual del año pasado. Si el empleado es novato, recalcula las 365 facturas cinco veces desde cero. Si es eficiente, calcula el balance la primera vez, guarda el informe en su cajón y en las siguientes cuatro solicitudes simplemente fotocopia el documento ya terminado.
• (b) Definición técnica paso a paso: Condición en la cual una formulación recursiva ingenua genera un árbol de cómputo donde los mismos nodos con idénticos parámetros de entrada son visitados de manera redundante O(2^N) o O(3^N) veces.
• (c) Cómo funciona en Rust (memoria y tipos): Se mitiga registrando resultados en un vector memo: &mut [Option<T>] o en un HashMap<K, V>. Antes de ejecutar cualquier llamada recursiva, se consulta si memo[state] ya contiene un valor Some(v).
• (d) Error típico de Junior: Intentar aplicar memoización a funciones que tienen efectos secundarios (I/O, mutación global) o donde los estados dependen de variables externas no incluidas en la firma de la función.

Top-Down (Memoización) vs Bottom-Up (Tabulación)#

• (a) En palabras simples (intuición):
• Top-Down: Empiezas en el piso 10 y dices "para saber cómo llegué aquí, necesito saber cómo llegué al 9, 8 y 7". Bajas recursivamente preguntando hacia atrás y anotando las respuestas.
• Bottom-Up: Empiezas en el piso 0 (la planta baja), calculas el piso 1, luego el 2, luego el 3, subiendo ordenadamente hasta alcanzar el piso 10 sin mirar atrás.
• (b) Definición técnica paso a paso:
• Top-Down: Ejecución guiada por la demanda que conserva la signatura recursiva natural, interceptando cada llamada con una consulta a un almacenamiento caché (memo).
• Bottom-Up: Ejecución iterativa que resuelve primero los casos base más pequeños y avanza topológicamente a través de bucles for llenando una tabla (dp).
• (c) Cómo funciona en Rust (memoria y tipos): Top-Down consume frames en el Call Stack (O(N) o O(R+C) en memoria de pila), arriesgando un desbordamiento de pila (stack overflow) si N > 10⁵. Bottom-Up usa bucles iterativos planos, eliminando por completo los frames de pila y reduciendo el overhead a cero llamadas a funciones.
• (d) Error típico de Junior: Usar siempre Top-Down por ser más "intuitivo" al traducir la fórmula matemática, ignorando que Bottom-Up casi siempre permite optimizar el espacio a O(1).

Arreglo Rodante y Reducción de Espacio a O(1) / O(Cols)#

• (a) En palabras simples (intuición): Si estás subiendo una escalera y tus pasos dependen solo de los últimos 3 escalones que pisaste, no necesitas cargar en tu mochila una libreta con el registro de los 10,000 escalones anteriores; basta con 3 notas adhesivas en la mano que vas actualizando a cada salto.
• (b) Definición técnica paso a paso: Técnica de ahorro de memoria aplicable cuando la relación de recurrencia en el paso i solo lee los estados a distancia finita k (i - 1, i - 2, …, i - k). Se descarta la tabla completa de longitud N y se mantienen únicamente k registros primitivos o un arreglo 1D reutilizable in-place de tamaño equivalente al ancho de la grilla.
• (c) Cómo funciona en Rust (memoria y tipos): En 1D se usan tres variables escalares en el Stack: let (mut a, mut b, mut c) = (1, 1, 2). En 2D (matrices de caminos) se transforma una matriz Vec<Vec<u64>> de R × C en un único vector Vec<u64> de tamaño C, actualizando dp[c] += dp[c - 1].
• (d) Error típico de Junior: En matrices con obstáculos, olvidar resetear dp[c] = 0 cuando la celda actual es un obstáculo, lo que deja valores de la fila anterior contaminando el cálculo de la fila nueva.

Poda de Celdas Muertas (failed_points / DFS con Memo)#

• (a) En palabras simples (intuición): En un laberinto, si entras por un pasillo que termina en una pared cerrada y regresas sobre tus pasos, clavas un cartel rojo de advertencia en la entrada de ese pasillo: "Callejón sin salida". Si horas más tarde llegas a esa misma bifurcación por otro camino, ves el cartel rojo y ni siquiera intentas entrar.
• (b) Definición técnica paso a paso: Poda en la reconstrucción de trayectorias (CTCI 8.2). Si una exploración desde la celda (r, c) fracasa en alcanzar el destino final, se registra (r, c) en un conjunto de exclusión failed_points. Cualquier llamada futura que intente transitar por (r, c) aborta en tiempo O(1).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante un HashSet<(usize, usize)> o una matriz booleana Vec<Vec<bool>>. Almacena celdas en el Heap que no deben volver a encolarse ni expandirse recursivamente.
• (d) Error típico de Junior: Memoizar solo los caminos exitosos; la explosión exponencial ocurre por explorar repetidamente las ramas que conducen a callejones sin salida. La poda crítica son las celdas fallidas.

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

Problema 1: Triple Step (CTCI 8.1 / LeetCode 70 Variación)#

Un niño sube una escalera de N escalones. En cada salto puede avanzar 1, 2 o 3 escalones. ¿Cuántas secuencias distintas de saltos existen para llegar a la cima?

Deducción de la Recurrencia#

Pensemos en el último salto que dio el niño para poner el pie en el escalón N:

1. Pudo haber saltado desde el escalón N - 1 con un salto de 1.
2. Pudo haber saltado desde el escalón N - 2 con un salto de 2.
3. Pudo haber saltado desde el escalón N - 3 con un salto de 3.

Como estos tres eventos son mutuamente excluyentes y cubren todas las posibilidades físicas:

¿Por qué el caso base f(0) = 1?#

Esta es la duda más frecuente de un desarrollador junior: "Si no hay escalones, ¿por qué hay 1 forma y no 0?".

• Razón combinatoria: f(0) representa el estado donde ya no quedan escalones por subir. Haber llegado a cero significa que la secuencia de saltos que ejecutaste fue exacta y válida (1 forma exitosa completa).
• Si definiéramos f(0) = 0, para subir 1 escalón tendríamos:

• Con f(0) = 1:

Evolución Algorítmica: De O(3^N) a O(1) en Espacio#

1. Fuerza Bruta Recursiva: Árbol ternario con factor de ramificación 3. Altura N. Tiempo O(3^N), Inviable para N ≥ 35.
2. Top-Down con Memoización: Cachea resultados en vector de tamaño N + 1. Tiempo O(N), Espacio O(N) (Call Stack + Heap).
3. Bottom-Up Tabulado: Bucle iterativo de 3 a N llenando un vector dp. Tiempo O(N), Espacio O(N).
4. Bottom-Up Optimizado: Mantiene solo 3 variables escalares a, b, c. Tiempo O(N), Espacio O(1) estricto.

Evolución de las 3 variables rodantes para N = 4:
Inicial: a=f(0)=1,  b=f(1)=1,  c=f(2)=2
i = 3:   curr = 1 + 1 + 2 = 4  --> a=1, b=2, c=4
i = 4:   curr = 1 + 2 + 4 = 7  --> a=2, b=4, c=7
Resultado final f(4) = 7

Problema 2: Robot in a Grid (CTCI 8.2 / LeetCode 62 & 63)#

Un robot se sitúa en la coordenada (0, 0) de una cuadrícula de R filas por C columnas. El robot solo puede moverse en dos direcciones:

• Hacia la DERECHA: (r, c + 1)
• Hacia ABAJO: (r + 1, c)

Ciertas casillas contienen obstáculos marcados con 1 (las libres tienen 0).

Objetivo A: Contar Caminos Únicos (LeetCode 62 y 63)#

Para llegar a la celda (r, c), el robot únicamente pudo provenir de la casilla superior (r - 1, c) o de la casilla izquierda (r, c - 1).

• Si (r, c) tiene un obstáculo: dp[r][c] = 0.
• Si (r, c) es libre: dp[r][c] = dp[r - 1][c] + dp[r][c - 1].

Optimización a Vector 1D Rodante:#

En lugar de almacenar una matriz R × C, observemos la actualización celda por celda:

Fila r-1 (anterior en memoria): [ dp[0],  dp[1],  dp[2], ..., dp[c], ... ]
                                                    |           |
                                                    | (arriba)  |
                                                    v           v
Fila r   (nueva en cálculo):   [ dp[0],  dp[1], ..., dp[c-1],  dp[c]_nuevo ]
                                                      (izq)

Al evaluar la columna c:

• El valor antiguo en dp[c] proviene de la fila anterior (r - 1, c) (representa el aporte desde arriba).
• El valor recién calculado en dp[c - 1] corresponde a la fila actual (r, c - 1) (representa el aporte desde la izquierda).
• Por lo tanto:

• Si la celda contiene un obstáculo:

El espacio se reduce drásticamente de O(R × C) a O(C).

Objetivo B: Reconstruir la Ruta Concreta (CTCI 8.2)#

Aquí no solo queremos saber el número total de formas, sino entregar el vector de puntos: [(0, 0), (0, 1), (1, 1), ..., (R-1, C-1)].

Un DFS simple sin control de estados recorre ramas redundantes con costo O(2^{R + C}). Si una celda no tiene camino hacia el destino, guardamos sus coordenadas en el conjunto failed_points. De este modo, cada celda de la grilla se explora una única vez, logrando tiempo O(R × C).

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

Diagrama de Flujo y Decisión de Transición DP#

Consulta el diagrama vectorial:

flowchart TD
    START(["Evaluar Celda (r, c)"]) --> OBST{"¿Es obstáculo?"}
    OBST -->|Sí: grid[r][c] == 1| ZERO["dp[c] = 0 (Sin caminos posibles)"]
    OBST -->|No: celda libre| BOUND{"¿c > 0?"}
    BOUND -->|Sí| ACC["dp[c] = dp[c] (arriba) + dp[c-1] (izq)"]
    BOUND -->|No: primera columna| KEEP["dp[0] mantiene valor de arriba"]
    ZERO --> NEXT["Avanzar a columna c + 1"]
    ACC --> NEXT
    KEEP --> NEXT

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

Analicemos qué ocurre en la memoria durante la ejecución de triple_step_optimized(4):

PASO 1: Inicialización en Stack (Cero asignaciones en Heap)
Stack Frame: triple_step_optimized(n = 4)
┌───────────────┬───────────────┬───────────────┐
│ a: u64 = 1    │ b: u64 = 1    │ c: u64 = 2    │
└───────────────┴───────────────┴───────────────┘
(Corresponden a f(0), f(1) y f(2))
Heap: [Vacío - Cero overhead de asignador]

PASO 2: Iteración i = 3
let curr = a + b + c = 1 + 1 + 2 = 4
Rotación de registros en Stack:
a = b  --> a = 1
b = c  --> b = 2
c = curr --> c = 4
┌───────────────┬───────────────┬───────────────┐
│ a: u64 = 1    │ b: u64 = 2    │ c: u64 = 4    │
└───────────────┴───────────────┴───────────────┘

PASO 3: Iteración i = 4
let curr = a + b + c = 1 + 2 + 4 = 7
Rotación de registros en Stack:
a = b  --> a = 2
b = c  --> b = 4
c = curr --> c = 7
┌───────────────┬───────────────┬───────────────┐
│ a: u64 = 2    │ b: u64 = 4    │ c: u64 = 7    │
└───────────────┴───────────────┴───────────────┘

PASO 4: Salida de función
Retorna el valor escalar c = 7 directamente a través de un registro de CPU (RAX en x86_64).
Costo de memoria: 0 bytes en Heap, 24 bytes en Stack.

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

Trampa 1: El Desbordamiento Silencioso de Enteros en Conteo de Caminos#

• El error: Usar i32 o u32 para acumular caminos en grillas de tamaño medio (por ejemplo, 30 × 30).
• Por qué falla: El número total de caminos en una grilla de 30 × 30 sin obstáculos viene dado por el coeficiente binomial:

Un entero de 32 bits con signo desborda a los 2.14 × 10⁹. En modo debug, Rust lanza un pánico inmediato (attempt to add with overflow); en modo release, produce una vuelta silenciosa (wrap-around) generando resultados erróneos o negativos.

• La solución: Usar siempre u64 o u128 para conteos combinatorios.

Trampa 2: Olvidar Poner en Cero las Celdas Bloqueadas en Arreglos 1D Rodantes#

• El error:

  // INCORRECTO:
  for r in 0..rows {
      for c in 0..cols {
          if grid[r][c] == 0 && c > 0 {
              dp[c] += dp[c - 1];
          }
          // Si grid[r][c] == 1, ¡no hace nada!
      }
  }

• Por qué falla: Si grid[r][c] == 1 y no modificas dp[c], la casilla conserva el valor que tenía en la fila superior r - 1. Ese valor remanente se propagará incorrectamente hacia abajo y hacia la derecha en las iteraciones siguientes como si no hubiera ningún obstáculo.
• La solución: Asignar explícitamente dp[c] = 0 cuando grid[r][c] == 1.

Trampa 3: No Podar Celdas Muertas (failed_points) en la Búsqueda de Rutas#

• El error: Implementar un DFS recursivo o backtracking ingenuo buscando el camino sin registrar qué casillas ya demostraron ser incapaces de alcanzar la meta.
• Por qué falla: En una grilla con obstáculos donde la meta es inalcanzable, múltiples ramas convergen sobre las mismas casillas. Un camino toma derecha-abajo y otro toma abajo-derecha; ambos llegan a la misma celda muerta (1, 1) y repiten exactamente toda la exploración fallida restante. Esto desata una complejidad exponencial O(2^{R + C}).
• La solución: Mantener un HashSet<(usize, usize)> o una matriz booleana failed_points. Si una celda retorna false, insertarla inmediatamente para abortar cualquier intento futuro en O(1).

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

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

use std::collections::{HashSet, VecDeque};

/// CTCI 8.1: Triple Step mediante Bottom-Up con Optimización a O(1) de Espacio.
pub fn triple_step_optimized(n: usize) -> u64 {
    if n == 0 || n == 1 {
        return 1;
    }
    if n == 2 {
        return 2;
    }

    let mut a: u64 = 1;
    let mut b: u64 = 1;
    let mut c: u64 = 2;

    for _ in 3..=n {
        let curr = a + b + c;
        a = b;
        b = c;
        c = curr;
    }

    c
}

/// LeetCode 63: Unique Paths II con obstáculos (espacio O(cols)).
pub fn unique_paths_with_obstacles(grid: &[Vec<i32>]) -> u64 {
    if grid.is_empty() || grid[0].is_empty() {
        return 0;
    }

    let rows = grid.len();
    let cols = grid[0].len();

    if grid[0][0] == 1 || grid[rows - 1][cols - 1] == 1 {
        return 0;
    }

    let mut dp = vec![0u64; cols];
    dp[0] = 1;

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == 1 {
                dp[c] = 0; // Poda del obstáculo: cero caminos
            } else if c > 0 {
                dp[c] += dp[c - 1]; // Acumulación desde la izquierda
            }
        }
    }

    dp[cols - 1]
}

/// CTCI 8.2: Robot in a Grid con memoización de celdas muertas (failed_points).
pub fn robot_in_a_grid(grid: &[Vec<i32>]) -> Option<Vec<(usize, usize)>> {
    if grid.is_empty() || grid[0].is_empty() || grid[0][0] == 1 {
        return None;
    }

    let rows = grid.len();
    let cols = grid[0].len();
    let mut path = Vec::new();
    let mut failed_points = HashSet::new();

    fn get_path(
        grid: &[Vec<i32>],
        r: usize,
        c: usize,
        rows: usize,
        cols: usize,
        path: &mut Vec<(usize, usize)>,
        failed: &mut HashSet<(usize, usize)>,
    ) -> bool {
        if r >= rows || c >= cols || grid[r][c] == 1 || failed.contains(&(r, c)) {
            return false;
        }

        let is_destination = r == rows - 1 && c == cols - 1;

        if is_destination
            || get_path(grid, r, c + 1, rows, cols, path, failed)
            || get_path(grid, r + 1, c, rows, cols, path, failed)
        {
            path.push((r, c));
            return true;
        }

        failed.insert((r, c));
        false
    }

    if get_path(grid, 0, 0, rows, cols, &mut path, &mut failed_points) {
        path.reverse();
        Some(path)
    } else {
        None
    }
}

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

from typing import List, Optional, Set, Tuple


def triple_step_tab(n: int) -> int:
    """CTCI 8.1: Triple Step Bottom-Up en O(N) tiempo y O(1) espacio."""
    if n <= 0:
        return 1 if n == 0 else 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    a, b, c = 1, 1, 2
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c

    return c


def unique_paths_with_obstacles(grid: List[List[int]]) -> int:
    """LeetCode 63: Unique Paths II optimizado a O(cols) espacio."""
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
        return 0

    dp = [0] * cols
    dp[0] = 1

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]

    return dp[-1]


def robot_in_a_grid(grid: List[List[int]]) -> Optional[List[Tuple[int, int]]]:
    """CTCI 8.2: Búsqueda con poda de celdas muertas (failed_points)."""
    if not grid or not grid[0] or grid[0][0] == 1:
        return None

    rows, cols = len(grid), len(grid[0])
    path: List[Tuple[int, int]] = []
    failed_points: Set[Tuple[int, int]] = set()

    def get_path(r: int, c: int) -> bool:
        if r >= rows or c >= cols or grid[r][c] == 1 or (r, c) in failed_points:
            return False

        is_destination = (r == rows - 1 and c == cols - 1)
        if is_destination or get_path(r, c + 1) or get_path(r + 1, c):
            path.append((r, c))
            return True

        failed_points.add((r, c))
        return False

    if get_path(0, 0):
        return path[::-1]

    return None

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

  if grid[0][0] == 1 { dp[0] = 0; }

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

1. Paso Límite 1: Grilla de Una Sola Fila o Una Sola Columna: - Resuelve mentalmente y verifica con código qué ocurre con una grilla de 1 × N o M × 1 con un obstáculo en el centro: - Todos los caminos posteriores al obstáculo deben ser estrictamente 0.
2. Paso Límite 2: Desbordamiento de Call Stack en Grillas Gigantes: - En una grilla de 1000 × 1000, la profundidad de recursión de robot_in_a_grid alcanza R + C = 2000. En Rust el hilo principal tiene típicamente 2 MB o 8 MB de stack, soportando esta profundidad sin colapso. Compara el consumo de memoria frente a la versión iterativa con cola BFS robot_in_a_grid_iterative.
3. Paso Límite 3: Triple Step con Número de Pasos Parametrizado (K pasos): - Modifica mentalmente la recurrencia para un niño que puede dar hasta K pasos simultáneos:
   f(n) = sum_{j=1}^K f(n - j)
   - ¿Cómo se puede optimizar el cálculo de la ventana deslizante para que cada escalón se calcule en tiempo O(1) en lugar de O(K) usando la técnica de Prefix Sums?

Navegación final:

• ← Sesión 38: CTCI Ch8 — Backtracking: Permutaciones y N-Reinas
• Sesión 40: Grokking Ch9 — DP: Knapsack 0/1 y Subset Sum →
• Glosario Maestro
• Guía de Diagramas de Arquitectura