#015 Caminos en una Cuadrícula

1 Visualizando el Problema

Empecemos con el caso pequeño: una cuadrícula de 2×2 tiene exactamente 6 caminos posibles. Cada camino requiere 2 movimientos hacia la derecha y 2 hacia abajo.

Los 6 caminos en una cuadrícula 2×2:

R R D D

R D R D

R D D R

D R R D

D R D R

D D R R

El Insight Clave

Observa algo crucial: todos los caminos tienen la misma longitud. Para ir de (0,0) a (2,2) necesitas exactamente:

→ →

2 pasos a la derecha

↓ ↓

2 pasos abajo

Un camino no es más que una secuencia de 4 movimientos: 2 son R (derecha) y 2 son D (abajo).

La pregunta se transforma: ¿De cuántas formas podemos ordenar RRDD?

Reformulando el problema

Grid 2\times2 4 posiciones, elegir 2 para "R" C(4,2) = 6 caminos

Grid 20\times20 40 posiciones, elegir 20 para "R" C(40,20) = ???

Conexión con el Triángulo de Pascal

C(n,k) son exactamente los números del triángulo de Pascal. Para n=4, k=2:

1

2

1

3

1

4

6

4

1

Fila 4, posición 2: C(4,2) = 6

Caminos en grid 20×20

137,846,528,820

Fórmula

C(40, 20)

2 Programación Dinámica (DP)

Antes de usar la fórmula directa, veamos cómo resolverlo con programación dinámica. Esta técnica es fundamental en algoritmos y tiene aplicaciones mucho más amplias.

La Idea Central de DP

Pregunta clave: ¿Cuántos caminos hay para llegar a cada celda?

Para llegar a cualquier celda (i, j), solo puedes venir de:

Arriba: celda (i-1, j)
Izquierda: celda (i, j-1)

caminos(i, j) = caminos(i-1, j) + caminos(i, j-1)

Construyendo la tabla (grid 3×3):

1

2

3

4

1

3

6

10

1

4

10

20

■ Bordes = 1 camino ■ Esquina final = 20 caminos

¿Por qué los bordes son siempre 1?

Para llegar a cualquier celda del borde superior, solo puedes ir hacia la derecha: → → → →
Para llegar a cualquier celda del borde izquierdo, solo puedes ir hacia abajo: ↓ ↓ ↓ ↓

Solo hay un único camino posible para cada celda del borde.

Python — Programación Dinámica

def lattice_paths_dp(n):
    """
    Cuenta caminos en una cuadrícula n×n usando DP.

    Construimos una tabla donde grid[i][j] = número de caminos
    desde (0,0) hasta (i,j).
    """
    # Crear tabla (n+1) × (n+1) porque hay n+1 puntos en cada dimensión
    # Para un grid 2×2, hay 3×3 = 9 intersecciones
    size = n + 1
    grid = [[0] * size for _ in range(size)]

    # Caso base: primera fila y primera columna = 1
    # (solo hay un camino para llegar a cualquier punto del borde)
    for i in range(size):
        grid[0][i] = 1  # Primera fila
        grid[i][0] = 1  # Primera columna

    # Rellenar el resto de la tabla
    # Cada celda = suma de (arriba + izquierda)
    for i in range(1, size):
        for j in range(1, size):
            grid[i][j] = grid[i-1][j] + grid[i][j-1]

    return grid[n][n]

# Verificar con el ejemplo del problema
print("Grid 2×2:", lattice_paths_dp(2))  # Debe ser 6
print("Grid 3×3:", lattice_paths_dp(3))  # Debe ser 20

# Resolver el problema
print("\nGrid 20×20:", lattice_paths_dp(20))

// Output aparecerá aquí

Análisis de Complejidad

Tiempo

O(n²)

Llenamos una tabla de (n+1)×(n+1)

Espacio

O(n²)

Almacenamos toda la tabla

Optimización posible: Solo necesitamos la fila anterior para calcular la actual, así que podríamos reducir el espacio a O(n). Pero para n=20, O(n²) es perfectamente aceptable.

Python — DP Optimizado (O(n) espacio)

def lattice_paths_dp_optimized(n):
    """
    Versión optimizada en espacio.

    Observación: para calcular la fila i, solo necesitamos la fila i-1.
    Podemos usar una sola fila y actualizarla in-place.
    """
    # Una sola fila de tamaño n+1, inicializada con 1s
    row = [1] * (n + 1)

    # Para cada fila (excepto la primera que ya es todo 1s)
    for i in range(1, n + 1):
        # Para cada columna (excepto la primera que siempre es 1)
        for j in range(1, n + 1):
            # row[j] ya contiene el valor de la fila anterior (arriba)
            # row[j-1] ya fue actualizado y contiene el valor de la izquierda
            row[j] = row[j] + row[j-1]

    return row[n]

