patternModerate
Proof of an Optimal substructure in Dynammic Programming?
Viewed 0 times
optimalprogrammingdynammicsubstructureproof
Problem
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?
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?
Solution
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:
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.
Context
StackExchange Computer Science Q#28111, answer score: 11
Revisions (0)
No revisions yet.