LiveCodingInterview.com
← Articles

Dynamic Programming Patterns: How to Recognize Them

Dynamic programming patterns are the small set of reusable strategies, the knapsack family, the sequence family, interval DP, grid DP, and state machine DP among them, that let you recognize and solve a new problem instead of memorizing solutions to problems you have already seen. Every DP problem shares two properties: optimal substructure, meaning the answer to the full problem is built from answers to smaller versions of itself, and overlapping subproblems, meaning those smaller versions repeat often enough that caching them saves real work. Spot both properties in the problem statement, match it to the right pattern family, and the rest of the work is choosing between two implementations, memoization from the top or tabulation from the bottom.

What Makes a Problem a Dynamic Programming Problem?

A problem qualifies for dynamic programming when it has optimal substructure and overlapping subproblems at the same time, and neither property alone is enough to justify the technique. Optimal substructure means you can express the answer for input of size n using the answers for smaller inputs, the way the best score reachable at house five depends only on the best scores reachable at houses three and four. Plenty of problems have this property without needing DP. A shortest path in a graph with no negative edges has optimal substructure, and Dijkstra's algorithm solves it directly with a greedy choice at every step, no table required.

What makes DP specifically necessary is the second property. Overlapping subproblems means that as you recurse toward the base case, you land on the exact same smaller input more than once. Write a naive recursive solution for a Fibonacci-shaped problem and trace the call tree by hand. You will see fib(3) computed inside the call for fib(5) and again inside the call for fib(4), wastefully recomputed both times, and that repetition is the tell. Divide-and-conquer algorithms like merge sort also break a problem into smaller versions of itself, but those subproblems never overlap, each half of the array is sorted completely independently, so caching wouldn't help at all and merge sort stays a divide-and-conquer algorithm rather than a DP one.

So before reaching for a table, ask whether the answer to the current input can be written as a function of answers to strictly smaller inputs, and whether that function gets asked for the same smaller input more than once as the recursion unfolds. Two yeses means dynamic programming is the right tool. One yes and one no usually means greedy or divide-and-conquer will do the job with less code.

How Do You Recognize a DP Problem From the Statement Alone?

Before you write a single line of code, the phrasing of the problem already tells you whether dynamic programming is what you need. Interviewers tend to reuse a small set of phrasings across DP problems, and learning to hear them turns a cold problem into a familiar shape within the first thirty seconds of reading it.

A few signals show up again and again:

  • "How many ways" or "count the number of" almost always points to a counting variant, where the recurrence sums the ways to reach each smaller state.
  • "Minimum cost", "maximum score", or "longest" points to an optimization variant, where the recurrence takes a min or max across the choices available at each state.
  • "Can you reach" or "is it possible to" combined with a rule about what moves are allowed points to a reachability variant, where each state is either true or false based on the states before it.
  • A constraint that ties each choice to earlier choices, such as no two adjacent items, a fixed number of transactions, or a cooldown period after an action, is one of the strongest DP tells around, because it means the best choice at each step depends on what you already picked.

This is the same recognition-first approach our guide to spotting LeetCode patterns before you code argues for across every pattern, not only DP. The signal lives in the words of the problem, and dynamic programming's signal is a small repeated decision that keeps building on the decisions made before it.

What Are the Core Dynamic Programming Patterns?

Ten to fifteen named DP patterns cover almost everything you'll see in an interview, and they group into a handful of families that share a shape, which matters more than any individual name. The knapsack family covers 0/1 knapsack, subset sum, and coin change, where you choose from a set of items under some capacity limit, either taking each item once or as many times as you want. Our Cheapest Menu Combinations question is a knapsack-family problem end to end, and working through it after reading this is a fast way to make the pattern concrete rather than theoretical.

The sequence family covers longest common subsequence, longest increasing subsequence, and edit distance, where the state compares a position in one sequence against a position in another, or against an earlier position in the same sequence. Interval DP, used for problems like matrix chain multiplication and palindrome partitioning, defines its state over a full subrange marked by two indices instead of a single position, and it usually processes ranges from short to long so every smaller range is already solved by the time a longer one needs it. Grid DP, the family behind unique paths and minimum path sum problems, ties each cell's answer to the cells directly above and to the left, which is why so many grid problems can fill their table row by row. State machine DP, the family behind house robber and stock trading problems with cooldowns or transaction limits, assigns each index a small number of named states, such as holding a share or not holding one, and defines a transition between those states at every step.

