Dynamic Programming for Interviews: From Zero to Confident

DP Is Just Recursion That Remembers

Dynamic programming has a reputation problem. The name is intimidating, the textbook explanations are dense, and candidates treat it as a category of "hard problems" rather than a systematic technique. Here's the truth: if you can write a recursive function, you can do DP. The entire technique is one idea applied repeatedly — solve a problem recursively, notice you're solving the same subproblems multiple times, and cache the results.

That's it. Everything else — tabulation, space optimization, state transitions — is mechanical once you internalize this core insight. The hard part of DP is never the DP itself. The hard part is defining the right subproblem. Once you have the recurrence, the rest is bookkeeping.

Richard Bellman coined the term "dynamic programming" in the 1950s. He deliberately chose a vague, impressive-sounding name to shield his research from a Secretary of Defense who was hostile to mathematical research. The name stuck, and it's been scaring engineers ever since. Don't let it. The technique is profoundly practical — it's the difference between a solution that runs in milliseconds and one that doesn't terminate before the heat death of the universe.

This article builds your DP instinct from the ground up. We start with the mental model, then work through five canonical patterns that cover the vast majority of interview DP problems. By the end, you should be able to look at a new problem and either identify the DP pattern it belongs to or determine that DP isn't the right approach at all.

The Three-Step Framework: Recursion, Memoization, Tabulation

Every DP problem follows the same progression. Don't skip steps — even in an interview, starting with the brute-force recursive solution is the right move. It shows the interviewer you understand the problem structure before optimizing.

Step 1: Write the Recursive Solution

Define a function that solves the problem for a given state. Identify the base cases (when the answer is trivially known) and the recursive cases (how a larger problem breaks into smaller ones). Don't worry about efficiency yet. The goal is correctness and clarity.

For Climbing Stairs (how many ways to reach step n if you can take 1 or 2 steps at a time):

climb(n) = climb(n-1) + climb(n-2), with base cases climb(0) = 1, climb(1) = 1.

This is a correct solution. It's also O(2^n) because every call branches into two more calls, and subproblems repeat exponentially. Drawing the recursion tree for climb(5) reveals that climb(3) is computed twice, climb(2) three times, and so on. This repetition is the signal that memoization will help.

Step 2: Add Memoization (Top-Down DP)

Store results in a hash map or array, keyed by the function's state parameters. Before computing a subproblem, check if it's already been solved. This is a one-line change to the recursive solution — add a cache lookup at the top and a cache write before returning.

For Climbing Stairs with memoization: create an array memo of size n+1. At the start of climb(n), check if memo[n] is set. If so, return it. Otherwise, compute climb(n-1) + climb(n-2), store the result in memo[n], and return. Time drops from O(2^n) to O(n). Space is O(n) for the cache plus O(n) for the recursion stack.

Step 3: Convert to Tabulation (Bottom-Up DP)

Instead of starting from the top and recursing down, start from the base cases and build up iteratively. Fill a table (array) from the smallest subproblems to the largest. This eliminates recursion overhead and often makes space optimization possible.

For Climbing Stairs: create dp[0..n]. Set dp[0] = 1, dp[1] = 1. For i from 2 to n: dp[i] = dp[i-1] + dp[i-2]. The answer is dp[n]. Same O(n) time, but no recursion stack. And since each value only depends on the previous two, you can optimize space to O(1) using two variables.

In an interview, start with the recursive solution and mention memoization as the optimization. If the interviewer asks for bottom-up, convert. If they ask about space optimization, reduce. Each step earns you points and shows structured thinking. Don't jump straight to the optimized tabulation — you'll skip the reasoning that interviewers actually want to see.

How to Know It's a DP Problem

Not every optimization problem is DP. Not every recursive problem needs memoization. Two properties must both be present:

1. Overlapping subproblems. The recursive solution solves the same subproblem multiple times. If every subproblem is unique (like in merge sort, where each half is different), memoization doesn't help and it's divide-and-conquer, not DP.

