Dynamic Programming Patterns for Coding Interviews: The Complete Guide

Most dynamic programming questions in coding interviews are one of six patterns. The skill being tested is recognizing the pattern, not remembering hundreds of solutions.

Dynamic programming, or DP, solves a problem by combining the answers to smaller versions of the same problem. Each pattern is a different way to define the smaller version. Once you know the six, a new question becomes a matching task.

This guide gives each pattern's signal, recurrence, classic problem, and usual mistake, then a study order and how to explain a solution out loud.

What a dynamic programming pattern is

A DP problem has three parts. The state is one or two numbers that describe a smaller version of the question, called a subproblem. The recurrence is the rule that computes one subproblem's answer from smaller subproblems.

The base case is a subproblem so small that its answer is known without any rule.

DP applies when subproblems repeat. Memoization stores each answer in a cache, which is a store of answers already computed, so nothing is solved twice. Tabulation fills a table from the smallest subproblem upward.

Both methods are shown on one problem in recursion, memoization, and tabulation. A pattern is a recurrence that many problems share, and six of them cover most common dynamic programming questions in tech interviews.

Which pattern is this? The six patterns in one table

Pattern 1: Fibonacci-style

The signal. One sequence, and the answer at position i depends on the answers at one or two earlier positions. "How many ways to reach step n" is one example.

The recurrence in words. The answer at i is a combination of the answers at i minus 1 and i minus 2. In counting questions you add them, and in best-value questions you keep the larger one.

Classic problem: Climbing Stairs. You may climb one or two steps at a time. The ways to reach step n equal the ways to reach step n minus 1 plus the ways to reach step n minus 2.

Because the rule uses only the two previous answers, two variables replace the whole table. The block below updates both on each pass of the loop.

def climb_stairs(n):
    two_back, one_back = 1, 1   # ways to reach step 0 and step 1
    for _ in range(2, n + 1):
        two_back, one_back = one_back, two_back + one_back
    return one_back

It runs in linear time, meaning proportional to n, and constant space, meaning a fixed number of variables.

House Robber adds a choice at each house. Skip the house, or rob it and add its value to the best total from two houses back. Grid paths are the two-dimensional form: each cell's count is the sum of the cell above and the cell to the left.

The usual mistake. Confusing sum and maximum. Say which operation you are using before you write the loop.

Pattern 2: 0/1 Knapsack

The signal. A set of items with sizes, each used at most once. You must reach a target, fill a capacity, or split the set, and the words subset, partition, and target usually appear.

The recurrence in words. A sum is reachable if it was already reachable without this item, or if the sum minus this item's size was reachable. Each item is included or excluded, which is the reason for the name 0/1.

Classic problem: Partition Equal Subset Sum. Can an array be split into two groups with the same total? If the total is even, the question becomes whether some subset reaches half of it.

The block below keeps one true-or-false value per sum from 0 to the target.

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    reachable = [True] + [False] * target
    for x in nums:
        for s in range(target, x - 1, -1):   # backward, so x is used once
            reachable[s] = reachable[s] or reachable[s - x]
    return reachable[target]

The time cost is the number of items multiplied by the target, and the space is the target plus one.

The usual mistake. Running the inner loop forward. A forward pass lets one item count twice, because the smaller sum it reads may already include that item.

Going backward means every value you read still describes the state before this item.

Pattern 3: Unbounded Knapsack

The signal. The same setup as 0/1 Knapsack, but each item can be used any number of times. Coins that repeat, rope lengths cut again, tasks done again.

The recurrence in words. For each amount, try every item that fits. The answer is the best answer for the amount minus that item's size, plus one more use of the item.

Because an item can repeat, the inner loop runs forward, the opposite of 0/1.

Classic problem: Coin Change. Given coin values and an amount, find the fewest coins that make the amount. The table holds the fewest coins for every amount from 0 up, and amount 0 needs zero coins.

The usual mistake. Loop order in Coin Change II, which counts the ways to make the amount. Coins outside and amounts inside counts each combination once.

Amounts outside and coins inside counts the same coins in a different order as different ways. The first counts combinations and the second counts ordered sequences. Check the wording to see which count the question asks for.

Grokking Dynamic Programming teaches these patterns one variation at a time, with runnable solutions for each problem.

Pattern 4: Longest Common Subsequence

The signal. Two strings or arrays, and you must compare them, align them, or turn one into the other.

A subsequence keeps characters in their original order but not necessarily next to each other, so "ace" is a subsequence of "abcde". A substring must be contiguous, so "ace" is not a substring of "abcde".

The recurrence in words. The state is a pair of prefixes: the first i characters of one string and the first j of the other. If the last characters match, the answer is one plus the answer for both prefixes shortened by one.

If they differ, the answer is the better of dropping the last character from either side.

Classic problem: LCS. The table has one row per prefix of the first string and one column per prefix of the second. Row 0 and column 0 represent the empty prefix and hold zero.

Fill the rows in order, and the answer is the bottom-right cell. The cost is the product of the two lengths, for both time and space.

