Suggest an edit

Improve this article

Refine the answer for “What does "overlapping subproblems" mean in dynamic programming?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

**Overlapping subproblems** is a property of a problem in which different branches of computation repeatedly solve the same subproblems. Dynamic programming eliminates these repeats through caching (memoization) or tabular computation (iterative tabulation), computing each unique subproblem exactly once and substantially reducing the asymptotic complexity.

## Detailed answer

### Definition and intuition

Overlapping subproblems is a situation where the set of unique subproblems is significantly smaller than the total number of their calls in a naive recursive expansion. In other words, the same states get computed again and again. DP stores the answers for already-solved states (for example, keyed by state) and reuses them.

- There are subproblems that repeat across different branches of computation.
- The number of unique states is bounded (usually by the subproblem's parameters: indices, remainder, sum, and so on).
- Overlapping subproblems is usually paired with optimal substructure: the optimal answer to the problem is built from the optimal answers to its subproblems.

### Classic example: Fibonacci numbers

Naive recursion recomputes the same F(k) many times - a clear case of overlapping subproblems.

```python
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# Calls to F(3), F(2), and others repeat many times -> exponential complexity O(phi^n).
```

DP eliminates the repeats: memoization (top-down) or tabulation (bottom-up).

```python
# Memoization (top-down)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

# Complexity: O(n) time and O(n) memory (cache/stack).
```

```python
# Tabulation (bottom-up)
def fib_tab(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

# Complexity: O(n) time, O(1) memory.
```

### More examples of problems with overlapping subproblems

- Counting paths in a grid: state (i, j) appears when counting paths from (i-1, j) and (i, j-1). DP: dp[i][j] = dp[i-1][j] + dp[i][j-1].
- LCS (longest common subsequence): state (i, j) for string prefixes repeats across different branches of character comparison.
- Coin change/subset sum: states (remaining_sum, idx) appear from different paths of choosing/skipping a coin.

### How to recognize overlapping subproblems

- Build the recursive formula and mentally unroll a few levels of the call tree: do you see identical states? That's it.
- The subproblem has few parameters, and their ranges are bounded (for example, indices i, j, remainder r) -> the number of unique states is finite and small.
- Naive recursion gives exponential complexity, but you suspect that answers can be reused.

### Comparison with "divide and conquer"

- Divide and conquer (quicksort/mergesort): subproblems are independent and do not overlap - there is no point in caching.
- DP: subproblems repeat -> caching/a table is critically important.

### Common interview mistakes

- Confusing overlapping subproblems with optimal substructure: these are different properties, but both are usually needed.
- Writing recursion without a cache, losing the time benefit.
- Storing too large a cache even though part of the state space is unreachable: memory can be optimized.

### Practical mini example: counting paths in a grid

Problem: how many paths are there from (0,0) to (m,n), moving only right and down? The subproblems dp[i][j] overlap because dp[i][j] is used when computing dp[i+1][j] and dp[i][j+1].

```python
def grid_paths(m, n):
    dp = [[0]*(n+1) for _ in range(m+1)]
    dp[0][0] = 1
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 and j == 0:
                continue
            from_up = dp[i-1][j] if i > 0 else 0
            from_left = dp[i][j-1] if j > 0 else 0
            dp[i][j] = from_up + from_left
    return dp[m][n]

# Time O(m*n), memory O(m*n) (can be reduced to O(n) with a single array).
```

### Short recap for the interview answer

- Overlapping subproblems: the same subproblems arise many times.
- Solution: DP with memoization (top-down) or tabulation (bottom-up), to compute each unique subproblem once.
- Check: a bounded number of states plus observable repeats in the recursion tree.
- Bottom line: reduced asymptotic complexity (often from exponential to polynomial).

Markdown · drag & drop images · ⌘B / ⌘I shortcuts669 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.