Dynamic Programming Interview Patterns: A Practical Guide

Dynamic programming has a reputation for being the hardest interview topic. It's less mysterious than it looks once you treat it as a handful of repeatable patterns. This guide extends 15 DSA patterns with a deeper DP treatment.

The 5-step method

1. Define the state: what does dp[i] (or dp[i][j]) mean? Say it in one sentence.
2. Write the recurrence: how does the state come from smaller states?
3. Base cases: the smallest subproblems.
4. Order of computation: which states must be filled first.
5. Optimize space: often you only need the previous row or two values.

Start with recursion plus a cache; convert to a table afterwards.

Pattern 1: 1D linear DP

State depends on a few previous positions.

# House Robber: max sum with no two adjacent
def rob(nums):
    prev, cur = 0, 0
    for x in nums:
        prev, cur = cur, max(cur, prev + x)
    return cur

Also: climbing stairs, decode ways, max subarray (Kadane), longest increasing subsequence.

Pattern 2: Grid DP

dp[r][c] from the cell above and left.

def unique_paths(m, n):
    dp = [[1]*n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
    return dp[-1][-1]

Also: minimum path sum, maximal square, dungeon game.

Pattern 3: Knapsack / subset

State: index plus remaining capacity or target.

def can_partition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [True] + [False]*target
    for x in nums:
        for t in range(target, x-1, -1):
            dp[t] = dp[t] or dp[t-x]
    return dp[target]

Also: 0/1 knapsack, coin change (min coins, ways), target sum, partition into subsets.

Pattern 4: Strings (two sequences)

State: dp[i][j] for prefixes of two strings.

def lcs(a, b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            dp[i][j] = dp[i-1][j-1]+1 if a[i-1]==b[j-1] else max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

Also: edit distance, longest palindromic subsequence, distinct subsequences, regex/wildcard matching.

Pattern 5: Interval DP

State: a range [i, j], split at k. Examples: burst balloons, matrix chain multiplication, palindrome partitioning. Hardest tier; learn after the others.

Practice order

Communicating DP in an interview

State the definition of dp, show the recurrence, trace a small example, give time and space complexity, and mention the space optimization. This framing helps even if you stumble on details. See how to crack a DSA coding round.

Worked example: coin change, from recursion to table

Problem: given coin denominations and a target amount, find the minimum number of coins.

State: best(a) = fewest coins to make amount a. Recurrence: best(a) = 1 + min(best(a - c)) over coins c that do not exceed a. Base case: best(0) = 0; unreachable amounts are infinity.

Recursion with memoization first: call best(amount), cache every result. Then convert to a bottom-up table where you fill amounts from 1 to the target. Time is amount x number of coins; space is amount.

Narrating exactly this progression is what interviewers want to hear.

How to spot the family

Space optimization

Most DP tables depend only on the previous row or the last two values. Keep just those. For 0/1 knapsack, iterate the capacity in reverse so each item is used once. Mention this at the end, because it shows you understand the structure.

Debugging DP

• Print the table for a tiny input and compare with a hand calculation
• Check base cases and indices, especially off-by-one in string DP
• Verify iteration order: dependencies must be computed before use
• Compare against brute force on small random inputs

Common mistakes

• Defining the state too vaguely
• Forgetting to initialize with the right sentinel (infinity versus zero)
• Mixing up "number of ways" (sum) and "minimum" (min) recurrences
• Using a greedy approach where choices interact

A weekly practice routine

Pair this with the broader 15 DSA patterns.

Related reading

• 15 DSA patterns that solve most coding interview questions
• Google interview process in India
• Python vs Java vs C++ for coding interviews