Como discutimos no Conjunto 1 , a seguir estão as duas propriedades principais de um problema que sugere que o problema dado pode ser resolvido usando a programação dinâmica: 
1) Subproblemas sobrepostos
2) Subestrutura  ótima 

Já discutimos a propriedade Overlapping Subproblem no Conjunto 1 . Vamos discutir a propriedade da Substrutura Ótima aqui. 

2) Subestrutura ótima: Um dado problema tem uma propriedade ótima de subestrutura se a solução ótima do problema dado pode ser obtida usando soluções ótimas de seus subproblemas. 

Por exemplo, o problema do caminho mais curto tem a seguinte propriedade de subestrutura ótima: 
Se um nó x está no caminho mais curto de um nó de origem u ao nó de destino v, então o caminho mais curto de u a v é a combinação do caminho mais curto de u a x e o mais curto caminho de x a v. O algoritmo padrão All Pair Shortest Path como Floyd – Warshall e o algoritmo Single Source Shortest path para arestas de peso negativo como Bellman – Ford são exemplos típicos de Programação Dinâmica. 

Por outro lado, o problema do Caminho Mais Longo não possui a propriedade Substrutura Ótima. Aqui, por caminho mais longo, queremos dizer o caminho simples mais longo (caminho sem ciclo) entre dois nós. Considere o seguinte gráfico não ponderado fornecido no livro CLRS . Existem dois caminhos mais longos de q para t: q → r → t eq → s → t. Ao contrário dos caminhos mais curtos, esses caminhos mais longos não têm a propriedade de subestrutura ideal. Por exemplo, o caminho mais longo q → r → t não é uma combinação do caminho mais longo de q para re o caminho mais longo de r para t, porque o caminho mais longo de q para r é q → s → t → re o caminho mais longo de r a t é r → q → s → t. 

Estaremos cobrindo alguns problemas de exemplo em postagens futuras sobre Programação Dinâmica . 

<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="374" src="https://www.youtube.com/embed/JWTqsNvtwP4?feature=oembed" width="665"></iframe>

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima. 

Referências:  
http://en.wikipedia.org/wiki/Optimal_substructure  
livro CLRS