DP State Design: 7 Patterns That Cut Interview Time in Half

The State Definition Problem No One Tells You About

Most dynamic programming failures don’t happen because you can’t write the recurrence relation. They happen because you defined the wrong state.

I’ve seen candidates nail the “how do I compute this state from previous states” part but still fail the interview because their state definition created an exponential state space. Or worse, they defined a state that couldn’t capture the information needed to make optimal decisions going forward.

The state design step gets maybe 30 seconds in most DP tutorials, sandwiched between “recognize the problem is DP” and “write the recurrence.” But in real interviews, this is where you separate yourself from the pack.

Here are 7 state design patterns that actually come up in coding interviews, with the specific cues that tell you which one to use.

Pattern 1: Single-Sequence States When Order Doesn’t Matter Forward

The simplest DP states track a single position in a sequence. Use this when:
– Future decisions only depend on “where you are” not “how you got there”
– No need to remember multiple positions simultaneously
– The problem asks about prefixes or suffixes

def rob(houses):
    """House Robber: can't rob adjacent houses, maximize loot.
    State: dp[i] = max loot using houses[0..i]

    Why this works: whether we robbed house i-2 or i-3 doesn't matter,
    only the best result we could have achieved before house i.
    """
    if not houses:
        return 0
    if len(houses) <= 2:
        return max(houses)

    # dp[i] represents max loot considering houses 0 to i
    prev2 = houses[0]
    prev1 = max(houses[0], houses[1])

    for i in range(2, len(houses)):
        current = max(prev1, prev2 + houses[i])
        prev2 = prev1
        prev1 = current

    return prev1

# Test it
print(rob([2, 7, 9, 3, 1]))  # Output: 12 (rob houses at indices 0, 2, 4)

Time: $O(n)$, Space: $O(1)$ after optimization. The recurrence is $dp[i] = \max(dp[i-1], dp[i-2] + houses[i])$.

The key insight: we don’t need to know which specific houses we robbed, just the maximum value achievable. That’s the hallmark of when single-position states work.

Pattern 2: Two-Sequence States for Matching Problems

When you’re comparing, aligning, or matching two sequences, you almost always need a 2D state space.

Cues that signal this pattern:
– Two input strings/arrays
– Words like “common”, “edit”, “align”, “match”
– Problems asking about correspondence between elements

