Q. What is the primary characteristic of a problem that can be solved using dynamic programming?
A.
Optimal substructure
B.
Linear structure
C.
Random access
D.
Static data
Solution
A problem that can be solved using dynamic programming must have an optimal substructure, meaning optimal solutions to subproblems can be used to construct optimal solutions to larger problems.