2. Optimal substructure. The optimal solution to the full problem can be built from optimal solutions to its subproblems. If making a locally optimal choice now can prevent you from reaching the globally optimal solution, you need DP (not greedy). Contrast with the coin change problem: a greedy approach (take the largest coin first) fails for arbitrary denominations because a locally good choice can lead to a worse total.

Here are the practical signals to look for in problem statements:

• "Find the minimum/maximum cost/profit/score" — optimization over choices at each step.
• "Count the number of ways" — combinatorial counting where paths overlap.
• "Is it possible to..." — reachability or feasibility problems with branching decisions.
• "Find the longest/shortest subsequence/substring with property X" — sequential decision-making.
• Constraints around n <= 10^3 or n <= 10^4 suggest O(n^2) DP is expected. If n <= 20, it might be bitmask DP at O(2^n * n).

If a problem has optimal substructure but no overlapping subproblems, it's likely divide-and-conquer. If it has optimal substructure and a greedy choice property (where the locally optimal choice is always globally optimal), greedy is simpler and preferred. DP sits between greedy and brute-force: more structured than enumeration, more powerful than greedy. For a broader view of where DP fits among all patterns, see our overview of coding interview patterns.

The Five Canonical DP Patterns

Most interview DP problems fall into five structural categories. Recognizing which category a problem belongs to immediately tells you what the state is, what the transition looks like, and how to set up your table. Here's the complete reference:

Let's work through each one with a detailed example.

Pattern 1: Linear DP

The state is a single index into a sequence. Each element depends on a constant number of previous elements. These are the simplest DP problems and often the first ones you encounter.

Worked example: House Robber. You're a robber planning to rob houses along a street. Each house has a certain amount of money. You can't rob two adjacent houses (the alarm will trigger). Find the maximum amount you can rob.

Thought process: At each house i, you have two choices — rob it (and add its value to the best you could do skipping the previous house) or skip it (and carry forward the best up to the previous house). This gives us the state: dp[i] = maximum money robbable from houses 0..i.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

Why it works: At each house, the optimal decision only depends on the previous two results. This is the hallmark of linear DP — a fixed lookback window.

Complexity: O(n) time. Since each state depends only on the two previous states, space optimizes to O(1) using two variables prev1 and prev2.

Variations to practice: House Robber II wraps the street into a circle, meaning the first and last houses are adjacent. The elegant fix: run House Robber twice — once excluding the first house, once excluding the last — and take the maximum. This decomposition trick (reducing a harder problem to two runs of a simpler one) appears in many linear DP variations and is worth having in your toolkit.

Maximum Subarray (Kadane's algorithm) is another linear DP classic, though it's often taught separately. The state is dp[i] = maximum subarray sum ending at index i. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]) — either extend the previous subarray or start fresh. The decision to "start fresh" is what makes this DP rather than a simple prefix sum.

Pattern 2: Grid DP

The state is a position in a 2D grid. Transitions typically come from the cell above and the cell to the left (or other neighboring cells, depending on allowed movement). Fill the table row by row, left to right.

Worked example: Minimum Path Sum. Given an m x n grid of non-negative integers, find the path from top-left to bottom-right that minimizes the sum of values along the path. You can only move right or down.

Thought process: To reach cell (i, j), you must come from either (i-1, j) (above) or (i, j-1) (left). The minimum cost to reach (i, j) is the grid value at (i, j) plus the cheaper of those two incoming paths.

Recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Base cases: First row can only come from the left: dp[0][j] = dp[0][j-1] + grid[0][j]. First column can only come from above: dp[i][0] = dp[i-1][0] + grid[i][0]. Corner: dp[0][0] = grid[0][0].

Complexity: O(m * n) time. Space can be reduced from O(m * n) to O(n) by processing one row at a time and overwriting. You can also modify the input grid in place if the interviewer allows it, achieving O(1) extra space.

