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.

Overlap is a useful clue, but state sufficiency, dependency order, and transition cost also matter.

  • Independent subproblems suggest D&C; total work still depends on the recurrence.
  • Repeated states suggest memoisation; repetition alone does not prove exponential cost. DP also handles counting and feasibility, without an optimisation objective.

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 w)$ values for rows of width $w$, provided reconstruction does not require discarded information.

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​

Check the actual recurrence. D&C and DP are useful design patterns, not a complete dichotomy. Repeated states can make memoisation valuable; the number and cost of states determine whether it helps. Naive Fibonacci recursion is exponential, but overlap alone does not imply that complexity.

Insufficient state. For longest simple paths, the endpoint alone forgets which vertices are already used. A state including the visited subset can support a correct DP, but has exponentially many subsets. The issue is state sufficiency and cost, not an absolute impossibility of dynamic programming.

"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​

Engineering extension: State sufficiency before memoisation​

For unlimited positive coin values, the remaining amount determines all future legal choices, so it is a sufficient state. With a limited stock, amount alone loses information: remaining inventory is also needed. For target 6 with one coin of value 3, the unlimited answer [3,3] is invalid. Caching an insufficient state makes the wrong answer faster. Zero-valued transitions also destroy the simple decreasing-amount termination argument.

Continue with the evidence contracts and the practice feedback after an independent attempt.