# How Dynamic Programming Problems Appear in Technical Interviews: 8 Patterns to Recognize

> Master dynamic programming interview questions by recognizing 8 common problem patterns in technical interviews. Learn to transform brute-force solutions into optimal algorithms.

- Repository: [John Washam/coding-interview-university](https://github.com/jwasham/coding-interview-university)
- Tags: tutorial
- Published: 2026-02-24

---

**Technical interviews test your ability to recognize problems that can be solved efficiently with Dynamic Programming and to apply common patterns—such as 1-D linear recurrence, 2-D table filling, and bitmask state compression—to transform exponential brute-force solutions into optimal polynomial-time algorithms.**

The *Coding Interview University* repository by John Washam serves as a comprehensive roadmap for software engineering interviews, explicitly dedicating a section to Dynamic Programming (DP) under its "More Knowledge" curriculum. While you may not encounter DP in every interview, recognizing the hallmarks of a DP-candidate problem is essential for advancing to onsite rounds at top technology companies.

## How DP Problems Manifest in Technical Interviews

Dynamic Programming problems typically appear in specific scenarios where brute-force recursion would result in exponential time complexity. According to the repository's overview in [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md), you should watch for these five interview contexts:

- **Optimization Problems** (e.g., "maximum profit", "minimum cost"): These exhibit **overlapping sub-problems** and **optimal substructure**, where the best solution for a sub-range can be reused to build larger solutions.

- **Counting and Combinatorial Problems** (e.g., "how many ways", "number of sequences"): Characterized by large recursion trees where results depend only on state variables like index or remaining capacity, making them ideal for memoization.

- **Subset-Selection Problems** (e.g., "choose items with constraints"): Feature binary decisions (take vs. skip) for each element, often with capacity or sum constraints that map to classic knapsack-style DP.

- **Sequence Alignment and Pathfinding** (e.g., "edit distance", "grid path with obstacles"): Require two-dimensional state representation `(i, j)` that can be filled iteratively in a table row-by-row or diagonal-by-diagonal.

- **Game Theory and Turn-Based Problems** (e.g., "optimal play", "winning strategy"): State depends on whose turn it is and the remaining board configuration, requiring DP to record win/lose outcomes for each state.

## 8 Core DP Patterns Developers Must Recognize

The repository outlines eight fundamental patterns that cover the majority of DP interview questions. Mastering these templates allows you to map novel problems to known solutions quickly.

### 1-D DP (Linear Recurrence)

**State Representation:** `dp[i]` stores the answer for the prefix or first `i` elements.

**Transition:** `dp[i] = f(dp[i-1], ...)` where the current state depends only on previous indices. Classic examples include Fibonacci and the House Robber problem. This pattern appears in the repository's foundational DP examples.

### 2-D DP (Grid or Table)

**State Representation:** `dp[i][j]` represents the answer for a sub-problem spanning dimensions `i` and `j`.

**Transition:** Combine neighboring cells such as `dp[i-1][j]` and `dp[i][j-1]` to build the current solution. This applies to Longest Common Subsequence and Edit Distance problems, where the state space naturally forms a matrix.

### 1-D DP with Rolling Array

When only the previous row or column is needed to compute the current state, maintain two 1-D arrays instead of a full 2-D table. This technique reduces space complexity from O(N²) to O(N) and is particularly effective for 0/1 Knapsack implementations.

### 2-D DP with Space Optimization

Collapse one dimension when the transition function only references `i-1` (the previous row). This optimization is commonly used in "minimum path sum" problems where you only need the previous row's results to calculate the current row.

### DP on Subsets (Bitmask DP)

**State Representation:** Use a bitmask to represent selected items, where the state space is ≤ 2ⁿ.

**Transition:** Add one element to the subset by manipulating bits. This pattern solves the Traveling Salesman Problem and subset sum questions efficiently. The repository references this pattern in conjunction with bit manipulation resources.

### DP with Memoized Recursion (Top-Down)

Implement a recursive function `solve(state)` with a hash map or array cache. This approach is advantageous when the state space is sparse or irregular, allowing you to compute only the states actually reached during recursion rather than filling an entire table.

### DP on Trees

**State Representation:** `dp[node][state]` stores the answer for the subtree rooted at that node.

**Transition:** Combine results from child nodes to compute the parent node's value. This pattern solves problems like Maximum Independent Set on trees, where decisions at each node affect its immediate children but not the entire tree.

### DP with Monotonic Queue or Convex Hull Optimization

Optimize recurrences of the form `dp[i] = min_{j<i}(dp[j] + cost(j,i))` to reduce time complexity from O(N²) to O(N log N) or O(N). This advanced pattern handles problems where the cost function satisfies specific mathematical properties (convexity or monotonicity).

## Concrete Code Templates for DP Patterns

The following Python implementations illustrate the three most frequently requested DP patterns in technical interviews. Use these as starting templates when recognizing similar problem structures.

### 1-D Linear DP: Fibonacci Sequence

```python
def fib(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

```

This template demonstrates the linear recurrence pattern where `dp[i]` depends solely on previously computed values.

### 2-D Table DP: Edit Distance (Levenshtein)

```python
def edit_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i          # deletions

    for j in range(n + 1):
        dp[0][j] = j          # insertions

        
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,      # deletion

                dp[i][j - 1] + 1,      # insertion

                dp[i - 1][j - 1] + cost # substitution

            )
    return dp[m][n]

```

This implementation fills a matrix where `dp[i][j]` represents the minimum operations to transform substring `a[0:i]` into `b[0:j]`.

### Bitmask DP: Subset Sum Verification

```python
def can_sum(nums, target):
    # dp[mask] = achievable sum using elements in mask

    dp = {0: 0}
    for mask in range(1, 1 << len(nums)):
        # isolate the rightmost set bit

        lsb = mask & -mask
        idx = (lsb - 1).bit_length()
        prev = mask ^ lsb
        dp[mask] = dp[prev] + nums[idx]
        if dp[mask] == target:
            return True
    return False

```

This pattern uses integer bitmasks to enumerate subsets efficiently, checking if any combination sums to the target value.

## Essential Resources in the Coding Interview University Repository

The repository provides specific files and sections to deepen your DP preparation:

- **[`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md)** (Dynamic Programming section): Contains the central roadmap entry for DP under "More Knowledge," including curated video resources from Skiena lectures, Simonson series, and MIT OpenCourseWare. This section appears around lines 1010-1022 of the main README.

- **[`programming-language-resources.md`](https://github.com/jwasham/coding-interview-university/blob/main/programming-language-resources.md)**: Offers language-specific DP implementations in Python, C, and C++, useful for translating conceptual solutions into your preferred interview language syntax.

- **`extras/cheat sheets/bits-cheat-sheet.pdf`**: Provides bit manipulation reference material frequently paired with DP problems, particularly for bitmask DP implementations handling subset representations.

- **Translations**: Localized versions of the README (e.g., [`translations/README-es.md`](https://github.com/jwasham/coding-interview-university/blob/main/translations/README-es.md), [`translations/README-zh.md`](https://github.com/jwasham/coding-interview-university/blob/main/translations/README-zh.md)) maintain the same DP bullet points and pattern descriptions for non-English speakers.

## Summary

- Dynamic Programming problems in technical interviews typically involve **optimization**, **counting**, **subset selection**, **sequence alignment**, or **game theory** scenarios.
- Recognize DP candidates by identifying **overlapping sub-problems** and **optimal substructure** that allow polynomial-time solutions where brute force would fail.
- Master eight core patterns: **1-D linear**, **2-D table**, **rolling array optimization**, **space-optimized 2-D**, **bitmask subsets**, **memoized recursion**, **tree DP**, and **monotonic queue optimization**.
- Reference the [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) Dynamic Programming section (lines 1010-1022) and [`programming-language-resources.md`](https://github.com/jwasham/coding-interview-university/blob/main/programming-language-resources.md) for curated study materials and implementation templates.
- Use the provided Python templates for Fibonacci (1-D), Edit Distance (2-D), and Subset Sum (bitmask) as starting points during interviews.

## Frequently Asked Questions

### How do I know if a problem requires Dynamic Programming?

Look for two key properties: **optimal substructure** (the optimal solution contains optimal solutions to sub-problems) and **overlapping sub-problems** (the same sub-problems are solved multiple times in a naive recursive approach). If the problem asks for an optimization (minimum/maximum) or counting result and exhibits these properties, DP is likely the expected solution.

### What is the difference between memoization and tabulation in DP?

**Memoization** (top-down) uses recursion with a cache to store already computed states, computing only the states reached during execution. **Tabulation** (bottom-up) iteratively fills a table from the base cases up to the target state, guaranteeing that all required sub-problems are solved before they are needed. Tabulation often offers better constant factors and avoids recursion stack limits, while memoization can be more intuitive for problems with irregular state spaces.

### When should I use 2-D DP versus 1-D DP with space optimization?

Use **2-D DP** when you need to reference multiple previous rows or columns (e.g., `dp[i-1][j]`, `dp[i][j-1]`, and `dp[i-1][j-1]`). Transition to **1-D DP with rolling arrays** when the recurrence only depends on the immediately preceding row or a fixed window of previous values. For example, Edit Distance requires 2-D, but 0/1 Knapsack can often be optimized to 1-D by iterating backwards through the capacity array.

### Are bit manipulation skills required for Dynamic Programming interviews?

While not required for all DP problems, **bitmask DP** is essential for subset-selection problems where you need to track which elements have been used (state compression). Familiarity with bitwise operations (AND, OR, XOR, bit shifts) allows you to implement efficient state transitions for problems like the Traveling Salesman Problem or assignment problems with small input constraints (typically N ≤ 20). The repository's `bits-cheat-sheet.pdf` provides the necessary reference for these operations.