O que é programação dinâmica?

A programação dinâmica, quando se refere ao campo da ciência da computação, descreve um grupo de algoritmos de computador semelhantes, destinados a resolver problemas complexos, dividindo o problema em conjuntos de problemas menores. Criada pela primeira vez por Richard Bellman na década de 1950, a programação dinâmica trabalha com problemas que são subproblemas sobrepostos ou subestruturas ideais. Para entender como a programação dinâmica funciona, é melhor entender o conceito por trás desses dois termos.

Os subproblemas sobrepostos descrevem equações complicadas que, quando divididas em conjuntos menores de equações, reutilizam partes das equações menores mais de uma vez para obter uma resposta. Por exemplo, uma equação matemática indicada para calcular todos os resultados possíveis usando um conjunto de números pode calcular o mesmo resultado várias vezes enquanto calcula outros resultados apenas uma vez. A programação dinâmica diria a esse problema que, depois de calcular o resultado pela primeira vez, ele deve salvá-lo e inserir a resposta na equação posteriormente, em vez de calculá-lo novamente. Ao lidar com processos e equações complexos e longos, isso economiza tempo e cria uma solução mais rápida usando muito menos etapas.

Subestruturas ideais criam uma solução, encontrando a melhor resposta para todos os subproblemas e, em seguida, criando a melhor resposta geral. Depois de dividir um problema complexo em problemas menores, o computador usa um sistema matemático para determinar qual é a melhor resposta para cada problema. Ele calcula a resposta para o problema original a partir das respostas menores. Existem falhas neste processo. Embora ela ofereça a solução que funciona melhor matematicamente, ela pode ou não ser a melhor solução na vida real, dependendo do tipo de problema e como ele se relaciona com o mundo real.

Durante qualquer uma dessas operações, o algoritmo de programação dinâmica tenta encontrar o caminho mais curto para a solução. Pode ser uma das duas abordagens para fazer isso. A abordagem de cima para baixo divide a equação em equações menores e reutiliza as respostas para essas equações quando necessário. A abordagem de baixo para cima tenta resolver o menor valor matemático após quebrar a equação e, em seguida, segue seu caminho em direção ao maior a partir daí. Ambas as abordagens economizam tempo, mas a programação dinâmica funciona apenas quando o problema original pode se decompor em equações menores que em algum momento são reutilizadas para resolver a equação.