Pirâmide de números

Pirâmide de números
Programação Dinâmica
Aluna: Raissa Barcellos

Problema clássico das Olimpíadas Internacionais de Informática de 1994

Problema
Calcular a rota, que começa no topo da pirâmide e acaba na base, com maior soma . Em cada passo podemos ir diagonalmente para baixo e para a esquerda ou para baixo e para a direita.

Duas possíveis rotas

Soma = 21

Soma = 30

Limites: todos os números da pirâmide são inteiros entre 0 e 99 e o número de linhas do triângulo‚ no máximo 100.

Análise da complexidade

• Em cada linha podemos tomar duas decisões diferentes: esquerda ou direita.
•

Seja n a altura da pirâmide. Uma rota ‚ constituída por n-1 decisões diferentes.

• Existem 2n-1 caminhos diferentes.
• Então, um programa que calculasse todas rotas teria complexidade temporal O(2n) : crescimento exponencial!
• Note-se que 2 99 ~ 6,34x1029 , que é um número demasiadamente grande!

Pirâmide de números
• Quando estamos no topo da pirâmide, temos duas decisões possíveis (esquerda ou direita):

Em cada um dos casos, temos de ter em conta todas as rotas das respectivas subpirâmides assinaladas em amarelo.

Pirâmide de números

Mas o que nos interessa saber sobre estas subpirâmides?
Apenas interessa o valor da sua melhor rota interna (que ‚ um instância mais pequena do mesmo problema)!
Para o exemplo, a solução é 7 mais o máximo entre o valor da melhor rota de cada uma das subpirâmides.

Pirâmide de números
• Então este problema pode ser resolvido recursivamente. 1

2

3

4

1

7

• Seja P[i][j] o j-ésimo número da i-ésima linha.

2

3

8

• Seja Max(i,j) o melhor que conseguimos a partir da

3

8

1

0

4

2

7

4

4

5

4

5

2

6

5

posição i,j.

5

Pirâmide de números
1

Então:
Max(i,j):
Se i = n então
Max(i,j) = P[i][j]
Senão
Max(i,j) = P[i][j] + máximo(Max(i+1,j), Max(i+1,j+1))

Para resolver o problema basta chamar Max(1,1)