Knowing which family a new problem belongs to gets you most of the way to the recurrence before you have written anything down, because the shape of the state and the shape of the transition are already decided by the family, not by the specific numbers in front of you.

How Do You Solve a Dynamic Programming Problem, Step by Step?

Solve a DP problem by moving through four stages in order: brute force recursion for correctness, top-down memoization for speed, bottom-up tabulation to drop the recursion, and a space pass to see what the table actually needs to remember. Walking through House Robber, a state machine problem where you can't rob two adjacent houses and want to maximize the total value taken, shows all four stages on real code.

Start with the brute force recursion, which exists purely to get the logic right before you optimize anything:

def rob_brute(houses, i):
    if i >= len(houses):
        return 0
    skip = rob_brute(houses, i + 1)
    take = houses[i] + rob_brute(houses, i + 2)
    return max(skip, take)

At each house you either skip it and move to the next, or take it and jump two ahead, and you keep whichever choice scores higher. This runs in O(2^n) time because every call branches into two more calls, and the same index gets recomputed many times as the branches overlap, which is exactly the overlapping subproblems signal from earlier.

Add a cache and the same logic becomes top-down memoization:

def rob_memo(houses):
    memo = {}
    def helper(i):
        if i >= len(houses):
            return 0
        if i in memo:
            return memo[i]
        skip = helper(i + 1)
        take = houses[i] + helper(i + 2)
        memo[i] = max(skip, take)
        return memo[i]
    return helper(0)

The recursive structure didn't change at all, but every index now gets computed once and reused after that, which drops the running time to O(n) at the cost of O(n) space for the cache and the call stack.

Converting to bottom-up tabulation removes the recursion entirely by building the same table from the base case upward instead of from the top down:

def rob_tabulation(houses):
    n = len(houses)
    dp = [0] * (n + 2)
    for i in range(n - 1, -1, -1):
        dp[i] = max(dp[i + 1], houses[i] + dp[i + 2])
    return dp[0]

Reading this against the memoized version, the recurrence itself didn't change, only the direction it gets filled in and the fact that a plain array replaced the function calls. This version still runs in O(n) time and O(n) space, but it avoids Python's recursion limit entirely, which matters once the input gets large.

The last stage asks what the table actually needs to remember. Look at the recurrence and notice dp[i] only ever depends on dp[i + 1] and dp[i + 2], never anything further back, so keeping the full array is more memory than the problem requires:

def rob_optimized(houses):
    next1, next2 = 0, 0
    for i in range(len(houses) - 1, -1, -1):
        current = max(next1, houses[i] + next2)
        next2 = next1
        next1 = current
    return next1

Two variables replace the whole array, and the space drops from O(n) to O(1) while the time complexity stays exactly the same. This last step is the one most guides skip entirely, and it's usually the exact follow-up question an interviewer asks once your tabulated solution already works.

Memoization or Tabulation: Which Should You Use in an Interview?

Start with memoization and convert to tabulation only if asked, because memoization builds directly on the recursive relation you already derived while recognizing the problem, while tabulation asks you to reason about fill order before you have written any code. Top-down memoization also has a real practical advantage: it naturally skips states the input never actually reaches, since it only computes what the recursion calls for, while a tabulated solution usually fills every cell in the table whether the final answer needs it or not.

Tabulation earns its place once you need to remove recursion for stack-depth reasons, or once the interviewer asks you to reduce the space, since the array in a bottom-up solution can be replaced with a handful of rolling variables in a way that's far more natural to reason about than trying to prune a call stack. Converting from one to the other is mostly mechanical once the recurrence is correct: reverse the order you fill states in so every dependency is already computed, and replace each recursive call with a lookup into the array. Practicing that conversion on two or three problems is worth more than memorizing either approach on its own, since interviewers routinely ask for both in the same round.

How Do You Cut the Space a DP Solution Uses?

