Qual é a diferença entre memorização e programação dinâmica?

Qual é a diferença entre memorização e programação dinâmica? Eu acho que a programação dinâmica é um subconjunto de memorização. Está certo?

Artigo relevante sobre Programming.Guide: Programação dinâmica vs memorização vs tabulação

Qual é a diferença entre memorização e programação dinâmica?

Memoização é um termo que descreve uma técnica de otimização em que você armazena em cache os resultados calculados anteriormente e retorna o resultado em cache quando o mesmo cálculo é necessário novamente.

A programação dinâmica é uma técnica para resolver problemas de natureza recursiva, iterativamente, e é aplicável quando os cálculos dos subproblemas se sobrepõem.

A programação dinâmica geralmente é implementada usando tabulação, mas também pode ser implementada usando memorização. Então, como você pode ver, nenhum é um "subconjunto" do outro.

Uma pergunta razoável de acompanhamento é: Qual é a diferença entre tabulação (a típica técnica de programação dinâmica) e memorização?

Quando você resolve um problema de programação dinâmica usando tabulação, resolve o problema "de baixo para cima ", ou seja, resolvendo todos os subproblemas relacionados primeiro, normalmente preenchendo uma tabela n- dimensional. Com base nos resultados da tabela, a solução para o problema "superior" / original é calculada.

Se você usar a memorização para resolver o problema, faça isso mantendo um mapa dos subproblemas já resolvidos. Você faz isso "de cima para baixo " no sentido de resolver o problema "de cima" primeiro (o que geralmente ocorre novamente para resolver os subproblemas).

Um bom slide daqui (o link está morto, o slide ainda é bom):

• Se todos os subproblemas precisarem ser resolvidos pelo menos uma vez, um algoritmo de programação dinâmica de baixo para cima geralmente supera um algoritmo memorizado de cima para baixo por um fator constante
  • Sem sobrecarga para recursão e menos sobrecarga para manter a tabela
  • Existem alguns problemas para os quais o padrão regular de acesso à tabela no algoritmo de programação dinâmica pode ser explorado para reduzir ainda mais os requisitos de tempo ou espaço
• Se alguns subproblemas no espaço do subproblema não precisarem ser resolvidos, a solução memorizada tem a vantagem de resolver apenas os subproblemas que são definitivamente necessários

Recursos adicionais:

• Wikipedia: Memoização , Programação Dinâmica
• SO Q / A relacionado: Abordagem de memorização ou tabulação para programação dinâmica

A programação dinâmica é um paradigma algorítmico que resolve um problema complexo, dividindo-o em subproblemas e armazenando os resultados dos subproblemas para evitar computar os mesmos resultados novamente.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

Memoização é um método fácil de rastrear soluções resolvidas anteriormente (geralmente implementadas como um par de valores de chave de hash, em oposição à tabulação que geralmente é baseada em matrizes), para que não sejam recalculadas quando forem encontradas novamente. Pode ser usado nos métodos de baixo para cima ou de cima para baixo.

Veja esta discussão sobre memorização vs tabulação.

Portanto, a programação dinâmica é um método para resolver certas classes de problemas, resolvendo relações de recorrência / recursão e armazenando soluções encontradas anteriormente por meio de tabulação ou memorização. Memoização é um método para rastrear soluções para problemas resolvidos anteriormente e pode ser usado com qualquer função que possua soluções determinísticas exclusivas para um determinado conjunto de entradas.

A programação dinâmica é freqüentemente chamada de memorização!

1. Memoização é a técnica de cima para baixo (comece a resolver o problema especificado, decompondo-o) e a programação dinâmica é uma técnica de baixo para cima (comece a resolver a partir do subproblema trivial, até o problema em questão)

2. O DP encontra a solução começando no (s) caso (s) base (s) e segue seu caminho para cima. O DP resolve todos os subproblemas, porque o faz de baixo para cima

   Ao contrário do Memoization, que resolve apenas os subproblemas necessários

3. O DP tem o potencial de transformar soluções de força bruta de tempo exponencial em algoritmos de tempo polinomial.

4. O DP pode ser muito mais eficiente porque sua interação

   Pelo contrário, a memorização deve pagar a sobrecarga (geralmente significativa) devido à recursão.

Para ser mais simples, o Memoization usa a abordagem de cima para baixo para resolver o problema, ou seja, começa com o problema principal (principal), depois o divide em subproblemas e os soluciona da mesma forma. Nesta abordagem, o mesmo subproblema pode ocorrer várias vezes e consumir mais ciclo da CPU, aumentando assim a complexidade do tempo. Enquanto na programação dinâmica, o mesmo subproblema não será resolvido várias vezes, mas o resultado anterior será usado para otimizar a solução.

