Different way of proving optimal substructure?

Viewed 402

For the optimal substructure property, it states that an optimal solution for a given problem can be obtained by combining optimal solutions of its subproblems.

We can write this as Opt(given problem) = f(Opt(subproblem 1), Opt(subproblem 2), ...). Where f combines optimal solutions to the subproblems.

Usually, to prove optimal substructure, we show that if $Opt(given problem)$ is in fact an optimal solution, then Opt(subproblem 1), Opt(subproblem 2), ..., are also all optimal. This is seen for example in the Cormen (CLRS) book.

My question is: can we prove the converse? That is, we show that if Opt(subproblem 1), Opt(subproblem 2), ..., are all optimal, then Opt(given problem) is also optimal?

0 Answers
Related