Proof of an Optimal substructure in Dynammic Programming? Could someone please explain how exactly the proof of optimal substructure property in dynamic programming problems works?

They usually say:


  Let's say the global optimal solution is A, and B is part of the solution. So B must the optimal solution of the subproblem, because if it weren't, then A wouldn't be the global optimal. 


It makes some  sense to me, but I think this would work with any non-dynamic problem (the property), or maybe it is because I still don't get how it works.

Can someone please help? How does the contradiction work?
There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it.

You should do the following:


Set up your (candidate) dynamic programming recurrence.
Prove it correct by induction.
Formulate the (iterative, memoizing) algorithm following the recurrence.