Skip to main content

Divide-and-Conquer and Dynamic Programming as General Strategies

What This Concept Is​

Divide-and-conquer (D&C) solves a problem by splitting it into smaller subproblems of the same shape, solving them independently, and combining the results. It works when subproblems are roughly independent and the combining step is cheap.

Dynamic programming (DP) is the cousin strategy for problems with overlapping subproblems and optimal substructure. Instead of recomputing the same subproblem many times, you store the answer (memoisation) or build up answers in a table (tabulation).

Both are heuristics for shape recognition, not algorithm categories. Seeing "this problem has a recursive structure with shared subproblems" is the move. The specific algorithm follows from the shape.

The dividing line between D&C and DP is one word: overlap.

  • No overlap, independent subproblems $\to$ D&C. Naive recursion is efficient.
  • Overlap, shared subproblems $\to$ DP. Naive recursion is exponential; memoise or tabulate.

A secondary distinction is about optimisation: DP typically targets optimal solutions (longest, shortest, max, min), leveraging optimal substructure. D&C is often for any solution of a correct shape (sort, search, discrete Fourier transform).

Common DP flavors you will meet later:

  • Top-down (memoised recursion): natural when the recursion is clear; $O(\text{states} \times \text{transition cost})$ time.
  • Bottom-up (tabulation): iterative, cache-friendlier; requires a dependency order on states.
  • Dimension reduction: if the current state depends only on the last $k$ rows, keep $O(k)$ space instead of $O(n)$.

Why It Matters Here​

These two strategies account for a large fraction of efficient algorithms in CS. Learning to recognise their fit in a problem is more valuable than memorising their templates.

In CS specifically:

  • D&C applications: sorting (mergesort, quicksort), searching (binary search), geometric algorithms (closest pair), FFT, matrix multiplication (Strassen), parallel algorithms (many), tree recursions.
  • DP applications: shortest paths (Bellman-Ford, Floyd-Warshall), edit distance, matrix chain multiplication, knapsack variants, sequence alignment (bioinformatics), scheduling, text layout.
  • Mixed: many graph optimisation problems combine D&C decomposition with DP at the leaves.

Many competition problems reward contestants who spot one of these shapes immediately. Many production systems bottleneck on naive recursion that a DP table would fix.

Forward pipeline: Semester 2 (full chapters on each), Semester 3 (memoisation as a refactoring pattern), Semester 4 (recognising exponential recursion as a bug to fix via DP), Semester 6 (distributed D&C via MapReduce), Semester 10 (capstone performance optimisation).

Concrete Examples​

Example 1 -- binary search (divide-and-conquer)​

Given a sorted array $a[0..n)$ and a target $t$, decide whether $t \in a$.

The problem splits: "is $t$ in the left half?" or "is $t$ in the right half?" Each subproblem has the same shape and half the size. The combining step is trivial (one comparison).

Recurrence: $T(n) = T(n/2) + O(1)$. Master theorem gives $T(n) = O(\log n)$.

def bsearch(a, t):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            return mid
        if a[mid] < t:
            lo = mid + 1
        else:
            hi = mid
    return -1

Key D&C marker: the two subproblems never overlap. The left half and right half have no shared elements. No DP needed.

Example 2 -- longest common subsequence (dynamic programming)​

Given two strings $x, y$ of lengths $m, n$, find the length of the longest common subsequence (LCS).

State. $\text{lcs}(i, j) = $ LCS length of $x[0..i)$ and $y[0..j)$.

Recurrence.

$$\text{lcs}(i, j) = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \ \text{lcs}(i-1, j-1) + 1 & \text{if } x[i-1] = y[j-1] \ \max(\text{lcs}(i-1, j), \text{lcs}(i, j-1)) & \text{otherwise} \end{cases}$$

Naive recursion is $O(2^{m+n})$ because the same $(i, j)$ states recur across the recursion tree.

DP observation: there are only $(m+1)(n+1)$ distinct states. Tabulate:

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

Time $O(mn)$. Space $O(mn)$, reducible to $O(\min(m, n))$ by keeping only the previous row. The key insight was optimal substructure -- an LCS is built from an LCS of shorter prefixes -- plus overlap -- the same prefix pair recurs in many naive-recursion branches.

