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

1. optimal substructures

2. overlapping sub-problems

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

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

- The tracback (for delivering an optimal solution). 

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