Two key ingredients for an optimization problem to be suitable for a dynamic-programming

1. optimal substructures

2. overlapping subproblems

• The development of a dynamic-programming algorithm has three basic components:

– The recurrence relation (for defining the value of an optimal solution);

– The tabular computation (for computing the value of an optimal solution);

– The traceback (for delivering an optimal solution).