# Why do we need optimal substructure for dynamic programming?

Cormen and others in their book on algorithms in chapter "15 Dynamic Programming" repeat again and again that we need to prove that "a problem exhibits optimal substructure". A problem exhibits optimal substructure iff (if a solution to a problem is optimal, then each of its subsolutions to a corresponding subproblem is optimal). I guess that we need this optimal substructure property to prove that the algorithm of dynamic programming is correct. I fail to see how this property helps.

Here is the algorithm of dynamic programming. Given a problem, for every choice, combine optimal subsolutions to each subproblem. In order to prove that the algorithm is correct, we need to prove that the combination of optimal subsolutions is optimal. This is the converse of the optimal substructure property.

Though my question seems abstract, it can be applied to any specific problem that Cormen and others present. For all problems, correctness is proved via the optimal substructure property, hence all these proofs are incorrect. (Of course, the algorithms are correct.)

I have searched for similar questions and found one (common keywords). However, the question does not make sense to me: proofs are not machines, proofs do not "work". So I can't use those answers.

• That the (simple) combination if optimal solutions to subproblems yields an optimal solution to the larger problem is what "optimal substructure" typically means. – Pontus May 5 '17 at 12:29