Common Confusion / Misconceptions​

D&C needs independence. Divide-and-conquer requires subproblems that do not overlap; if they do, naive recursion is wasteful and DP is better. Applying D&C to an overlapping problem produces exponential blow-up (e.g. naive Fibonacci recursion).

DP without optimal substructure. Applying DP when an optimal solution cannot be assembled from optimal subproblem solutions produces correct-looking tables and wrong final answers. Example: longest simple path in a general graph -- optimal substructure fails, DP does not directly apply.

"Try DP and see if it works." They are structural hypotheses, not random guesses. Before choosing, state: "the problem breaks into subproblems because ..." and "the subproblems overlap because ...". Without both statements, you are guessing.

Forgetting to estimate the state space. A DP is efficient only if the number of states is polynomial. Knapsack with real-valued weights has a continuous state space; standard DP does not apply.

How To Use It​

Strategy-selection protocol:

  1. Identify recursive structure. Does solving the problem reduce to solving one or more smaller instances of the same problem? Write the recurrence.
  2. Check subproblem overlap. Do the same subproblems appear in multiple branches of the recursion? Count distinct subproblems.
  3. Check optimal substructure. Can an optimal solution be composed from optimal subproblem solutions?
  4. If overlap + optimal substructure: DP. Choose memoisation or tabulation.
  5. If no overlap: D&C. Apply master theorem to estimate cost.
  6. Estimate the state space. Number of states $\times$ transition cost. If not polynomial, reconsider.
  7. Write the recurrence and base cases explicitly before coding. The code writes itself from a correct recurrence.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithm design). Entire chapters on each, including master theorem, DP on trees, DP on intervals, DP on bitmasks.
  • Semester 2 (optimisation). Bellman-Ford, Floyd-Warshall, and shortest-path trees are DP; Strassen and FFT are D&C.
  • Semester 3 (refactoring). Naive recursion $\to$ memoisation is a standard refactor ("introduce cache"). Tabulation is a second refactor ("invert control").
  • Semester 4 (debugging performance). Spotting exponential recursion in a call graph and recognising its DP shape is a frequent perf-fix.
  • Semester 6 (MapReduce / distributed D&C). Map = divide; reduce = combine. The mental model scales directly.
  • Semester 7 (architecture). System decomposition is structural D&C. "Which subsystems share state?" is the overlap question at macro scale.
  • Semester 10 (capstone). Any optimisation problem you meet will either be D&C-shaped or DP-shaped.

Check Yourself​

  1. What is the difference between divide-and-conquer and dynamic programming? State it in terms of subproblem overlap.
  2. Why do non-overlapping subproblems make DP unnecessary? What is the computational consequence of using DP anyway?
  3. Give an example of a problem where DP is correct but divide-and-conquer is not.
  4. What is "optimal substructure"? Give a problem that has it and one that does not.
  5. Why is estimating the state space a required step before committing to a DP? What kind of problem fails this check?

Mini Drill or Application​

Drill A. Classify each problem by strategy and justify in one sentence:

  1. computing $n!$
  2. computing the $n$-th Fibonacci number
  3. mergesorting an array of $n$ numbers
  4. finding the longest common subsequence of two strings
  5. finding the maximum element in an unsorted array
  6. computing the minimum number of coins to make change for $k$ given denominations

Drill B. Problem: Matrix-chain multiplication. Given matrices $A_1, A_2, \dots, A_n$ with dimensions $p_0 \times p_1, p_1 \times p_2, \dots, p_{n-1} \times p_n$, parenthesise to minimise total scalar multiplications. Write the DP recurrence $m(i, j)$ for the minimum cost of multiplying $A_i \cdots A_j$. State the state-space size and the per-state transition cost. Conclude the overall complexity.

Drill C (unseen). Problem: Given a boolean array, find the longest run of consecutive $\texttt{true}$s. Decide whether D&C, DP, or neither is the right shape. Write the algorithm at $O(n)$ time. If you chose DP, state the one-dimensional recurrence.

Read This Only If Stuck​