Larback - Retornando conhecimento

A fila do lado sempre anda mais rápido. Não adianta trocar de fila.

Exemplo de programação dinâmica em java

A técnica de desenvolvimento de algoritmos "programação dinâmica" consiste, basicamente, em utilizar uma tabela para evitar que problemas repetidos sejam resolvidos pelas chamadas recursivas.

Como exemplo, vamos calular um número da sequência fibonacci
A resolução mais comum é a recursiva:
static int fibo(int n){
        if (n<2)
            return n;
        else
            return fibo(n-1)+fibo(n-2);
    }
O problema desse código é que sua complexidade é exponencial - O(2^n) - Isso acontece porque o mesmo problema é resolvido repetidas vezes. Para evitar isso, utilizando programação dinâmica, criamos um vetor onde os valores já calculados são armazenados:
    static long[] tFibo;
 static long fiboPD(int n){
        if(tFibo[n]!=-1) // -1 é um valor qualquer que nunca ocorrerá. O vetor deve ter todas as posições inicializadas com esse valor
            return tFibo[n];
        else
            return tFibo[n] = fiboPD(n-1)+fiboPD(n-2);
    }

    public static void main(String[] args) {
// antes de chamarmos o método, vamos inicializar a tabela com um pre-processamento, vamos inicializar todos os valores com o nosso valor coringa (no caso -1) e colocar os valores bases nas posições 0 e 1
       int n=50;
       tFibo = new long[n+1];
       for(int i=2;i<=n;i++)
           tFibo=-1;
       tFibo[0] = 0;
       tFibo[1] = 1;
       
       System.out.println(fiboPD(n));
       }
Qualquer dúvida, utilizem nosso grupo.


Bons estudos.