Question

We mentioned in class that dynamic programming and greedy algorithms can only be used to solve problems that exhibit Optimal Substructure. Do Divide and Conquer algorithms require the problem to exhibit Optimal Substructure as well, or could we use Divide and Conquer to solve problems that do not exhibit optimal substructure?

Answer 1

Step-by-step explanation:

divide and conquer algorithm is a mathematical approach to recursively break down the problem into smaller sub-parts until it becomes simple enough to be solved directly.

it is a design pattern to solve the problems and does not exhibit or aim to provide optimal solutions.