Dynamic Programming

Tactic

Dynamic programming defines a state, a recurrence, base cases, and an evaluation order. Each state answers one reusable subproblem.

The invariant is that every state is solved from smaller or already known states. In top-down form, the call stack discovers states and a cache remembers them. In bottom-up form, the table order guarantees dependencies are ready.

The main skill is state design. A state should include exactly the information needed to make the remaining decision independent of the earlier path. Too little state gives wrong reuse. Too much state explodes time and space.

Value

The value is controlled reuse. DP turns repeated search into a table of unique questions, which is why it often converts exponential recursion into polynomial time.

Direct complexity example

Brute force: Explore all decision paths in a recursion tree: often $O(2^n)$ or worse, with repeated subproblems.
With this tactic: Cache each unique state once: $O(\text{states} \times \text{transition cost})$ time.
Space: Space is $O(\text{states})$ for the cache or table, sometimes reducible with state compression.

Challenges this solves

counting ways
minimum cost
maximum score
sequence alignment
choice with constraints
grid paths

When to use it

Use this tactic when these conditions are true:

the brute force asks the same suffix or subproblem many times
the answer for a larger problem can be built from smaller answers
the prompt asks for min, max, count, or feasibility
a greedy rule is tempting but not provable

When not to use it

Reach for a different tactic when these warning signs appear:

there is no overlapping subproblem structure
a simple scan or greedy invariant keeps all needed information
the state space is too large and needs a different model
the recurrence depends on future choices in a cyclic way

Terminology clues

These prompt words often point toward this concept:

number of ways
min cost
max profit
can form
choose or skip
optimal substructure
overlapping subproblems
recurrence