5 Dynamic Programming Patterns You Must Know (with Code)

Dynamic programming feels hard because people try to memorize solutions instead of the recipe — and the recipe is always the same: define the state, write the recurrence, set the base case, then memoize. DP applies whenever a problem has optimal substructure (the answer is built from answers to subproblems) and overlapping subproblems (the same subproblem recurs). Spot those two properties, apply the recipe, and most "hard" DP questions become a variation on one of five patterns below.

The recipe (use it every time)

1. Define the state — what do the DP indices/parameters mean? (e.g., dp[i] = best answer using the first i items.)
2. Write the recurrence — how does dp[i] build from smaller states?
3. Set the base case(s) — the smallest subproblems you can answer directly.
4. Choose memoization (top-down) or tabulation (bottom-up) — same recurrence, different direction.

Top-down (recursion + a cache) is usually the fastest to write in an interview; convert to bottom-up if asked about space.

from functools import lru_cache

def rob(nums):                      # House Robber — Fibonacci-style DP
    @lru_cache(None)
    def best(i):
        if i >= len(nums):
            return 0
        return max(best(i + 1),                 # skip house i
                   nums[i] + best(i + 2))        # rob house i, skip i+1
    return best(0)

The five patterns

1. Fibonacci-style (1-D sequence)

The current state depends on a couple of previous states. State: dp[i] from dp[i-1], dp[i-2]. Examples: Climbing Stairs, House Robber, Min Cost Climbing Stairs.

2. 0/1 Knapsack (choose / don't choose)

Each item is taken at most once under a capacity constraint. State: dp[i][c] = best using first i items with capacity c; choose max(skip, take). Examples: Subset Sum, Partition Equal Subset Sum, Target Sum.

3. Unbounded Knapsack (reuse items)

Like 0/1, but an item can be used unlimited times — the "take" branch stays on the same item. Examples: Coin Change, Coin Change II, Rod Cutting.

4. Longest Common Subsequence (two sequences)

A 2-D grid over two strings/arrays. State: dp[i][j] compares prefixes; match → 1 + dp[i-1][j-1], else max(dp[i-1][j], dp[i][j-1]). Examples: LCS, Edit Distance, Distinct Subsequences.

5. Interval / subsequence on one string

DP over substrings/intervals, often expanding from the center or by interval length. State: dp[i][j] for the substring i..j. Examples: Longest Palindromic Subsequence, Palindrome Partitioning, Burst Balloons.

Recognition cues

• The problem asks for a count of ways, a min/max, or "is it possible" over choices.
• A greedy approach gives wrong answers on some inputs (you need to consider combinations).
• The brute-force recursion recomputes the same arguments — that's the overlapping-subproblems signal to add a cache.

Common mistakes

• Vague state definition — if you can't say in one sentence what dp[i] means, the recurrence will be wrong.
• Missing/incorrect base cases — handle empty input and the smallest indices explicitly.
• Wrong iteration order in tabulation — a state must be computed before it's used.
• Reaching for DP when greedy works (or vice-versa) — DP is for when local choices interact.

Practice problems

Climbing Stairs, House Robber, Coin Change, Partition Equal Subset Sum, Longest Common Subsequence, Edit Distance, Longest Increasing Subsequence, Word Break, Longest Palindromic Subsequence.

Drill one pattern at a time — build a schedule with our free study-plan generator, or get live feedback in our DSA course.

More interview patterns: Binary Search · Two Pointers · Sliding Window · Graph Algorithms

Written by Amit Singh — Senior SDE at Amazon, Claude Certified Architect, and founder of AlgoEngineer.