Euler 18 - Maximum Path Sum

Seja o seguinte problema do projeto Euler.

Dado um triângulo de números calcular a soma máxima entre os caminhos possíveis desde o vértice até a um valor na base do triângulo.

No exemplo seguinte, a soma máxima é 23 resultante da soma dos elementos no caminho a vermelho.

3
7 4
2 4 6
8 5 9 3

Considerem que leem o input para uma matriz Java triangle[][] ficando os valores neste formato:

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

Uma abordagem Greedy que parece funcionar: começando por cima, escolher o elemento maior entre os dois possíveis da linha abaixo:

3
7 4
2 4 6
8 5 9 3

int solveGreed(int[][] triangle) {
    int sum=triangle[0][0];
    
    for(int i=1, currentCol=0; i<SIZE; i++) {   // for each row
        if (triangle[i][currentCol] < triangle[i][currentCol+1])
            currentCol++;
        sum += triangle[i][currentCol];
    }
    return sum;
}

mas não é difícil encontrar um contra-exemplo:

3
7 4
2 4 6
8 5 9 30

Uma outra abordagem é a força bruta, ou seja, testar todas as hipóteses. Para um triângulo de altura N existem 2^(N-1) caminhos possíveis. Podemos usar bitmasks: cada caminho é representado por N-1 bits de um número inteiro (eg, bit 0 desce pela esquerda, 1 pela direita). Por exemplo, o número 6 cuja representação binária é 110 representa o caminho máximo descrito acima. Já o número 3 é 011 representa o caminho

3
7 4
2 4 6
8 5 9 3

Assim podemos implementar este algoritmo:

int solveBruteForce(int[][] triangle) {
    int maxSum =0;
    int nPaths = 2 << (SIZE-1);
    
    for(int i=0; i<nPaths; i++) {
        int sum = triangle[0][0];
        for (int j=0, index=0; j<SIZE-1; j++) {
            index += i >> j & 1;
            sum   += triangle[j+1][index];
        }
        if (sum>maxSum)
            maxSum = sum;
    }
    return maxSum;
}

Mas a força bruta tem complexidade exponencial na altura N do triângulo, O(2^N)...

Podemos usar a programação dinâmica para calcular a resposta em O(N^2).

Uma abordagem passa por guardar em cada linha (a contar de cima), a soma máxima atual conseguida pelos caminhos parciais que começam no vértice. No exemplo acima temos

3 3 3 3
7 4 10 7 10 7 10 7
2 4 6 => 2 4 6 => 12 14 13 => 12 14 13
8 5 9 3 8 5 9 3 8 5 9 3 20 19 23 16

vamos descendo linha a linha, fazendo as somas de acordo com os máximos parciais de cima. Quando terminamos este processo, o resultado que queremos será o maior valor da linha da base.

O código:

int solveDP(int[][] triangle) {
    
    for(int i=1; i<SIZE; i++) {   // for each row
        // treat extremities (just one possible sum)
        triangle[i][0] += triangle[i-1][0];
        triangle[i][i] += triangle[i-1][i-1];
        
        for(int j=1; j<i; j++)
            triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
    }

    int maxSum=0;
    for(int i=0; i<SIZE; i++)
        if (triangle[SIZE-1][i] > maxSum)
            maxSum = triangle[SIZE-1][i];
    return maxSum;
}

Podem também pensar como se poderia resolver com programação dinâmica começando da base para o vértice.

Para um triângulo com 25 linhas, estes são os resultados e os tempos obtidos:

Brute Force: 1867, time: 1046 ms
Greed: 1546, time: 0 ms
DP: 1867, time: 0 ms

Como seria de esperar, a abordagem gananciosa obteve uma solução sub-óptima. E observamos a diferença de desempenho da força bruta que demorou mais de um segundo enquanto a solução de programação dinâmica demorou menos de 1 ms.

Um obrigado ao Diogo Sousa por me enviar este problema.