Variations to practice: Unique Paths is the pure counting version of grid DP — how many distinct paths exist from top-left to bottom-right? The recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1] (sum instead of min). Unique Paths II adds obstacles, requiring a simple check: if a cell is blocked, dp[i][j] = 0. Dungeon Game flips the direction — you work backwards from the bottom-right corner because the constraint is about maintaining positive health at every step, not just at the destination. Recognizing when to fill the table in reverse is an important grid DP skill. For related traversal problems, see our guide on graph algorithms.

Pattern 3: String DP

The state involves positions in one or two strings. These problems require comparing characters and making decisions based on matches or mismatches. The table is typically 2D with dimensions matching the string lengths.

Worked example: Edit Distance (Levenshtein Distance). Given two strings word1 and word2, find the minimum number of operations (insert, delete, replace) to convert word1 into word2.

Thought process: Define dp[i][j] as the edit distance between word1[0..i-1] and word2[0..j-1]. If the characters at position i-1 and j-1 match, no operation is needed and dp[i][j] = dp[i-1][j-1]. If they differ, we pick the cheapest of three operations: replace (dp[i-1][j-1] + 1), delete from word1 (dp[i-1][j] + 1), or insert into word1 (dp[i][j-1] + 1).

Recurrence:

• If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
• Otherwise: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Base cases: dp[i][0] = i (delete all characters from word1), dp[0][j] = j (insert all characters of word2).

Complexity: O(m * n) time and space. Space reduces to O(n) with a single-row optimization, but you need to track the diagonal value from the previous row carefully — a common implementation pitfall. Edit distance appears frequently in interviews at Google, Meta, and Amazon, and variations (like one-edit distance check) show up as follow-ups.

Variations to practice: Longest Common Subsequence (LCS) is the other foundational string DP problem. The recurrence is simpler: if characters match, dp[i][j] = dp[i-1][j-1] + 1; if not, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). LCS itself rarely appears as a standalone interview question, but it's a building block for harder problems like Shortest Common Supersequence and various diff algorithms. If you understand both Edit Distance and LCS deeply, you can handle virtually any string DP problem by reasoning about what happens at each character pair — match, mismatch, insert, or delete.

Another high-frequency string DP problem is Longest Palindromic Subsequence, which is actually LCS of a string with its reverse. Seeing these connections between problems is what separates mechanical DP solvers from genuinely fluent ones.

Pattern 4: Knapsack DP

You have items with weights and values, and a constraint on total weight (or sum, or capacity). The decision at each step is whether to include or exclude each item. This pattern extends well beyond the classic knapsack — any problem where you're selecting a subset to meet a constraint likely fits here.

Worked example: Subset Sum. Given an array of positive integers and a target sum, determine if any subset adds up to exactly the target.

Thought process: Define dp[i][s] as whether it's possible to achieve sum s using the first i elements. For each element, we either include it (reducing the remaining target) or skip it.

Recurrence: dp[i][s] = dp[i-1][s] || dp[i-1][s - nums[i-1]] (skip the item, or take it if s >= nums[i-1])

