4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Step 1: understand that all you do is prove correctness of a recurrence. Step 2: Use induction. $\endgroup$
    – Raphael ♦
    Jun 30, 2014 at 21:57

2 Answers 2

Reset to default
11
$\begingroup$

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:

  1. Set up your (candidate) dynamic programming recurrence.
  2. Prove it correct by induction.
  3. Formulate the (iterative, memoizing) algorithm following the recurrence.
Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ That is the best description of dynamic programming I've seen. Most of definitions/descriptions are so vague that almost nonsensical. Because of that I strugled to understand the concept for veeery long time. $\endgroup$
    – Trismegistos
    Sep 3, 2015 at 14:02
6
$\begingroup$

Most students are indeed puzzled by this property: it looks obvious when they read it, but yet they can't manage to apply it to solve problems. First note that when you express the objective by recursion on the subproblems, the expression has to be monotonic and the subproblems must be independent. For instance, in the travelling salesman problem, you cannot solve it by a call to find the best path from A to B and another from B to A: the two subproblems have to decide how to divide the nodes between them, since the salesman cannot pass two times in the same node.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.