Búsqueda del camino máximo en un triángulo numérico

Swift Hard loops

Tarea «Búsqueda del camino máximo en un triángulo numérico»

Dado un triángulo de números enteros. Se necesita encontrar la suma máxima de números en un camino desde la cima hasta la base, moviéndose en cada paso una fila hacia abajo y una columna hacia la izquierda o hacia la derecha (a los elementos adyacentes de la siguiente fila). Implemente un algoritmo usando bucles y programación dinámica. El triángulo se define por la cantidad de filas N y luego N filas de números. Imprima un número: la suma máxima.

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 100). A continuación, siguen N líneas, cada una con i+1 números enteros (donde i es el número de fila, comenzando desde 0). Los números en valor absoluto no superan 10^4.

Formato de salida

Un número entero – la suma máxima del camino.

Ejemplos

Ejemplo 1

ENTRADA

SALIDA

27

Ejemplo 2

ENTRADA

1

SALIDA

0

Ejemplo 3

ENTRADA

SALIDA

10

Ejemplo 4

ENTRADA

2
1 2
3 4

SALIDA

4

Ejemplo 5

ENTRADA

2

SALIDA

0

main.swift