why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire problem .So what is the difference in terminology of sub-problems in divide and conquer and dynamic programming except for the fact that in the latter case we have overlapping sub-problems since both tend to imply that we have some sub-problems which combine to give an optimal solution to entire problem so in case of divide and conquer can we say that each sub-problem also gives us optimal solution ?
The CLRS definition of optimal substructure:
A problem exhibits optimal substructure if any optimal solution to the problem contains within it optimal solutions to subproblems.
This make sense for both methods.
Divide&Conquer is used when subproblems are independent, there is no overlapping subproblems. In this case you just combine solutions to resolve the main problem.
Dynamic Programming is used when subproblems are dependent, there are overlapping subproblems and results are typically stored in some data structure for later reuse.