o principal diferença entre dividir e conquistar e a programação dinâmica é que o dividir e conquistar combina as soluções dos subproblemas para obter a solução do problema principal, enquanto a programação dinâmica usa o resultado dos subproblemas para encontrar a solução ótima do problema principal.

Dividir para conquistar e programação dinâmica são dois algoritmos ou abordagens para resolver problemas. O algoritmo de divisão e conquista divide o problema em subproblemas e combina essas soluções para encontrar a solução para o problema original. No entanto, a programação dinâmica não resolve os subproblemas de forma independente. Ele armazena as respostas dos subproblemas para usá-los em problemas semelhantes.

Divida para conquistar, programação dinâmica

O que é dividir para conquistar

Dividir para conquistar divide o problema principal em pequenos subproblemas. Os subproblemas são divididos repetidamente. Em um ponto, haverá um estágio em que não podemos dividir ainda mais os subproblemas. Então, podemos resolver cada subproblema independentemente. Finalmente, podemos combinar as soluções de todos os subproblemas para obter a solução para o problema principal.

Existem três etapas principais para dividir e conquistar. Eles são os seguintes.

Dividir (quebrar) - Envolve a divisão do problema principal em uma coleção de subproblemas

Conquistar (resolver) - Envolve resolver cada subproblema separadamente

Combinar (fundir) - Une as soluções dos subproblemas para obter a solução do problema principal

O que é programação dinâmica

A programação dinâmica divide o problema principal em subproblemas menores, mas não os resolve de forma independente. Ele armazena os resultados dos subproblemas para usar ao resolver subproblemas semelhantes. O armazenamento dos resultados dos subproblemas é denominado memorização. Antes de resolver o subproblema atual, ele verifica os resultados dos subproblemas anteriores. Finalmente, ele verifica os resultados de todos os subproblemas para encontrar a melhor solução ou a solução ótima. Este método é eficaz porque não calcula as respostas repetidamente. Normalmente, a programação dinâmica é usada para otimização.

Os elementos da programação dinâmica são os seguintes.

Subproblemas simples - Divida o problema original em pequenos subproblemas que possuem uma estrutura semelhante

Subestrutura ótima do problema - A solução ótima para o problema principal está dentro da solução ótima para seus subproblemas

Subproblemas sobrepostos - Situações de resolução dos mesmos subproblemas repetidas vezes

Diferença entre dividir e conquistar e programação dinâmica

Definição

Dividir para conquistar é um algoritmo que divide recursivamente um problema em dois ou mais subproblemas do mesmo tipo ou de tipo relacionado até que se torne simples o suficiente para ser resolvido diretamente. No entanto, a programação dinâmica é um algoritmo que ajuda a resolver com eficiência uma classe de problemas que têm subproblemas sobrepostos e propriedade de subestrutura ótima.

Modelo

A principal diferença entre dividir e conquistar e a programação dinâmica é que dividir e conquistar é recursiva, enquanto a programação dinâmica é não recursiva.

Subproblemas

Em dividir para conquistar, os subproblemas são independentes uns dos outros. No entanto, na programação dinâmica, os subproblemas são interdependentes. Portanto, esta é outra grande diferença entre dividir e conquistar e a programação dinâmica.

Consumo de Tempo

O consumo de tempo é outra diferença entre dividir e conquistar e a programação dinâmica. Dividir e conquistar resolve cada subproblema de forma independente. Portanto, é mais demorado. A programação dinâmica, por outro lado, usa as respostas dos subproblemas anteriores. Portanto, é menos demorado.

Eficiência

A eficiência também faz a diferença entre dividir e conquistar e a programação dinâmica. A programação dinâmica é mais eficiente do que dividir para conquistar.

Formulários

Merge sort, quicksort e pesquisa binária usam dividir e conquistar, enquanto a multiplicação da cadeia de matrizes e a árvore de pesquisa binária ideal usam programação dinâmica.

Conclusão

A principal diferença entre dividir e conquistar e a programação dinâmica é que dividir e conquistar combina as soluções dos subproblemas para obter a solução do problema principal, enquanto a programação dinâmica usa o resultado dos subproblemas para encontrar a solução ótima do problema principal.

Referência:

1. “Introdução ao DAA Divide and Conquer - Javatpoint.” Www.javatpoint.com, disponível aqui.2. “Introdução à Programação Dinâmica - Javatpoint.” Www.javatpoint.com, disponível aqui.3. Programação dinâmica | Steps to Design & Applications |, Education 4u, 2 de abril de 2018, disponível aqui.4. “Programação dinâmica”, Programiz. com, disponível aqui.

Cortesia de imagem:

1. “Diagrama de algoritmo de ordenação de mesclagem” Por VineetKumar na Wikipedia em inglês - Transferido de en.wikipedia para Commons por Eric Bauman usando CommonsHelper (Domínio Público) via Commons Wikimedia2. “Fibonacci dynamic programming” Por en: Usuário: Dcoatzee, rastreado por Usuário: Stannered - en: Imagem: Fibonacci dynamic programming.png (Domínio Público) via Commons Wikimedia