You've spent this entire module building divide-and-conquer algorithms. But D&C isn't the only recursive strategy out there. There's another family of recursive algorithms that looks similar on the surface — same recursion, same subproblems, same “build up from smaller cases” feel.

Dynamic programming.

Both D&C and DP break problems into subproblems and combine their solutions. Both recurse. Both have base cases. If you squint at the code, they can look almost identical.

But they're fundamentally different strategies, and confusing them will lead you to use the wrong tool for the problem. The question is: how do you tell them apart?

Let's start with gut instinct. Here are three algorithms. Two categories. Sort them by feel before we analyze why they belong where they do.

Three algorithms. Two categories. Before you analyze anything formally, just go with your gut — which ones feel like they belong together? Merge sort, Fibonacci, and matrix chain multiplication. Two of them are divide-and-conquer. One is dynamic programming. (Or is it the other way around?) Sort them by instinct, then we'll figure out why your gut was right or wrong.

Your gut probably had opinions — and they were probably right. But let's make the difference precise.

Both D&C and DP recurse on subproblems. The critical question is: do the subproblems overlap?

In merge sort, when you split [3,1,4,2] into [3,1] and [4,2], those halves are completely independent. Solving [3,1] tells you nothing about [4,2]. The recursion tree is a tree — each subproblem appears exactly once.

In Fibonacci, to compute fib(5), you need fib(4) and fib(3). But fib(4) itself needs fib(3) and fib(2). The same subproblem — fib(3) — appears multiple times. The “recursion tree” is actually a DAG with shared nodes.

Here's what that looks like. The left side is a tree — every node unique. The right side is a DAG — shared nodes highlighted.

D&C has independent subproblems. DP has overlapping subproblems. That's the dividing line.

Let's build both trees side by side and see the difference up close.

Now let's make the difference visual. You'll build two recursion trees side by side — one for a D&C algorithm and one for a DP algorithm. In the D&C tree, every node is unique — no subproblem appears twice. In the DP tree, you'll see the same subproblem show up under multiple parents. Build both trees node by node and watch where the overlap happens. The structural difference will be obvious once you see it.

The D&C tree fans out and never revisits a subproblem. Every node is unique. The total work is the sum across all nodes.

The DP DAG has shared subproblems. Without memoization, you'd recompute them exponentially. But the question is: how bad does it actually get? You've seen that fib(3) appears under both fib(5) and fib(4). That duplication cascades — fib(2) appears under every copy of fib(3) and under fib(4) itself. Before you see the numbers, make a prediction:

Drag the slider up to n = 20 and feel the scale of it. Over a million recursive calls for just 21 unique subproblems. All that extra work is pure redundancy — recomputing answers that already exist somewhere in the call stack, over and over.

The obvious fix is to remember each answer the first time you compute it. But how much does that actually help? Make a prediction before you see the effect:

With memoization, you only solve each unique subproblem once — the rest are instant cache lookups. The exponential tree collapses into a linear chain of unique computations. The structure is fundamentally different from D&C because the subproblems aren't independent, but memoization tames the explosion by ensuring the shared work is done exactly once.

You can even see the overlap at the formula level. Tap on either branch of the Fibonacci recurrence.

D&C gets its speed from geometric shrinkage — the problem halves at each level, and the total work converges. DP gets its speed from memoization of shared work — without it, the same subproblem is solved exponentially many times. Same recursion syntax, completely different performance stories.

Now let's test your understanding. Two new problems — can you classify them correctly?

Two new problems you haven't seen before. For each one, decide: is this divide-and-conquer or dynamic programming? Don't just guess — think about the subproblems. If you split the problem in half, do the halves depend on each other? Could the same subproblem appear under two different parent calls? The answer to that question is the entire classification. Get it right here and you'll never confuse the two strategies again in an interview.

The classification isn't always obvious from the problem statement. Sometimes you need to look at the code — specifically, the recursive calls.

D&C code typically has: solve(arr, lo, mid) and solve(arr, mid+1, hi) — the subproblems are non-overlapping ranges. The array is physically partitioned.

DP code typically has: solve(i-1) and solve(i-2), or solve(i, j-1) and solve(i-1, j) — the subproblems are prefixes or suffixes that overlap. Multiple parent problems can depend on the same child.

When you're not sure, ask the three diagnostic questions.

Let's look at some real code and classify it.

The classification isn't always obvious from the problem statement — but the code never lies. D&C recursive calls split the input into non-overlapping ranges: solve(arr, lo, mid) and solve(arr, mid+1, hi). DP recursive calls reference overlapping prefixes or suffixes: solve(i-1) and solve(i-2), where different parents call the same child. Look at the recursive calls in each snippet below and classify them. The structure of the arguments tells you everything.

function quicksort(arr: number[]): number[] {

  if (arr.length <= 1) return arr

  const pivot = arr[0]

  const left = arr.filter(x => x < pivot)

  const right = arr.filter(x => x > pivot)

  return [...quicksort(left), pivot, ...quicksort(right)]

}

function coinChange(amount: number, coins: number[]): number {

  if (amount === 0) return 0

  if (amount < 0) return -1

  let best = Infinity

  for (const coin of coins) {

    const sub = coinChange(amount - coin, coins)

    if (sub !== -1) best = Math.min(best, sub + 1)

  }

  return best === Infinity ? -1 : best

}

You've now sorted algorithms, built their recursion trees, and classified new problems by reading tree structure. Across every example, the same question kept deciding the answer.

Think back: what was the single test that correctly classified every problem you saw? Merge sort, quicksort, Fibonacci, coin change — what separated the D&C algorithms from the DP ones?

It comes down to one question: can the same subproblem appear under two different parent calls? If you answered that correctly for every tree you built, you already know the rule. If the subproblems are disjoint partitions — no shared nodes, no repeated labels — it's divide-and-conquer. If the same subproblem shows up under multiple parents, that overlap is the signal for dynamic programming.

Here's a practical decision framework for the next time you're staring at a recursive problem and aren't sure which tool to reach for:

Look at the recursive calls. Does the function split the input into non-overlapping ranges (solve(lo, mid) and solve(mid+1, hi))? That's a disjoint partition — D&C territory. Does it call solve(i-1) and solve(i-2), or solve(i, j-1) and solve(i-1, j), where different parents share the same child? That's overlap — DP territory.

Check the subproblem count. D&C typically has O(n) unique subproblems (one per node in the tree), and the tree's shape determines the total work. DP often has O(n^2) or O(n*W) unique subproblems, and the memoization table's size determines the total work. If the number of unique subproblems is polynomial but the naive recursion is exponential, memoization is your rescue.

Ask about independence. In merge sort, the answer to the left half can't possibly affect the answer to the right half — the elements don't interact until the combine step. In Fibonacci, fib(3) is needed by both fib(5) and fib(4) — the subproblems are entangled. Independence means D&C. Entanglement means DP.

You've completed the full divide-and-conquer journey: from the basic three-step pattern (divide, conquer, combine), through merge sort and quickselect, into the Master Theorem for analyzing recursion trees, through geometric D&C and merge-sort piggybacking, and finally to the boundary where D&C ends and DP begins. The next time you see a problem that can be split, you'll know exactly which tool to reach for.