Base cases: dp[i][0] = true for all i (empty subset sums to zero). dp[0][s] = false for s > 0 (can't make a positive sum with zero items).

Complexity: O(n * target) time. This is pseudo-polynomial — polynomial in the numeric value of the target but exponential in the number of bits needed to represent it. Space reduces to O(target) by iterating the sum dimension right to left in a 1D array (this prevents using the same item twice, which is the distinction between 0/1 knapsack and unbounded knapsack).

Key insight: The direction of iteration matters. For 0/1 knapsack, iterate sums from high to low so each item is only used once. For unbounded knapsack (like Coin Change), iterate low to high so items can be reused. Getting this wrong is one of the most common DP implementation bugs.

Pattern 5: Interval DP

The state represents a contiguous subarray defined by its endpoints. The key insight is that optimal solutions for intervals can be built by trying every possible split point within the interval. Interval DP problems are typically O(n^3) due to the three nested loops: interval length, start position, and split point.

Worked example: Burst Balloons. You have n balloons, each with a number. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins. After bursting, the neighbors become adjacent. Find the maximum coins.

Thought process: The trick is to think about which balloon is burst last in each interval, not first. Define dp[i][j] as the maximum coins from bursting all balloons between indices i and j (exclusive boundaries). If balloon k is the last one burst in the interval (i, j), then when it pops, the only remaining neighbors are i and j (everything else in the interval is already gone). So the coins earned for bursting k last are nums[i] * nums[k] * nums[j], plus the optimal solutions for the sub-intervals (i, k) and (k, j).

Recurrence: dp[i][j] = max over all k in (i+1..j-1) of (dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])

Base cases: dp[i][j] = 0 when j <= i + 1 (no balloons to burst in an empty or single-element interval).

Complexity: O(n^3) time, O(n^2) space. Interval DP is harder to optimize and rarely reduces below cubic time. The iteration order matters: process intervals by increasing length, so smaller sub-intervals are solved before larger ones that depend on them.

Why this problem is hard: The non-obvious step is reframing from "which balloon to burst first" to "which balloon to burst last." Bursting first creates a dependency nightmare because neighbors change. Bursting last means the boundaries are fixed. This reframing trick appears in several interval DP problems and is worth internalizing as a general strategy.

Variations to practice: Matrix Chain Multiplication is the textbook interval DP problem. Given dimensions of n matrices, find the order of multiplication that minimizes the total number of scalar multiplications. The recurrence tries every split point k in the interval (i, j): dp[i][j] = min over k of (dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]). The structure is identical to Burst Balloons — try all split points, combine optimal sub-intervals, add the cost of merging. Once you see this shared structure, interval DP becomes one pattern with different cost functions, not a collection of unrelated hard problems.

Palindrome Partitioning II (minimum cuts to partition a string into palindromes) is another interval DP problem that appears in interviews, though it can also be solved with a clever linear DP formulation. Having both approaches in mind lets you discuss trade-offs with the interviewer.

Common Mistakes and How to Avoid Them

After reviewing thousands of DP solutions (both correct and incorrect), these are the mistakes that appear most frequently in interviews:

1. Jumping to DP when greedy works. Not every optimization problem needs DP. If making the locally best choice at each step always leads to the globally best solution, greedy is simpler and faster. Activity selection (choose the event that ends earliest) is greedy. Fractional knapsack (take the highest value-per-weight first) is greedy. Before building a DP table, ask yourself: "Can I prove that a greedy strategy works here?" If it does, you've saved yourself significant implementation complexity. The interviewer will be impressed that you considered and ruled out simpler approaches.

2. Not identifying the state clearly. The single most important step in any DP problem is defining what dp[i] (or dp[i][j]) represents. Vague state definitions lead to incorrect recurrences. Before writing any transition logic, write a precise English sentence: "dp[i] represents the maximum profit using items 0 through i with capacity w remaining." If you can't write that sentence, you're not ready to code. In an interview, state this definition out loud — it grounds the conversation and gives the interviewer something concrete to evaluate.

3. Forgetting base cases. Off-by-one errors in base cases cause subtle bugs that are hard to debug under time pressure. The systematic approach: consider what happens when the input is empty, when it has one element, and when you're at the boundary of your state space. Fill in the edges of your DP table explicitly before writing the general transition. For grid DP, this means initializing the first row and first column. For string DP, this means initializing dp[0][j] and dp[i][0].

4. Wrong iteration order in space-optimized solutions. When you reduce a 2D DP table to 1D, the direction of iteration determines whether you're reading stale or fresh values. For 0/1 knapsack, iterate right to left. For unbounded problems, iterate left to right. Getting this backwards produces a solution that silently gives wrong answers — the code runs, but the output is incorrect. Always trace through a small example to verify your iteration direction.

