Dynamic programming solves problems with overlapping subproblems by computing each distinct subproblem once and reusing its result.

The first step is to identify a state that captures exactly the information needed to describe a subproblem. A recurrence then expresses each state in terms of smaller states.

Two common evaluation styles are:

• top-down memoization: solve states on demand and cache their results;
• bottom-up tabulation: evaluate states in an order that guarantees their dependencies are already known.

The running time is often

$$\text{number of states}\times\text{work per state}.$$

Dynamic programming is especially useful for optimization and counting problems where naive recursion recomputes the same subproblems many times. The central design problem is choosing the right state and recurrence, not merely storing results in a table.