O problema do Triângulo Numérico (POJ1163) consiste em encontrar o caminho de maior soma em um triângulo numérico, onde cada passo permite mover-se para a esquerda inferior ou direita inferior. O objetivo é calcular essa soma máxima, sem a necessidade de exibir o caminho percorrido. O número de linhas do triângulo é entre 2 e 100, e os números variam de 0 a 99.

Considere o seguinte triângulo:

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

Formato de Entrada:

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Saída Esperada:

30

Abordagem Inicial: Recursão Simples

Podemos modelar este problema usando uma abordagem recursiva. Seja D(r, j) o número na linha r e posição j (ambos começando em 1). Definimos MaxSum(r, j) como a soma máxima de um caminho que começa em D(r, j) e vai até a base do triângulo.

O problema se resume a encontrar MaxSum(1, 1).

A relação de recorrência é a seguinte:

• Se r == N (onde N é o número total de linhas), então MaxSum(r, j) = D(r, j).
• Caso contrário, MaxSum(r, j) = max(MaxSum(r+1, j), MaxSum(r+1, j+1)) + D(r, j).

Otimização 1: Memorização (Recursão com Ponto de Ordem)

A abordagem recursiva simples envolve muitos cálculos redundantes. Podemos otimizar isso armazenando os resultados de MaxSum(r, j) à medida que são calculados. Se um valor já foi computado, ele é simplesmente recuperado, evitando recálculos.

Otimização 2: Transformando Recursão em DP Iterativa (Abordagem "Todos por Um")

A relação de recorrência pode ser transformada em uma abordagem iterativa de programação dinâmica. Em vez de resolver o problema de cima para baixo (recursão), resolvemos de baixo para cima.

Usando um array bidimensional f[r][j] para armazenar o valor de MaxSum(r, j):

• Inicializamos a última linha: f[N][j] = D[N][j] para todo j.
• Iteramos das linhas N-1 até 1: f[r][j] = max(f[r+1][j], f[r+1][j+1]) + D[r][j].

O resultado final será f[1][1].

Código Pascal para DP Iterativa:

1 // Por LYLtim
2 // 2010.10.18
3 uses math;
4 var n,i,j:byte;
5     a:array[1..10,1..10]of word;
6     f:array[1..10,1..10]of word;
7 begin
8     assign(input,'tower.in');reset(input);
9     assign(output,'tower.out');rewrite(output);
10     readln(n);
11     for i:=1 to n do
12         begin
13             for j:=1 to i do
14                 read(a[i,j]);
15             readln;
16         end;
17     fillchar(f,sizeof(f),0);
18     for i:=1 to n do f[n,i]:=a[n,i];
19     for i:=n-1 downto 1 do
20         for j:=1 to i do
21             f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];
22     writeln('max=',f[1,1]);
23     close(input);close(output);
24 end.

Otimização 3: Redução de Espaço

Observamos que, ao calcular a linha r, dependemso apenas dos valores da linha r+1. Isso significa que não precisamos armazenar todo o array 2D f. Podemos usar um array unidimensional maxSum[100] para armazenar os resultados da linha atual que estamos calculando (ou a linha anterior, dependendo da direção da iteração).

Uma otimização ainda maior é possível: podemos sobrescrever os valores do array de entrada D diretamente. Após o cálculo, a última linha do array D conterá os valores de MaxSum para a penúltima linha, e assim por diante, até que D[1][1] contenha o resultado final.

Código C++ para DP Iterativa com Otimização de Espaço:

1 // Por LYLtim
2 // 2015.2.11
3 #include <iostream>
4 #include <algorithm>
5 using namespace std;
6 int main()
7 {
8     int n, d[101][101];
9     cin >> n;
10     for (int i = 1; i <= n; i++)
11         for (int j = 1; j <= i; j++)
12             cin >> d[i][j];
13     for (int i = n-1; i >= 1 ; i--)
14         for (int j = 1; j <= i; j++)
15             d[i][j] = max(d[i+1][j], d[i+1][j+1]) + d[i][j]; // Correção: sobrescreve d[i][j]
16     cout << d[1][1]; // O resultado final está em d[1][1]
17 }
</algorithm></iostream>

Nota: O código C++ fornecido na pergunta original continha um erro na linha de atualização, que foi corrigido acima para sobrescrever d[i][j] corretamente.

Guia Geral para Converter Recursão em DP

A conversão de uma solução recursiva para uma solução de programação dinâmica geralmente segue estes passos:

1. Identificar Subproblemas: Divida o problema original em subproblemas menores que compartilham a mesma estrutura. A solução para o problema original depende das soluções dos subproblemas.
2. Definir Estados: Um "estado" representa um conjunto de variáveis que definem um subproblema específico. O "valor" de um estado é a solução para esse subproblema. O conjunto de todos os estados forma o "espaço de estados".
3. Determinar Estado Inicial (Casos Base): Identifique os estados mais simples ou de fronteira e defina seus valores. No exemplo do triângulo, os estados iniciais são os números na base do triângulo.
4. Estabelecer Relação de Transição de Estado (Equação de Recorrência): Defina como calcular o valor de um estado com base nos valores de outros estados. Esta é a fórmula que descreve como passar de um ou mais estados com valores conhecidos para um novo estado.

Características dos Problemas Resolvíveis com DP:

• Subestrutura Ótima: A solução ótima para o problema principal contém soluções ótimas para seus subproblemas.
• Propreidade de Ausência de Memória Posterior (Sem Efeitos Posteriores): Uma vez que um estado é determinado, a evolução futura do processo depende apenas desse estado, e não do caminho percorrido para alcançá-lo.