#018 Suma Máxima de Camino I

Maximum Path Sum I

Empezando en la cima del triángulo y moviéndote a números adyacentes en la fila de abajo, encuentra la suma máxima desde la cima hasta la base.

● Programación Dinámica ● Bottom-up ● Por qué falla greedy

1 El Problema del Triángulo

Tenemos un triángulo de números. Desde la cima, podemos bajar a uno de los dos números adyacentes en la fila siguiente. Queremos maximizar la suma del camino.

Ejemplo pequeño (4 filas):

Camino óptimo: 3 → 7 → 4 → 9 = 23

¿Qué significa "adyacente"?

Desde cada número, solo puedes moverte a los dos números directamente debajo:

Si estás en posición i de una fila,

puedes ir a posición i o i+1 de la siguiente.

Desde el 7, solo puedes ir al 2 o al 4 (no al 6)

¿Por qué NO funciona elegir siempre el mayor?

El enfoque "greedy" (codicioso) sería: en cada paso, elegir el número más grande. Pero esto puede llevarnos a un camino subóptimo:

Camino Greedy

3→7→4→5 = 19

Camino Óptimo

3→7→4→9 = 23

Greedy elige 5 sobre 9 porque desde el 4, el 5 está "disponible" pero el camino al 9 requiere planificación desde antes.

El Triángulo Real (15 filas)

El problema nos da un triángulo de 15 filas. ¿Cuántos caminos posibles hay?

En cada fila elegimos izquierda o derecha: 2 opciones.
14 decisiones (filas 1→2, 2→3, ..., 14→15).
Total: 2¹⁴ = 16,384 caminos

Probar todos es factible para 15 filas, pero el problema 67 tiene ¡100 filas! (2⁹⁹ caminos)

Suma máxima del camino

1074

Filas en el triángulo

2 Fuerza Bruta: Probar Todos los Caminos

La solución más directa: explorar todos los caminos posibles con recursión y quedarnos con el mejor.

La Idea Recursiva

Para cada celda, la mejor suma desde ahí hasta abajo es:

mejor(fila, col) = valor[fila][col] + max(
mejor(fila+1, col),
mejor(fila+1, col+1)
)

Caso base: en la última fila, mejor(fila, col) = valor[fila][col]

Python — Recursión (fuerza bruta)

triangle = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
    [20, 4, 82, 47, 65],
    [19, 1, 23, 75, 3, 34],
    [88, 2, 77, 73, 7, 63, 67],
    [99, 65, 4, 28, 6, 16, 70, 92],
    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
    [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
]

def max_path_recursive(row, col):
    """
    Calcula la suma máxima desde (row, col) hasta la base.

    Esta versión es INEFICIENTE porque recalcula los mismos
    subproblemas muchas veces.
    """
    # Caso base: última fila
    if row == len(triangle) - 1:
        return triangle[row][col]

    # Caso recursivo: mi valor + el mejor de los dos hijos
    left = max_path_recursive(row + 1, col)
    right = max_path_recursive(row + 1, col + 1)

    return triangle[row][col] + max(left, right)

# Para el ejemplo pequeño
small = [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]
triangle_backup = triangle
triangle = small

print("Ejemplo pequeño:")
print(f"Suma máxima: {max_path_recursive(0, 0)}")

# Para el problema real
triangle = triangle_backup
print(f"\nTriángulo de 15 filas:")
print(f"Suma máxima: {max_path_recursive(0, 0)}")
print("\n⚠️ Esto funciona, pero es O(2^n) - muy lento para triángulos grandes")

// Output aparecerá aquí

El Problema: Trabajo Repetido

Observa este triángulo de llamadas para el ejemplo pequeño:

max(0,0) = 3 + max(max(1,0), max(1,1))
           │
           ├── max(1,0) = 7 + max(max(2,0), max(2,1))
           │              │
           │              ├── max(2,0) = 2 + max(max(3,0), max(3,1))
           │              └── max(2,1) = 4 + max(max(3,1), max(3,2))  ← ¡REPETIDO!
           │
           └── max(1,1) = 4 + max(max(2,1), max(2,2))
                          │
                          ├── max(2,1) = 4 + max(max(3,1), max(3,2))  ← ¡REPETIDO!
                          └── max(2,2) = 6 + max(max(3,2), max(3,3))

max(2,1) se calcula dos veces. En triángulos grandes, el mismo subproblema se recalcula miles de veces.

Complejidad temporal

O(2ⁿ)

Exponencial - cada nodo genera 2 llamadas

Complejidad espacial

O(n)

Profundidad del stack de recursión

✓ Recursión ✓ Subproblemas solapados ! Ineficiente O(2ⁿ)

3 Programación Dinámica: Bottom-Up

