Problema
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
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.
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.