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?