Edit Distance is the same table with one more choice. When the characters differ, you may insert, delete, or replace, and you take the cheapest of the three plus one.

The usual mistake. The off-by-one between the string and the table. Row i represents the first i characters, so it compares character i minus 1 of the zero-indexed string.

Pattern 5: Palindromic Subsequence

The signal. One string and the word palindrome. A palindrome reads the same forward and backward, so its two ends must match.

That makes the natural subproblem an interval from position i to position j, not a prefix.

The recurrence in words. If the characters at both ends match, the answer is two plus the answer for the interval inside them. If they differ, take the better of the two intervals that each drop one end.

Classic problem: Longest Palindromic Subsequence. The base case is a single character, which is a palindrome of length one. The table has one cell per interval.

Fill the table by increasing interval length, so each inner interval is ready before the outer one. The cost is quadratic in the string length, meaning proportional to the length squared, for both time and space.

The usual mistake. Confusing substring and subsequence. For a palindromic substring, a mismatch at the ends means the interval is not a palindrome at all, so the mismatch rule changes.

The interval table works for both, so check which word the question uses before writing the rule.

Pattern 6: Longest Increasing Subsequence

The signal. The longest or best subsequence that obeys an ordering rule: strictly increasing numbers, envelopes that nest, jobs that do not overlap. The state is the longest valid subsequence that ends at element i.

The recurrence in words. For element i, look at every earlier element j that is allowed to come before it. The subsequence ending at i is the longest subsequence ending at such a j, plus one.

If no earlier element fits, the subsequence is element i alone.

Classic problem: LIS. Two nested loops give a quadratic solution that is clear enough to explain in full. A faster version runs in n log n time by keeping the smallest last value for each subsequence length.

It places each new number with binary search, which finds a position in a sorted list by halving the range each step. Mention this version by name and write it only if asked.

Russian Doll Envelopes is LIS after a sort. Sort by width ascending and, for equal widths, by height descending, then run LIS on the heights. The descending order for equal widths stops two envelopes of the same width from nesting.

The usual mistake. Missing the sort that reduces the problem to one dimension. When each item has two values, ask which sort order turns the items into a single sequence.

A study order for the six patterns

Learn the patterns in this order: Fibonacci-style, 0/1 Knapsack, Unbounded Knapsack, Longest Common Subsequence, Palindromic Subsequence, then Longest Increasing Subsequence.

Fibonacci-style teaches state and recurrence with the simplest possible state. The two knapsacks add a choice per item, and the loop direction is the only difference between them.

LCS introduces the two-dimensional table indexed by prefixes, and Palindromic Subsequence reuses that table with intervals. LIS is last because its recurrence looks at every earlier element, not a fixed one or two.

Solve four to six problems per pattern, in rising difficulty, and write the signal in your own words after each one.

The wider set of coding patterns works the same way, and how much practice is enough gives a count for the whole interview.

How to explain a DP solution in the interview

Say four things, in this order, using House Robber as the example.

1. The choice at each step: "at each house, I either rob it or skip it."
2. The subproblem: "the best total for the first i houses."
3. The base case: "with zero houses, the best total is zero."
4. The table order: "I fill from house 1 to house n, so each answer is ready before the next one needs it."

Then state the cost. Name the table size and the work per cell. Then give the time and space in big O notation, which describes how cost grows with input size.

If a version with less memory exists, like the two variables in Climbing Stairs, say so and offer to write it.

Starting with recursion is fine, because the recursive function shows the choice and the subproblem in plain form. Then add a cache in two lines. Convert to a table if the interviewer asks or if recursion depth is a concern in your language.

Frequently asked questions

How do I know a question needs dynamic programming and not a greedy choice? Try to find an input where the greedy choice fails. If the locally best pick gives a globally wrong answer on some input, you need DP. If you cannot find one, say so and use the greedy approach.

Should I use memoization or tabulation in a coding interview? Both are accepted. Memoization is usually faster to write, because you add a cache to a recursive function. Tabulation gives you more control over memory use.

How many dynamic programming problems should I solve before an interview? About thirty, if they are sorted by pattern. Four to six problems for each of the six patterns is enough to recognize each one quickly.

What is the difference between 0/1 Knapsack and Unbounded Knapsack? In 0/1 Knapsack each item is used at most once. In Unbounded Knapsack an item can be used any number of times. In the one-dimensional table version, the only code difference is the direction of the inner loop.

Are six patterns enough for every dynamic programming question? Most interview questions match one of the six. A few combine two patterns or use other states, like a bitmask (an integer whose bits mark chosen items) or a position in a tree. Learn the six first, because the harder questions reuse the same steps.

To practice these patterns together with the other coding patterns, Grokking the Coding Interview teaches each pattern with worked problems and runnable solutions.

Related reading

• From Recursion to Memoization to Tabulation: Solve the Same Problem Three Ways
• What Is Recursion?
• LeetCode Coding Patterns
• Coding Interview Cheat Sheet
• What Are Common Dynamic Programming Questions in Tech Interviews?
• What Is the Difference Between Recursion, Memoization, and Dynamic Programming?