Optimal substructure in Dynamic Programing

Question

I have been trying to understand Dynamic Programming, and what I understood is that there are two parts of DP.

1. Optimal substructures
2. Overlapping subproblems

I understand the second one, but I am not able to understand the first one.

Answer 1

Optimal substructure means, that any optimal solution to a problem of size n, is based on an optimal solution to the same problem when considering n' < n elements.

That means, when building your solution for a problem of size n, you split the problem to smaller problems, one of them of size n'. Now, you need only to consider the optimal solution to n', and not all possible solutions to it, based on the optimal substructure property.

An example is the knapsack problem:

D(i,k) = min { D(i-1,k), D(i-1,k-weight(i)) + cost(i) }

The optimal substructure assumption here, is D(i,k) can check only optimal solutions to D(i-1,k), and none optimal solutions are not considered.

An example where this does not hold is the Vertex Cover problem.

If you have a graph G=(V,E), assume you have an optimal solution to a subgraph G'=(V',E[intersection]V'xV') such that V' <= V - the optimal solution for G does not have to be consisted of of the optimal solution for G'/