def longest_common_subsequence(text1, text2):
    """LCS: longest subsequence appearing in both strings.
    State: dp[i][j] = LCS length for text1[0..i-1] and text2[0..j-1]

    Why 2D: we need to track progress in BOTH strings independently.
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                # Characters match: extend the LCS from [i-1][j-1]
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # No match: take the best of skipping in either string
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(longest_common_subsequence("abcde", "ace"))  # Output: 3

The recurrence:

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}$$

Time: $O(mn)$, Space: $O(mn)$ (optimizable to $O(\min(m,n))$ with rolling array).

Interviewers love asking “can you optimize the space?” Here’s the move: since each row only depends on the previous row, keep two 1D arrays instead of the full 2D grid. I’ve seen candidates get from “good” to “great” just by mentioning this optimization.

Pattern 3: Endpoint States When the Boundary Matters

Sometimes “where you are” isn’t enough — you need to know “what just happened” to decide what comes next.

Use this when:
– Constraints depend on the last action (cooldowns, consecutive limits)
– The problem explicitly mentions “ending at position i”
– You need to enforce “must use this element” semantics

def max_subarray(nums):
    """Maximum sum subarray (Kadane's algorithm as DP).
    State: dp[i] = max sum of subarray ENDING at index i

    Critical: 'ending at i' means nums[i] MUST be included.
    This forces us to make a clean decision: extend or start fresh.
    """
    if not nums:
        return 0

    max_ending_here = nums[0]
    max_so_far = nums[0]

    for i in range(1, len(nums)):
        # Either extend the previous subarray or start new at nums[i]
        max_ending_here = max(nums[i], max_ending_here + nums[i])
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # Output: 6 (subarray [4,-1,2,1])

The recurrence: $dp[i] = \max(nums[i], dp[i-1] + nums[i])$.

Why “ending at i” is powerful: it eliminates ambiguity. Without this constraint, $dp[i]$ could mean “best subarray somewhere in $nums[0..i]$” which makes the recurrence messy. By forcing inclusion of $nums[i]$, we get a clean two-way choice.

Pattern 4: Multi-Dimensional States for Independent Constraints

When the problem has multiple independent constraints, each one often needs its own state dimension.

Cues:
– “with at most k transactions”
– “using exactly m items”
– “with capacity limit w”
– Multiple resource types that can’t be combined into one counter

def knapsack_01(weights, values, capacity):
    """0/1 Knapsack: maximize value with weight limit.
    State: dp[i][w] = max value using items[0..i-1] with capacity w

    Why 2D: item index and remaining capacity are independent constraints.
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: don't take item i-1
            dp[i][w] = dp[i-1][w]

            # Option 2: take item i-1 (if it fits)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_01(weights, values, 5))  # Output: 7 (take items 0 and 1: weights 2+3=5, values 3+4=7)

Recurrence: $dp[i][w] = \max(dp[i-1][w], \; dp[i-1][w – weights[i-1]] + values[i-1])$

Time: $O(n \cdot W)$ where $W$ is capacity. This is why knapsack is “pseudo-polynomial” — the complexity depends on the numeric value of the input, not just its size.

Gotcha: candidates often try to use a 1D state $dp[w]$ = “best value with capacity $w$” but this doesn’t work for 0/1 knapsack because you lose track of which items you’ve considered. For unbounded knapsack (where you can use items repeatedly), 1D works fine.

Pattern 5: State Machines for Explicit Mode Tracking

When the problem has explicit “modes” or “states” in the English sense (not the DP sense), model them directly.

Cues:
– “buy” and “sell” phases
– “on” and “off” states
– Multiple distinct modes with different transition rules

def max_profit_with_cooldown(prices):
    """Stock trading: after selling, must cooldown 1 day before buying again.
    States: 
      hold[i] = max profit on day i ending in 'holding stock' state
      sold[i] = max profit on day i ending in 'just sold' state
      rest[i] = max profit on day i ending in 'resting' state (no stock)

    Transitions:
      hold[i] = max(hold[i-1], rest[i-1] - prices[i])  # keep holding or buy
      sold[i] = hold[i-1] + prices[i]                  # sell
      rest[i] = max(rest[i-1], sold[i-1])              # rest after cooldown
    """
    if not prices:
        return 0

    n = len(prices)
    hold = [0] * n
    sold = [0] * n
    rest = [0] * n

    hold[0] = -prices[0]  # Buy on day 0
    sold[0] = float('-inf')  # Can't sell on day 0
    rest[0] = 0  # Or just don't do anything

    for i in range(1, n):
        hold[i] = max(hold[i-1], rest[i-1] - prices[i])
        sold[i] = hold[i-1] + prices[i]
        rest[i] = max(rest[i-1], sold[i-1])

    # On last day, we want to be either sold or resting (not holding)
    return max(sold[n-1], rest[n-1])

print(max_profit_with_cooldown([1, 2, 3, 0, 2]))  # Output: 3 (buy@1, sell@2, cooldown, buy@0, sell@2)

Transition equations:

$$\begin{align} hold[i] &= \max(hold[i-1], \; rest[i-1] – prices[i]) \\ sold[i] &= hold[i-1] + prices[i] \\ rest[i] &= \max(rest[i-1], \; sold[i-1]) \end{align}$$

Time: $O(n)$, Space: $O(n)$ (optimizable to $O(1)$ with variables).

The beauty of this pattern: the state machine makes the logic explicit. You’re not trying to cram everything into one $dp[i]$ value and hoping the recurrence works out. Each state has a clear meaning.

Pattern 6: Range DP for Interval Problems

When the problem asks about optimal ways to process a contiguous interval, use range DP.

Cues:
– “palindrome” (substring problems)
– “merge” or “burst” elements
– “minimize cost to combine”
– Decisions depend on both endpoints of an interval

def min_cost_merge_stones(stones):
    """Merge stones: minimize cost to merge all stones into one pile.
    Each merge combines exactly 2 consecutive piles (simplified k=2 version).

    State: dp[i][j] = min cost to merge stones[i..j] into one pile

    Note: Full problem allows k-way merges, requiring 3D DP.
    This demonstrates the range DP pattern with 2-way merges.
    """
    n = len(stones)
    if n < 2:
        return 0

    # Prefix sums for quick range sum queries
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]

    # dp[i][j] = min cost to merge stones[i..j] into one pile
    dp = [[float('inf')] * n for _ in range(n)]

    # Base case: single stone needs no merge
    for i in range(n):
        dp[i][i] = 0

    # Try all interval lengths
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Try all split points
            for mid in range(i, j):
                # Cost to merge [i..mid] and [mid+1..j] separately,
                # then merge those two piles
                dp[i][j] = min(dp[i][j],
                              dp[i][mid] + dp[mid+1][j] + prefix[j+1] - prefix[i])

    return dp[0][n-1] if dp[0][n-1] != float('inf') else 0