# Verificar
print("Grid 2×2:", lattice_paths_dp_optimized(2))
print("Grid 3×3:", lattice_paths_dp_optimized(3))
print("\nGrid 20×20:", lattice_paths_dp_optimized(20))
print("\n¡Mismo resultado, pero usando solo O(n) memoria!")

// Output aparecerá aquí

✓ Programación Dinámica ✓ Tabla de subproblemas ✓ Optimización de espacio

3 Fórmula Combinatoria Directa

La programación dinámica es elegante, pero existe una solución O(n) que usa directamente el coeficiente binomial. Es la forma más eficiente de resolver este problema.

Fórmula del coeficiente binomial C(n, k) = n! / (k! \times (n-k)!) Para un grid n\timesn: C(2n, n)

¿Por qué C(2n, n)?

Para un grid n×n necesitamos:

n movimientos hacia la derecha (R)
n movimientos hacia abajo (D)
2n movimientos en total

Un camino es una secuencia de 2n movimientos donde elegimos cuáles n son "R".

Ejemplo grid 2×2:

Posiciones: 1 2 3 4

Elegir 2 para "R": {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}

Caminos: RRDD, RDRD, RDDR, DRRD, DRDR, DDRR

C(4,2) = 6 ✓

Python — math.comb (Python 3.8+)

import math

def lattice_paths_comb(n):
    """
    Solución O(n) usando el coeficiente binomial.

    Para un grid n×n, la respuesta es C(2n, n).
    Python 3.8+ incluye math.comb() que lo calcula eficientemente.
    """
    return math.comb(2 * n, n)

# Verificar
print("Grid 2×2:", lattice_paths_comb(2))   # 6
print("Grid 3×3:", lattice_paths_comb(3))   # 20
print("Grid 4×4:", lattice_paths_comb(4))   # 70

# Resolver el problema
print("\nGrid 20×20:", lattice_paths_comb(20))

# Bonus: ¡también podemos calcular grids enormes!
print("\nGrid 100×100:", lattice_paths_comb(100))

// Output aparecerá aquí

Python — Cálculo manual (sin math.comb)

def lattice_paths_manual(n):
    """
    Calcula C(2n, n) manualmente.

    Truco: C(2n, n) = (2n)! / (n! × n!)

    Pero calcular factoriales enormes y dividir es ineficiente.
    En vez de eso, calculamos paso a paso:

    C(2n, n) = (2n × (2n-1) × ... × (n+1)) / (n × (n-1) × ... × 1)

    Para evitar overflow (aunque Python lo maneja), alternamos
    multiplicaciones y divisiones.
    """
    result = 1

    for i in range(n):
        # Multiplicamos por (2n - i) / (i + 1)
        result = result * (2 * n - i) // (i + 1)

    return result

# Verificar
print("Grid 2×2:", lattice_paths_manual(2))
print("Grid 3×3:", lattice_paths_manual(3))
print("\nGrid 20×20:", lattice_paths_manual(20))

# Mostremos el cálculo paso a paso para n=2
print("\n--- Cálculo paso a paso para C(4,2) ---")
result = 1
n = 2
for i in range(n):
    numerator = 2 * n - i
    denominator = i + 1
    result = result * numerator // denominator
    print(f"Paso {i+1}: × {numerator} / {denominator} = {result}")

// Output aparecerá aquí

Comparación de Métodos

Método	Tiempo	Espacio	Uso
DP (tabla)	O(n²)	O(n²)	Didáctico
DP optimizado	O(n²)	O(n)	Memoria limitada
math.comb	O(n)	O(1)	Óptimo

C(2n, n): El Número Central de Catalan

C(2n, n) es el número central de la fila 2n del triángulo de Pascal. Es el más grande de su fila y aparece en muchos problemas de combinatoria:

Caminos en cuadrículas (este problema)
Formas de subir escaleras
Secuencias balanceadas de paréntesis (relacionado con Catalan)
Aproximación de π (fórmula de Wallis)

✓ Coeficiente binomial ✓ math.comb ✓ Reformulación combinatoria ✓ Triángulo de Pascal

Lattice Paths

1 Visualizando el Problema

Los 6 caminos en una cuadrícula 2×2:

El Insight Clave

Reformulando el problema

Conexión con el Triángulo de Pascal

2 Programación Dinámica (DP)

La Idea Central de DP

Construyendo la tabla (grid 3×3):

¿Por qué los bordes son siempre 1?

Análisis de Complejidad

3 Fórmula Combinatoria Directa

¿Por qué C(2n, n)?

Comparación de Métodos

C(2n, n): El Número Central de Catalan