Question

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

(a) Dynamic programming

(b) Greedy

(c) Divide and conquer

(d) Recursion

This question was posed to me in an interview.

My question is taken from Dynamic Programming topic in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right choice is (c) Divide and conquer

Best explanation: In divide and conquer, the problem is divided into smaller non-overlapping subproblems and an optimal solution for each of the subproblems is found. The optimal solutions are then combined to get a global optimal solution. For example, mergesort uses divide and conquer strategy.