A programação dinâmica é tipicamente aplicada para problemas de otimização. Existe na programação dinâmica uma similaridade ao método “dividir para conquistar”, visto que ambos resolvem um problema através da combinação da solução de subproblemas. Uma das diferenças reside no fato de o método “dividir para conquistar” dividir o problema original em subproblemas independentes, enquanto a programação dinâmica divide o problema original em subproblemas gerados de subproblemas anteriores.

Sobre programação dinâmica, considere as afirmativas a seguir.

I − Algoritmos de programação dinâmica resolvem cada problema apenas uma vez, salvando a resposta em uma tabela a fim de evitar que o problema necessite ser resolvido novamente, caso reapareça.

II − O objetivo da programação dinâmica é encontrar a solução ótima para um problema e não uma solução ótima qualquer.

III − Uma possível aplicação para a programação dinâmica é na biologia, na comparação de DNA de dois ou mais organismos, através do problema da maior subsequência comum de caracteres.

É(São) correta(s), apenas, a(s) afirmativa(s):