Para determinar se podemos otimizar um problema usando programação dinâmica, podemos examinar os dois critérios formais dos problemas de DP. Também darei um atalho em um segundo que tornará esses problemas muito mais rápidos de serem identificados.
Vamos começar com a definição formal.
Um problema pode ser otimizado usando programação dinâmica se:
tem uma subestrutura ótima.
tem subproblemas sobrepostos.
Se um problema atender a esses dois critérios, sabemos com certeza que ele pode ser otimizado por meio da programação dinâmica.