What does it mean for a problem to have optimal substructure?
› View/hide answer
A globally optimal solution can be found by combining solutions to local subproblems.
What does it mean for a problem to have overlapping subproblems?
› View/hide answer
An optimal solution involves solving the same problem multiple times.