En vez de calcular desde arriba (y repetir trabajo), calculamos desde abajo hacia arriba. Cada celda solo se procesa una vez.

La Idea Clave

Empezamos por la penúltima fila. Para cada número, sumamos el mayor de sus dos hijos:

nuevo[i] = original[i] + max(hijo_izq, hijo_der)

Repetimos hasta llegar a la cima. El número en la cima es la respuesta.

Ejemplo paso a paso:

Paso 0: Triángulo original

Paso 1: Procesar fila 3

2+max(8,5)=10, 4+max(5,9)=13, 6+max(9,3)=15

Paso 2: Procesar fila 2

7+max(10,13)=20, 4+max(13,15)=19

Paso 3: Procesar fila 1 (cima)

3+max(20,19)=23 ✓

Python — Programación Dinámica (bottom-up)

triangle = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
    [20, 4, 82, 47, 65],
    [19, 1, 23, 75, 3, 34],
    [88, 2, 77, 73, 7, 63, 67],
    [99, 65, 4, 28, 6, 16, 70, 92],
    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
    [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
]

def max_path_dp(tri):
    """
    Calcula la suma máxima usando DP bottom-up.

    Modificamos el triángulo in-place, de abajo hacia arriba.
    Cada celda se convierte en: valor + max(hijo_izq, hijo_der)
    """
    # Hacemos una copia para no modificar el original
    dp = [row[:] for row in tri]

    # Desde la penúltima fila hasta la primera
    for row in range(len(dp) - 2, -1, -1):
        for col in range(len(dp[row])):
            # Sumar el mayor de los dos hijos
            left_child = dp[row + 1][col]
            right_child = dp[row + 1][col + 1]
            dp[row][col] += max(left_child, right_child)

    # La cima contiene la suma máxima
    return dp[0][0]

# Ejemplo pequeño
small = [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]
print(f"Ejemplo pequeño: {max_path_dp(small)}")

# Problema real
print(f"Triángulo de 15 filas: {max_path_dp(triangle)}")

# Mostrar cómo se ve el triángulo transformado (ejemplo pequeño)
print("\n--- Triángulo transformado (ejemplo pequeño) ---")
dp = [row[:] for row in small]
for row in range(len(dp) - 2, -1, -1):
    for col in range(len(dp[row])):
        dp[row][col] += max(dp[row + 1][col], dp[row + 1][col + 1])
    print(f"Después de fila {row}: {dp[row]}")

// Output aparecerá aquí

Python — Versión compacta (una línea por iteración)

triangle = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
    [20, 4, 82, 47, 65],
    [19, 1, 23, 75, 3, 34],
    [88, 2, 77, 73, 7, 63, 67],
    [99, 65, 4, 28, 6, 16, 70, 92],
    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
    [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
]

def max_path_compact(tri):
    """
    Versión compacta usando reduce y zip.

    Empezamos con la última fila y vamos "reduciendo" hacia arriba.
    """
    from functools import reduce

    def combine_rows(bottom, top):
        # Para cada elemento de la fila superior,
        # sumar el máximo de sus dos hijos
        return [t + max(l, r) for t, l, r in zip(top, bottom, bottom[1:])]

    # Reducir de abajo hacia arriba
    return reduce(combine_rows, reversed(tri))[0]

print(f"Suma máxima: {max_path_compact(triangle)}")

# Explicación del zip
print("\n--- Cómo funciona zip en este contexto ---")
bottom = [8, 5, 9, 3]
top = [2, 4, 6]
print(f"bottom:     {bottom}")
print(f"bottom[1:]: {bottom[1:]}")
print(f"top:        {top}")
print(f"\nzip(top, bottom, bottom[1:]):")
for t, l, r in zip(top, bottom, bottom[1:]):
    print(f"  ({t}, {l}, {r}) → {t} + max({l}, {r}) = {t + max(l, r)}")

// Output aparecerá aquí

Comparación de Complejidad

Método	Tiempo	Espacio	15 filas	100 filas
Recursión	O(2ⁿ)	O(n)	16,384 ops	10³⁰ ops
DP bottom-up	O(n²)	O(n²)	120 ops	5,050 ops

n = número de filas. DP es exponencialmente más rápido.

El Patrón de Programación Dinámica

Identificar subproblemas solapados: los mismos cálculos se repiten
Definir el estado: ¿qué información necesito? (fila, columna)
Encontrar la recurrencia: dp[i][j] = valor + max(dp[i+1][j], dp[i+1][j+1])
Establecer caso base: la última fila ya tiene los valores finales
Elegir dirección: bottom-up suele ser más eficiente que top-down con memoización

✓ Programación Dinámica ✓ Bottom-up vs Top-down ✓ Subproblemas solapados ✓ Por qué greedy falla