Most DP solutions only ever look back a fixed number of steps, one, two, or a small fixed window, which means a full table is usually far more memory than the problem actually needs. The House Robber example above only ever reads dp[i + 1] and dp[i + 2], so two rolling variables carry exactly as much information as the entire array did. The same idea applies to two-dimensional grid problems whose current row only depends on the row directly above it. Instead of keeping the full grid in memory, you can keep just the previous row and overwrite it in place as you move down, which turns an O(rows times columns) space solution into an O(columns) one.

Interviewers ask for this specifically because it separates candidates who copied a recurrence from candidates who understand what the table is actually storing. Before you claim a space optimization is possible, trace which earlier states the current state's formula actually touches. If it only ever touches the last one or two computed values, you can drop the array. If it touches an arbitrary earlier state, the full table has to stay.

How Do You Talk Through a DP Solution Out Loud in an Interview?

Say the state and the recurrence out loud before you write any code, since an interviewer grading a DP problem is listening for whether you understand what each entry in the table represents, not just whether the final code happens to run. A useful order to narrate in starts with naming the state in plain words, something like "dp of i represents the most value I can rob using houses zero through i", followed by the transition in the same plain language, then the base case, and only after all three are said out loud do you start writing.

Mention the brute force approach explicitly even if you plan to skip implementing it, since saying "I'll state the brute force recursive relation first so we agree it's correct, then optimize it" signals that you understand memoization is an optimization layered on top of a correct recursive idea rather than a separate technique you memorized in isolation. When you convert to tabulation, narrate the fill order and why it guarantees every dependency is ready, and when you cut the space down, say out loud exactly which earlier states the current one depends on before you drop the array. That last sentence is usually the one that convinces an interviewer you didn't just memorize a template.

Where to Practice These Patterns Next

Reading the families and tracing one worked example gets you the shape of dynamic programming, but the recognition speed that actually matters in an interview only comes from working real problems under a clock. Our Big O breakdown for interviews is worth pairing with this guide, since every DP answer you give should come with a clear statement of the time and space complexity you just built. From there, practice with real interview-reported questions rather than an unfiltered problem list, since matching what current loops actually ask beats grinding through problems that stopped showing up years ago.

Frequently Asked Questions

What are dynamic programming patterns?

Dynamic programming patterns are reusable problem shapes, such as the knapsack family, the sequence family, interval DP, grid DP, and state machine DP, that share a common state definition and transition. Recognizing which family a new problem belongs to gets you most of the way to a working recurrence before you write any code.

Is dynamic programming hard to learn for interviews?

It is harder to learn than most single algorithms because it asks you to define a state and a transition rather than apply a fixed procedure, but it becomes mechanical once you have solved enough problems in each pattern family to recognize the shape on sight. Most candidates find the recognition step, not the coding step, is what takes practice.

What is the difference between memoization and tabulation?

Memoization is a top-down technique that keeps the recursive structure of a brute force solution and caches each result the first time it gets computed, while tabulation is a bottom-up technique that fills a table iteratively from the base case upward with no recursion at all. Both reach the same time complexity, but tabulation avoids recursion-depth limits and usually makes a later space optimization easier to reason about.

What is optimal substructure in dynamic programming?

Optimal substructure means the best answer to a problem can be built directly from the best answers to smaller versions of the same problem, the way the most value you can rob from a street depends only on the most value you can rob from two shorter versions of that same street. It is one of two properties, alongside overlapping subproblems, that a problem needs before dynamic programming is the right tool.

Should I learn dynamic programming patterns or just practice more problems?

Learn the pattern families first, then practice inside each one, rather than solving problems in a random order with no organizing structure. A candidate who recognizes a new problem as knapsack-shaped or interval-shaped within the first minute is transferring real knowledge, while a candidate who has only memorized solutions to specific problems is starting from zero every time the wording changes.

How many dynamic programming patterns do I actually need to know for interviews?

Roughly ten to fifteen named patterns, grouped into five or six families, cover the large majority of DP questions asked in real interviews. Going deep on the knapsack, sequence, interval, grid, and state machine families, rather than memorizing a long list of thirty or more named variants, is the more efficient way to prepare.