print(min_cost_merge_stones([3, 2, 4, 1]))  # Output: 20

Recurrence for range $[i, j]$:

$$dp[i][j] = \min_{i \le mid < j} \left( dp[i][mid] + dp[mid+1][j] + \sum_{k=i}^{j} stones[k] \right)$$

Time: $O(n^3)$ for the three nested loops. Space: $O(n^2)$.

The iteration order matters here. You must process smaller intervals before larger ones, which is why we loop by increasing length. A lot of candidates try to do this with top-down memoization and get the base cases wrong.

Pattern 7: Bitmask DP for Small Subsets

When the problem involves subsets and $n \le 20$, encode the subset as a bitmask.

Cues:
– “assign n items” where $n \le 20$
– “visit all nodes” (TSP-style)
– “partition into groups”
– Exponential state space but small $n$

def min_cost_assign_tasks(cost):
    """Assign n tasks to n people, minimize total cost.
    cost[i][j] = cost for person i to do task j

    State: dp[mask] = min cost to assign tasks in 'mask' to first popcount(mask) people
    Mask is a bitmask where bit j = 1 means task j is assigned.
    """
    n = len(cost)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0  # No tasks assigned, zero cost

    for mask in range(1 << n):
        if dp[mask] == float('inf'):
            continue

        # Count how many tasks are already assigned = which person we're assigning to
        person = bin(mask).count('1')

        if person == n:
            continue

        # Try assigning each unassigned task to this person
        for task in range(n):
            if not (mask & (1 << task)):  # Task not yet assigned
                new_mask = mask | (1 << task)
                dp[new_mask] = min(dp[new_mask], dp[mask] + cost[person][task])

    return dp[(1 << n) - 1]

cost_matrix = [
    [9, 2, 7, 8],
    [6, 4, 3, 7],
    [5, 8, 1, 8],
    [7, 6, 9, 4]
]
print(min_cost_assign_tasks(cost_matrix))  # Output: 13 (optimal assignment: 0→1, 1→2, 2→2, 3→3 gives cost 2+3+1+7=13)

Time: $O(2^n \cdot n^2)$ — iterate through $2^n$masks, for each try$n$people and$n$tasks. Space:$O(2^n)$.

The transition: $dp[mask | (1 << task)] = \min(dp[mask | (1 << task)], \; dp[mask] + cost[person][task])$

Why bitmask works: we need to track “which subset of tasks have been assigned” and there are $2^n$ possible subsets. Representing this as a bitmask lets us use integer indexing instead of hashing sets.

