Course contentsShow
← Computer Science
Lesson 915 of 2,87222. Dynamic ProgrammingFree lesson

Overlapping Subproblems

Understand why DP applies when the same subproblems are solved multiple times in a recursive solution.

Overlapping Subproblems

What you'll learn: You'll discover what makes a problem suitable for Dynamic Programming by understanding overlapping subproblems.


The Core Idea

When you solve a problem recursively, you often break it into smaller subproblems. Overlapping subproblems means that your recursive solution ends up solving the exact same subproblems multiple times.

This is wasteful! If you're computing the same thing over and over, you're doing redundant work. Dynamic Programming exploits this by solving each subproblem once and storing its result for reuse.

A Classic Example

Think about calculating Fibonacci numbers recursively:

  • fib(5) calls fib(4) and fib(3)
  • fib(4) calls fib(3) and fib(2)
  • Notice: fib(3) gets computed twice!

As the numbers grow, this explosion gets worse. fib(3) might be computed dozens of times in a single call to fib(10). These are overlapping subproblems—the same calculation (fib(3)) appearing in multiple branches of your recursion tree.

Contrast with Divide and Conquer

In algorithms like Mergesort, you split an array and never revisit the same subarray twice. Each subproblem is unique. That's why Mergesort doesn't need Dynamic Programming—there's no overlap!

Dynamic Programming shines when:

  1. You have optimal substructure (covered in the previous lesson)
  2. You have overlapping subproblems (this lesson!)

Together, these properties tell you: "Store results as you go, because you'll need them again."


Key Takeaway: Overlapping subproblems occur when a recursive solution repeatedly solves identical smaller problems; recognizing this pattern is essential for applying Dynamic Programming to avoid redundant computation.