(1) Memoização e DP, conceitualmente , são realmente a mesma coisa. Porque: considere a definição de DP: "subproblemas sobrepostos" "e subestrutura ideal". A memorização possui totalmente esses 2.

(2) A memorização é DP, com o risco de estouro de pilha e a recursão é profunda. O DP de baixo para cima não tem esse risco.

(3) A memorização precisa de uma tabela de hash. Espaço adicional e algum tempo de pesquisa.

Então, para responder à pergunta:

- Conceitualmente , (1) significa que são a mesma coisa.

-Tendo em conta (2), se você realmente quiser, a memorização é um subconjunto do DP, no sentido de que um problema solucionável pela memoização será solucionável pelo DP, mas um problema solucionável pelo DP pode não ser solucionável pela memoização (porque pode sobrecarregar).

- Levando em conta (3), eles têm pequenas diferenças no desempenho.

Da wikipedia:

Memoização

Na computação, a memorização é uma técnica de otimização usada principalmente para acelerar programas de computador, evitando que as chamadas de função repitam o cálculo dos resultados para entradas processadas anteriormente.

Programaçao dinamica

Em matemática e ciência da computação, a programação dinâmica é um método para resolver problemas complexos, dividindo-os em subproblemas mais simples.

Ao dividir um problema em subproblemas menores / mais simples, geralmente encontramos o mesmo subproblema mais de uma vez - então usamos Memoization para salvar os resultados dos cálculos anteriores e não precisamos repeti-los.

A programação dinâmica geralmente encontra situações em que faz sentido usar a memorização, mas você pode usar uma das técnicas sem necessariamente usar a outra.

A memorização e a programação dinâmica resolvem o subproblema individual apenas uma vez.

A memorização usa recursão e funciona de cima para baixo, enquanto a programação dinâmica se move na direção oposta, resolvendo o problema de baixo para cima.

Abaixo está uma analogia interessante -

De cima para baixo - Primeiro você diz que vou dominar o mundo. Como você vai fazer isso? Você diz que eu assumirei a Ásia primeiro. Como você vai fazer isso? Eu assumirei a Índia primeiro. Vou me tornar o ministro-chefe de Delhi, etc. etc.

Bottom-up - Você diz que me tornarei o CM de Delhi. Então assumirei a Índia, depois todos os outros países da Ásia e, finalmente, dominarei o mundo.

Eu gostaria de ir com um exemplo ;

Problema:

Você está subindo uma escada. São necessários n passos para chegar ao topo.

Cada vez que você pode subir 1 ou 2 passos. De quantas maneiras distintas você pode subir ao topo?

Recursão com memorização

Desta forma, estamos podando (uma remoção do excesso de material de uma árvore ou arbusto) a árvore de recursão com a ajuda da matriz de notas e reduzindo o tamanho da árvore de recursão até nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Programaçao dinamica

Como podemos ver, esse problema pode ser dividido em subproblemas e contém a propriedade ideal da subestrutura, ou seja, sua solução ideal pode ser construída eficientemente a partir de soluções ideais de seus subproblemas, podemos usar a programação dinâmica para resolver esse problema.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Os exemplos são de https://leetcode.com/problems/climbing-stairs/

Pense em duas maneiras,

1. Dividimos o problema maior em subproblemas menores - abordagem de cima para baixo.
2. Começamos pelo menor subproblema e alcançamos o maior problema - abordagem de baixo para cima.

Em Memoization , vamos com (1.) onde salvamos cada chamada de função em um cache e retornamos a partir daí. É um pouco caro, pois envolve chamadas recursivas.

Na Programação Dinâmica , seguimos com (2.) onde mantemos uma tabela, de baixo para cima, resolvendo subproblemas usando os dados salvos na tabela, comumente referidos como dp-table.

Nota:

• Ambos são aplicáveis ​​a problemas com subproblemas sobrepostos.

• A memorização executa comparativamente baixa para o DP devido às despesas gerais envolvidas durante as chamadas de função recursivas.

• A complexidade de tempo assintótica permanece a mesma.

Na programação dinâmica ,

• Sem sobrecarga para recursão, menos sobrecarga para manter a tabela.
• O padrão regular dos acessos à tabela pode ser usado para reduzir os requisitos de tempo ou espaço.

Na memorização ,

• Alguns subproblemas não precisam ser resolvidos.