Question: what are the basic characteristics of dynamic programming?
Answer: Optimal Substructure: If an optimal solution contains optimal sub solutions then a problem exhibits optimal substructure.
Overlapping subproblems: When a recursive algorithm would visit the same subproblems repeatedly, then a problem has overlapping subproblems.