5. Over-complicating the state. If your state has four dimensions and the recurrence involves six cases, step back. Most interview DP problems have 1D or 2D state. If you're building something more complex, you may be framing the subproblem wrong. Ask: "Is there a simpler way to define what I'm tracking?" Often, the right state isn't the most obvious one. House Robber doesn't need a state for "did I rob the previous house" — the recurrence handles that implicitly through the i-2 lookback.

Putting It All Together: A Problem-Solving Protocol

When you encounter a potential DP problem in an interview, follow this sequence:

1. Verify it's DP. Check for overlapping subproblems and optimal substructure. Consider whether greedy or divide-and-conquer might work instead. State your reasoning out loud.
2. Identify the pattern. Is it linear, grid, string, knapsack, or interval? The input structure usually makes this obvious — a single array suggests linear or knapsack, a grid suggests grid DP, two strings suggest string DP.
3. Define the state precisely. Write or say: "dp[i] represents..." Be specific about what the indices mean and what the value represents (count, minimum cost, boolean feasibility, etc.).
4. Write the recurrence. Express the transition in terms of smaller subproblems. This is where the pattern knowledge pays off — if you know it's knapsack, the transition is include-or-exclude. If it's interval, you're trying all split points.
5. Identify base cases. What are the trivially solvable states? Fill in the boundaries of your table.
6. Determine the answer location. Is the answer dp[n]? dp[n][m]? The maximum over all dp[i]? This depends on your state definition.
7. Code the solution. Start with memoized recursion if you're more comfortable with that approach. Convert to tabulation if the interviewer asks or if you want to optimize space.
8. Analyze complexity. Time is the number of states times the work per state. Space is the table size (before optimization).

This protocol is mechanical. That's the point. Under interview pressure, a systematic process beats ad-hoc brilliance. Even if you've never seen the exact problem before, the protocol guides you to a solution — and the interviewer sees a structured thinker, not someone flailing.

The biggest mistake candidates make with DP isn't getting the recurrence wrong. It's spending 30 minutes silently staring at the problem trying to see the optimal solution directly. Start with brute-force recursion. Draw the recursion tree for a small input. Circle the repeated nodes. The DP solution will be obvious once you see the repetition. This process takes 5 minutes and it works on problems you've never seen before.

How to Practice DP Effectively

DP has a steeper learning curve than most other patterns because the subproblem definition varies so much between problems. Here's a practice plan that actually builds intuition rather than just familiarity:

Week 1: One pattern per day. Solve 2 problems from each of the five patterns above. Start with the worked examples in this article, then do one variation. Focus on writing the recurrence before writing code. If you can state the recurrence correctly, the code is straightforward.

Week 2: Mixed practice without labels. Solve DP problems without knowing which pattern they belong to. This trains classification, which is the hard part in a real interview. Use LeetCode's "Dynamic Programming" tag but shuffle the problems rather than sorting by acceptance rate.

Week 3: Timed practice with communication. Set a 30-minute timer. Solve the problem while explaining your thought process out loud (or to a rubber duck). This simulates interview conditions and reveals gaps in your understanding — if you can't explain why the recurrence is correct, you don't fully understand it yet.

Don't try to memorize solutions. Memorized solutions crumble under follow-up questions like "What if the constraint changes?" or "Can you optimize space?" Understanding the why behind each recurrence makes you adaptable. A candidate who derives the solution live, even slowly, scores higher than one who recites a memorized answer and can't modify it.

When you're ready to practice this protocol under realistic conditions, Hoppers AI's coding mock interviews let you work through DP problems with real-time AI feedback on your approach, communication, and code quality — helpful for building the muscle memory of thinking out loud while solving. You can also explore related patterns like sliding window and two pointers, which complement DP for problems involving sequences and subarrays.