Algorithms | Dynamic Programming | Question 4

Which of the following is NOT a characteristic of dynamic programming?

(A)

Memoization, which involves storing the results of expensive function calls and reusing them.

(B)

Breaking a problem into smaller overlapping subproblems.

(C)

Solving problems in a sequential manner.

(D)

Dynamic programming can be used for problems where the solution has an optimal substructure.

Answer: (C)
Explanation:

Option (A): In dynamic programming Break down the given problem in order to begin solving it. If you see that the problem has already been solved, return the saved answer. If it hasn’t been solved, solve it and save it. This is usually easy to think of and very intuitive, This is referred to as Memoization.

Option (B): It is a big hint for DP if the given problem can be broken up into smaller sub-problems, and these smaller subproblems can be divided into still smaller ones, and in this process, you see some overlapping subproblems. 

Option(C): Dynamic problems can never be solved in a sequential manner.

Option(D): Dynamic programming can be used for problems where the solution has an optimal substructure. this statement is also correct.

Hence (C) is the correct answer.

Quiz of this Question
Please comment below if you find anything wrong in the above post