Dynamic programming requires two key properties: Overlapping subproblems and what else?
Show answer
Optimal substructure
Optimal substructure means that an optimal solution to a problem contains within it optimal solutions to subproblems. This allows for a recursive formulation that can be memoized or computed via a table.
Also asked as:
- Besides overlapping subproblems, what is the other essential property a problem must have to be solved via dynamic programming?