© TippaPatt/Shutterstock.com
A programação dinâmica (DP) é uma área exigente da programação de computadores, com habilidades e técnicas específicas para resolver problemas. Sim, você se sairá bem como engenheiro de software sem ela, mas a programação dinâmica tem importantes aplicações do mundo real e você pode ser questionado sobre ela em uma entrevista de desenvolvedor.
Se você é novo em dinâmica programação ou deseja atualizar suas habilidades, este breve artigo explica o que é programação dinâmica, com exemplos e onde você pode desenvolver suas habilidades de DP online.
O que é programação dinâmica?
Na programação de computadores, a programação dinâmica (DP) é um método de solução de problemas que estrutura e simplifica problemas complicados dividindo-os em uma cascata de subproblemas sobrepostos. Ao aplicar DP, várias classes de problemas podem ser resolvidas com eficiência.
DP tem origem na matemática e é aplicável em diversas áreas, desde bioinformática até engenharia de recursos hídricos e economia.
Como funciona a programação dinâmica na ciência da computação?
A programação dinâmica deve ser aplicada adequadamente para ser usada na programação de computadores. Um problema deve ter duas características para ser adequado para DP:
Uma subestrutura ótima: Um problema especificado tem propriedade de subestrutura ótima se sua solução ótima puder ser derivada de soluções ótimas de seus subproblemas. Subproblemas sobrepostos: O problema em questão deve poder ser dividido em uma cascata de subproblemas reutilizáveis ou um algoritmo recursivo que pode resolver repetidamente subproblemas sem gerar novos.
Estas duas propriedades são fundamentais para usar DP. Se a solução ótima for encontrada usando subproblemas não sobrepostos, o DP não pode ser usado. Em vez disso, dividir para conquistar é usado. Da mesma forma, algoritmos de classificação como merge sort e quick sort não são DP.
Recursão e programação dinâmica
Recursão é a chave propriedade das subestruturas ótimas usadas em DP. A recursão é simplesmente um processo que se repete, como quando você fica entre dois espelhos e seu reflexo é repetido várias vezes (o efeito Droste).
As subestruturas ótimas têm cascatas de problemas que se resolvem continuamente e o problema principal recursivamente.
Um algoritmo recursivo em DP não gera novos subproblemas, mantendo a quantidade de espaço tomados pelos subproblemas sobrepostos individuais pequenos. Idealmente, os mesmos subproblemas devem ser resolvidos repetidamente.
Tipos principais de programação dinâmica?
Existem dois tipos ou métodos de DP que dependem de como você aborda um problema. Ambos os métodos usam soluções de memoização, armazenamento e tabulação para que possam ser recuperadas rapidamente, economizando o tempo de repetição do cálculo.
Top-down
Na abordagem top-down, a solução de um problema é recursiva, permitindo a memorização de soluções para os subproblemas sobrepostos. Novos subproblemas subseqüentes são resolvidos consultando o cache de dados memorizados para ver se uma solução já está presente. Se o subproblema não foi resolvido anteriormente, ele e sua solução são adicionados ao cache de memoização.
O DP de cima para baixo é simples de entender e usar, pois facilita a solução direcionada de subproblemas. Você pode depurá-lo facilmente, mas essa abordagem de recursão pode usar muita memória cache, o que pode levar a erros de estouro de pilha.
Bottom-up
A abordagem bottom-up, também conhecida como tabulação ou preenchimento de tabela, usa a tabulação para criar um registro de subproblemas e soluções armazenados. Em seguida, ele usa os subproblemas resolvidos tabulados para uma reformulação de baixo para cima do problema. Subproblemas menores são resolvidos, com as soluções aproveitadas para resolver subproblemas maiores. O loop For pode ser usado para iterar os subproblemas.
Exemplo: programação dinâmica e a série Fibonacci
Um exemplo prático de programação dinâmica em ação trabalhando com a série Fibonacci:
0, 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55…
Com os números de Fibonacci (Fn), qualquer número na sequência é a soma dos dois números anteriores. À medida que o valor de’n’em Fn aumenta, a escala e a complexidade do cálculo desses números aumentam.
DP pode ser usado para calcular qualquer número de Fibonacci. Ao usar o DP, você não precisa gerar uma árvore recursiva ou resolver problemas repetidamente. Basta usar os valores previamente calculados. Veja como o código procura uma implementação desta série usando o método descendente:
O código para calcular qualquer número de Fibonacci.
©”TNGD.com
Por que a programação dinâmica é importante?
A programação dinâmica não é uma parte importante do cenário da programação moderna. Isso ocorre porque geralmente não é usado diretamente no desenvolvimento contemporâneo em nível de produção
Muitos engenheiros competentes se estabeleceram sem ter mais do que conhecimento superficial de DP, apesar de fazer parte das principais linguagens de programação como:
PythonJavaScriptRubyPHPPerlLua
O conhecimento prático de DP é valioso para os engenheiros porque pode ajudar os desenvolvedores a criar aplicativos de software mais bem estruturados e mais eficientes.
A moderna arquitetura de serviço compartilhado consiste em aplicativos independentes acessando os recursos (memória, poder de processamento, capacidade de rede, custos) de um pool compartilhado. Código mal estruturado com pouca atenção à resolução de problemas pode levar ao consumo desnecessário de recursos, impactando o desempenho de outras aplicações. O DP ajuda a refinar o código do software para evitar que isso aconteça.
Exemplos do mundo real de programação dinâmica
Existem muitos exemplos de aplicativos de software do mundo real que usam DP para permanecer ágeis e eficientes e minimizar os requisitos do sistema para executá-los. Aqui estão alguns exemplos:
Google Maps: no Google Maps, DP é usado para identificar o caminho mais curto entre um único ponto de partida e uma variedade de destinos. Mecanismos de busca: para calcular o grau de similaridade entre dois conteúdos online.Software de plágio: Desenvolvimento do algoritmo de distância do documento para ajudar na detecção do nível de similaridade entre documentos de texto.Rede: Transferência de dados de uma única fonte para vários receptores diferentes sequencialmente.Verificadores ortográficos: O algoritmo de distância de edição que é usado para quantificar o quão diferentes dois palavras são e calcular o número de operações necessárias para transformar uma palavra em outra.
Bases de dados/cache da base de conhecimento: armazenamento de consultas/solicitações comuns em memória local acessível ou caches. O DP ajuda a evitar a busca repetida de dados comumente usados de servidores, em favor do armazenamento local.
Exemplos de perguntas de entrevista de programação dinâmica
Se você está procurando seu próximo emprego de engenheiro de software ou desenvolvedor, o conhecimento de DP lhe dará uma vantagem nas entrevistas de emprego.
DP é uma grande coisa em entrevistas de tecnologia. As principais empresas de tecnologia, como Google e Amazon, rotineiramente desafiam os candidatos com questões de DP que precisam ser resolvidas no local! Isso é para testar como os desenvolvedores pensam e se eles dividirão as tarefas e encontrarão as maneiras mais eficientes de resolver problemas.
Aqui estão alguns exemplos de perguntas e respostas de entrevistas de programação dinâmica
Além da equação de Fibonacci mostrada acima, aqui estão algumas perguntas comuns sobre entrevistas de programação dinâmica, com exemplos de respostas e soluções:
Pergunta 1: Você pode explicar as vantagens e desvantagens da memoização?
(Dica: esta é uma pergunta sobre os prós e contras da abordagem de cima para baixo em DP)
Resposta:
As vantagens da memoização incluem:
A a codificação é fácilUm problema pode ser abordado escrevendo um wrapper ou anotação que executará automaticamente a função recursiva As respostas podem ser obtidas de um cache e usadas para vários problemas
A principal desvantagem da memoização é que, se você tiver um número grande ou profundo de cálculos, você pode rapidamente ficar sem espaço na pilha.
Pergunta 2: Você está subindo st ares. Você pode subir um ou dois degraus de cada vez. Quantas maneiras diferentes existem para subir até o topo?
(Dica: esta questão é conhecida como o problema de’subir escadas’)
Resposta: Dê uma olhada na abordagem para esta pergunta comum de entrevista de codificação neste vídeo:
Onde posso praticar programação dinâmica?
Desenvolver habilidades em programação dinâmica fortalece as habilidades de pensamento e resolução de problemas dos desenvolvedores. O DP também pode ajudá-lo a pensar de forma mais holística sobre os problemas e desenvolver soluções incomuns, mas eficazes. Se é hora de você obter treinamento ou certificações em DP, aqui estão 3 dos melhores cursos online:
Quando estiver atualizado, a prática leva à perfeição!
Arredondamento up
A programação dinâmica pode não fazer parte da sua pilha de desenvolvedores, mas é importante para as empresas para as quais você deseja trabalhar. Compreender e aprender DP não apenas lhe trará empregos, mas também refinará suas habilidades e o ajudará a escrever o código limpo que seu desenvolvedor líder vai adorar!
O que é programação dinâmica, com exemplos Perguntas frequentes (perguntas frequentes)
O que é memoização?
Na programação, memoização é uma técnica de otimização que armazena os resultados de funções com muitos recursos em um cache para que possam ser chamadas rapidamente se forem necessários novamente. Isso aumenta a velocidade e a eficiência dos programas de computador.
O que é tabulação?
Tabulação é outro termo para a abordagem ascendente da programação dinâmica. Uma tabela é preenchida com soluções dos subproblemas mais baixos e usada para calcular a resposta para subproblemas em níveis mais altos até que a solução original seja encontrada.
O que é dividir e conquistar?
Dividir e conquistar é outra técnica de resolução de problemas. Ele pega o problema original e o divide em subproblemas menores relacionados que podem ser resolvidos independentemente.
A entrevista de codificação do Google é difícil?
Sim. Esta entrevista virtual tem a reputação de ser uma das entrevistas mais difíceis do setor de tecnologia. As perguntas exigem muita pesquisa e prática e geralmente abrangem tópicos relacionados aos serviços do Google. Perguntas de DP são feitas com frequência.
A Amazon pergunta aos candidatos a entrevistas de engenharia de software sobre programação dinâmica?
Sim. A Amazon não hesita em fazer perguntas avançadas de programação dinâmica aos candidatos para separar os despreparados.