Patterns / Dynamic Programming

Dynamic Programming Pattern

Break a problem into overlapping subproblems, solve each once, and reuse the answers.

What it is

Dynamic programming applies when a problem has optimal substructure (its answer is built from answers to smaller versions) and overlapping subproblems (those smaller versions repeat). You define a state, a transition that expresses a state in terms of smaller states, and base cases. Then you either memoize a recursion (top-down) or fill a table (bottom-up). The hard part is naming the state precisely; the rest follows.

When to use it — the signals

• "Number of ways to …", "minimum / maximum cost", "can you reach …".
• A choice at each step where greedy fails because choices interact.
• Brute-force recursion that recomputes the same arguments repeatedly.

How it works

A representative implementation in Java:

// Climbing stairs: ways[i] = ways[i-1] + ways[i-2].
int prev2 = 1, prev1 = 1;            // ways to reach steps 0 and 1
for (int i = 2; i <= n; i++) {
    int cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
}
return prev1;

Complexity

Usually O(number of states × work per transition) — often O(n) or O(n·m). Space can frequently be reduced to O(1) or O(n).

Common pitfalls

• Choosing a state that does not capture everything the transition needs.
• Wrong base cases or iteration order, so a cell is read before it is written.
• Reaching for DP when a greedy or simpler approach is provably correct.

Practice problems

Classic problems where this pattern is the intended approach: Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence. Work through them on the Leet Study home page.