Gotcha: make sure you understand bit operations. mask & (1 << task) checks if bit task is set. mask | (1 << task) sets bit task. I’ve seen candidates fumble this in interviews because they haven’t practiced bitwise ops recently. If bit manipulation feels rusty, Clean Code by Robert Martin has a solid chapter on writing readable low-level code.

How to Pick the Right Pattern Under Pressure

In an interview, you have maybe 2 minutes to decide on a state definition. Here’s the decision tree I use:

1. One sequence, only care about prefix/suffix? → Single-position state (Pattern 1)
2. Two sequences, matching/aligning/comparing? → Two-position 2D state (Pattern 2)
3. Constraints on consecutive actions or “must use this”? → Endpoint state (Pattern 3)
4. Multiple independent resource limits? → Multi-dimensional state (Pattern 4)
5. Explicit phases/modes in the problem description? → State machine (Pattern 5)
6. Problem about intervals/ranges/subarrays? → Range DP (Pattern 6)
7. Subsets, $n \le 20$? → Bitmask DP (Pattern 7)

If none of these fit, you might be looking at a graph DP or a problem that isn’t DP at all.

The Interview Mistakes I See Repeatedly

Most DP failures in interviews come from three places:

1. Defining states that can’t answer the question. Example: in the stock cooldown problem, if you only track $dp[i]$ = “max profit by day $i$” without tracking whether you’re holding stock, you can’t enforce the cooldown rule. The recurrence becomes impossible to write.

2. Forgetting to handle base cases. Range DP especially trips people up. What does $dp[i][i]$ mean? What about $dp[i][i-1]$ (empty range)? If your recurrence tries to access $dp[i][j]$ where $j < i$, you need to define what that means.

3. Overthinking the state. I once watched a candidate add a third dimension to track “whether we used an even or odd number of operations” when that information was completely irrelevant to the answer. Simpler is better. Start with the minimal state that lets you make decisions, then add dimensions only if you can’t write a valid recurrence.

FAQ

Q: How do I know if a problem is DP vs greedy vs backtracking?

Greedy: If locally optimal choices always lead to global optimum (e.g., activity selection, Dijkstra). DP: If locally optimal choices DON’T guarantee global optimum — you need to try multiple options and compare. Backtracking: If you need to generate all valid solutions, not just find the optimal one. DP problems typically ask for “maximum”, “minimum”, “count all ways”, or “is it possible.”

Q: Should I always write memoized recursion or bottom-up tabulation?

In interviews, start with whichever you can code faster without bugs. Memoized recursion is often easier to get right because the recurrence relation maps directly to code. But interviewers might ask you to optimize to bottom-up tabulation, which can save the recursion stack overhead. I’d say: prototype with memoization, optimize to tabulation if asked.

Q: What if I define the state but can’t write the recurrence?

Trace through a small example by hand. Pick $dp[3]$ or $dp[2][3]$ and ask: “What decisions could have led here? What previous states do I need?” If you can’t answer this for a specific index, your state definition might be missing information. This is also why writing out the first few values ($dp[0], dp[1], dp[2]$) manually is so useful — patterns emerge.

When to Walk Away from DP

Not every optimization problem is DP. If you find yourself adding a fifth dimension to your state space, or if the recurrence has seven terms and you’re not sure why, step back.

Sometimes the right answer is: “This looks like DP but the state space is exponential even with pruning. Maybe there’s a greedy insight I’m missing, or maybe this is actually an NP-hard problem and we need approximation.”

Being honest about the limits of DP is itself a signal of expertise. I’ve seen senior engineers get more respect by saying “I don’t think DP is the right model here” than junior engineers who force DP onto every problem that mentions “optimal.”

For the patterns above, my rule of thumb: if you can’t write a recurrence relation with at most 3-4 terms per case within 5 minutes of settling on a state definition, either the state is wrong or the problem isn’t DP. That constraint forces you to keep the state space manageable.