When Is a Problem Suited for Dynamic Programming?

Dynamic programming is a powerful algorithmic technique in classical computing, but it only works effectively when a problem exhibits two specific structural properties: optimal substructure and overlapping subproblems. Together, these properties determine whether breaking a problem into smaller pieces and storing their results will yield a correct and efficient solution.

Optimal Substructure

A problem has optimal substructure if an optimal solution to the overall problem can be constructed from optimal solutions to its subproblems. Formally, if \(S\) is an optimal solution to a problem of size \(n\), and \(S\) can be decomposed into decisions that lead to subproblems \(P_1, P_2, \dots, P_k\), then the portions of \(S\) corresponding to each \(P_i\) must themselves be optimal solutions to those subproblems.

For example, in the shortest path problem on a weighted graph, if the shortest path from vertex \(u\) to vertex \(v\) passes through an intermediate vertex \(w\), then the segment from \(u\) to \(w\) must be the shortest path from \(u\) to \(w\), and the segment from \(w\) to \(v\) must be the shortest path from \(w\) to \(v\).

Without optimal substructure, combining optimal solutions to subproblems does not guarantee an optimal global solution. In such cases, dynamic programming cannot be applied directly, because local optimality does not compose into global optimality.

Overlapping Subproblems

A problem has overlapping subproblems if a recursive algorithm for the problem solves the same subproblems repeatedly rather than generating new subproblems at every step.

Consider the Fibonacci sequence defined by:

\[F(n) = F(n - 1) + F(n - 2)\]

with base cases \(F(0) = 0\) and \(F(1) = 1\). A naive recursive implementation computes \(F(n - 2)\) multiple times, leading to an exponential time complexity of \(O(2^n)\). By storing the result of each subproblem \(F(k)\) in a table (memoization or tabulation), each subproblem is solved only once, reducing the time complexity to \(O(n)\).

If subproblems do not overlap—as in merge sort, where each recursive call operates on a disjoint half of the array—storing subproblem results provides no benefit. Such problems are better suited to divide-and-conquer rather than dynamic programming.

How Both Properties Work Together

Optimal substructure ensures correctness, while overlapping subproblems ensure efficiency.

1. Optimal substructure guarantees that a recurrence relation exists linking the optimal value of the main problem to the optimal values of its subproblems.
2. Overlapping subproblems guarantee that caching those subproblem values avoids redundant computation, often turning exponential-time brute-force searches into polynomial-time algorithms.

When both properties are present, a problem is an ideal candidate for dynamic programming. If optimal substructure is missing, the recurrence will not produce the right answer; if overlapping subproblems are missing, dynamic programming offers no asymptotic speedup over standard recursion.