Can someone please explain optimal substructure in dynamic programing?
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 sub problems
I understand the 2nd one, but nor able to get 1st one.
Can someone please explain with examples in plain English which is easy to understand?
Answer
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'/