Q. What is the main characteristic of a problem that can be solved using dynamic programming?
A.
It can be solved in linear time
B.
It has optimal substructure
C.
It requires sorting
D.
It can be solved using a greedy approach
Solution
A problem that can be solved using dynamic programming must have optimal substructure, meaning the optimal solution can be constructed from optimal solutions of its subproblems.
