Busca pelo caminho máximo em um triângulo numérico

Swift Hard loops

Tarefa «Busca pelo caminho máximo em um triângulo numérico»

Dado um triângulo de números inteiros. É necessário encontrar a soma máxima dos números em um caminho do topo até a base, movendo-se a cada passo uma linha para baixo e uma coluna para a esquerda ou para a direita (para os elementos vizinhos da linha seguinte). Implemente o algoritmo usando loops e programação dinâmica. O triângulo é definido pelo número de linhas N e, em seguida, pelas N linhas de números. Imprima um único número – a soma máxima.

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 100). A seguir, vêm N linhas, cada uma com i+1 números inteiros (onde i é o número da linha, começando em 0). Os números em módulo não excedem 10^4.

Formato de Saída

Um único número inteiro – a soma máxima do caminho.

Exemplos

Exemplo 1

ENTRADA

SAÍDA

27

Exemplo 2

ENTRADA

1

SAÍDA

0

Exemplo 3

ENTRADA

SAÍDA

10

Exemplo 4

ENTRADA

2
1 2
3 4

SAÍDA

4

Exemplo 5

ENTRADA

2

SAÍDA

0

main.swift