Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Suma máxima de un camino en un triángulo

Encuentra la mayor suma de un camino que va desde la cima de un triángulo de números hasta su fila inferior.

Lo que aprenderás

  • Sustituir una búsqueda exponencial por programación dinámica
  • Combinar los resultados de la fila de abajo
  • Tratar valores negativos y entradas vacías

Problema

Ver original (inglés)

Un triángulo de números tiene un valor en la fila 0, dos en la fila 1, y así sucesivamente. Empieza en la cima y baja una fila cada vez, eligiendo el valor que está justo debajo o el que está debajo a la derecha (de la posición i a la i o a la i + 1). Encuentra el camino cuyos valores suman más. Probar todos los caminos duplica el trabajo en cada fila; en cambio, si trabajas hacia arriba desde la última fila, el costo es cuadrático.

Implementa triangle_max_path_sum(triangle).

Entrada

triangle: las filas de arriba abajo; la fila r tiene r + 1 valores, que pueden ser negativos.

Salida

Devuelve la mayor suma posible de un camino de arriba abajo. Para un triángulo vacío devuelve 0.

Restricciones

0 ≤ filas ≤ 100; −1000 ≤ valor ≤ 1000

Ejemplos

Ejemplo 1
Entrada:
triangle = [
    [4],
    [7, 2],
    [1, 9, 5],
    [6, 3, 8, 2]
]

Salida esperada:
expected = 28
Entrada:
std::vector<std::vector<long long>> triangle = {
    {4},
    {7, 2},
    {1, 9, 5},
    {6, 3, 8, 2}
};

Salida esperada:
long long expected = 28;
Entrada:
long[][] triangle = new long[][] {
    new long[] {4},
    new long[] {7, 2},
    new long[] {1, 9, 5},
    new long[] {6, 3, 8, 2}
};

Salida esperada:
long expected = 28;

Explicación

El mejor camino es 4, 7, 9, 8 (posiciones 0, 0, 1, 2), que suma 28.

Ejemplo 2
Entrada:
triangle = [
    [-3],
    [5, -8],
    [-1, 2, 9]
]

Salida esperada:
expected = 4
Entrada:
std::vector<std::vector<long long>> triangle = {
    {-3},
    {5, -8},
    {-1, 2, 9}
};

Salida esperada:
long long expected = 4;
Entrada:
long[][] triangle = new long[][] {
    new long[] {-3},
    new long[] {5, -8},
    new long[] {-1, 2, 9}
};

Salida esperada:
long expected = 4;

Explicación

Con negativos, −3, 5, 2 da 4, mientras que −3, −8, 9 da −2, así que la respuesta es 4.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Empieza por la última fila: el mejor camino desde una casilla de abajo es simplemente su valor.

Pista 2

El mejor camino desde una casilla es su valor más el mayor de los mejores caminos de las dos casillas que tiene debajo.

Pista 3

Después de procesar todas las filas hacia arriba, la casilla de la cima contiene la respuesta.

Complejidad esperada

tiempo O(rows²), espacio extra O(rows)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.