Dynamic Programming
1. Overview
A. Definition
Dynamic Programming (DP) is an optimization algorithm design technique that decomposes one large problem into overlapping smaller subproblems, computes each subproblem's solution only once and stores (remembers) it, then reuses it — thereby reducing exponential search to polynomial time.
Dynamic programming was formalized in the 1950s by Richard Bellman to solve multi-stage decision problems; in the name, "dynamic" refers to multi-stage decisions over time, and "programming" means mathematical optimization (planning). Today DP is one of the three major paradigms of algorithm design (divide-and-conquer, greedy, dynamic programming) and has become a core tool for eliminating the inefficiency of "solving the same subproblem repeatedly."
B. Background and necessity
Many optimization problems, when defined with naive recursion (exhaustive search), redundantly compute the same subproblem exponentially many times. The most common example is the Fibonacci sequence. If you recursively call fib(n) = fib(n-1) + fib(n-2) as written, fib(n-2) is computed twice, fib(n-3) three times, and the total number of calls explodes to roughly O(1.618ⁿ) in proportion to the golden ratio. Even at n=50, the calls reach hundreds of millions and do not finish in practical time. The number of distinct "solutions" is clearly polynomial, yet the search method is exponential — this contradiction is exactly what DP aims to resolve.
Dynamic programming removes this redundancy with the simple but powerful principle of "store the answer once computed, and fetch it when needed again." Fibonacci's distinct subproblems are only the n+1 values fib(0)~fib(n), so computing each exactly once finishes the whole in O(n). In other words, the essence of DP is to trade time for memory (the space-time trade-off), absorbing the exponential waste of redundant computation into polynomial storage space. For this trade to hold, the problem must satisfy two conditions.
The necessity of DP recurs in every optimization problem that "searches exponentially for a polynomial number of solutions." Seemingly unrelated problems — path finding, resource allocation, string alignment, scheduling — in fact share the common structure that "small decisions accumulate into the optimal overall decision," and exhaustive search makes the combinations of decisions explode exponentially. DP folds this explosion into an intermediate summary called a "state," letting a single stored value represent the countless paths that reach the same state. Learning DP, therefore, is not about memorizing individual problem solutions but about cultivating the eye to recognize this common structure and abstract it into states.
C. Two conditions under which DP holds
DP cannot be applied to just any problem. Its applicability is judged by two conditions: Optimal Substructure and Overlapping Subproblems. The former is the property that "the optimal solution of the large problem is composed of the optimal solutions of the small problems," and the latter is the property that "the same small problem appears repeatedly." The two conditions are independent, so if both hold, DP is appropriate; if only optimal substructure holds and there is no overlap, divide-and-conquer is appropriate; and if, in addition, a local optimum guarantees the global optimum, the greedy method is appropriate. This judgment is treated in detail in the comparison section below.
The two conditions together explain not only "whether DP applies" but also its "efficiency." If optimal substructure guarantees the recurrence's 'correctness' (does combining subsolutions yield the correct overall solution?), overlapping subproblems determine DP's 'benefit' (how much is saved by storing and reusing?). If there is almost no overlap, storage cost merely increases with no benefit, making it essentially no different from divide-and-conquer; the more overlap there is, the larger the reduction from exponential to polynomial. Therefore, the habit of explicitly checking both conditions when receiving a problem becomes the first gate that filters out both wrong application and unnecessary application.
2. Principles and Structure of Dynamic Programming
The overall structure of dynamic programming can be understood as the flow "decompose the problem → define state → recurrence → store and reuse → reconstruct solution." The structure diagram below shows at a glance the difference between exhaustive search (redundant computation) and DP (store and reuse).
flowchart TB
P["Original problem"] --> SUB["Decompose into subproblems"]
SUB --> CHK{"Already-computed<br/>subproblem?"}
CHK -->|"Yes (duplicate)"| MEM["Look up in store (O(1))"]
CHK -->|"No (first time)"| CALC["Compute via recurrence"]
CALC --> STORE["Record in store (memoize)"]
STORE --> COMB["Combine into parent solution"]
MEM --> COMB
COMB --> ANS["Optimal solution of original problem"]
A. Optimal Substructure
Optimal substructure is the property that the optimal solution of the whole problem is composed solely of the optimal solutions of its subproblems. For example, if the shortest path from Seoul to Busan passes through Seoul→Daejeon→Busan, then the Seoul→Daejeon segment contained in that path must itself be the shortest path from Seoul to Daejeon. If there were a shorter Seoul→Daejeon path, the whole path could also be shorter, contradicting the assumption of "optimality." Thanks to this property, a large problem can be expressed in the form of a 'recurrence relation' in terms of the answers to small problems.
Optimal substructure matters because, without it, no matter how many small-problem answers you store, you cannot construct the large problem. For example, the 'longest simple path' problem does not satisfy optimal substructure. Joining two partial paths may duplicate vertices and break the 'simple path' constraint, so combining partial optima does not guarantee the overall optimum. Thus, before applying DP, you must first verify that "combining subsolutions forms the overall solution."
B. Overlapping Subproblems
Overlapping subproblems is the property that, when solving a problem recursively, the same subproblem is called repeatedly many times. The typical example is fib(3) being recomputed several times in Fibonacci. The more this overlap, the greater the gain from DP. Conversely, like merge sort, if subproblems do not overlap and each handles new input, there is nothing to store and reuse, so divide-and-conquer — not DP — is the right choice.
Overlapping subproblems is quantified as 'the total number of distinct subproblems.' Fibonacci has n+1, the 0/1 knapsack problem has (number of items)×(capacity), and the longest common subsequence (LCS) has (length of string1)×(length of string2) distinct subproblems. The time complexity of DP is generally computed as 'number of distinct subproblems × cost of solving one subproblem,' so accurately grasping the size of the state space is the starting point of performance analysis.
This quantification becomes, in practice, the basis for judging before coding whether "DP will actually run." For example, if the state is (1,000 items)×(1,000,000 capacity), the number of states reaches a billion, exceeding both memory and time limits, signaling that one should consider state reduction or an approximation algorithm before applying DP directly. Conversely, if the number of states is within a few million, one can confidently design the DP. Thus, 'estimating the state-space size' is a practical checkpoint that validates the feasibility of applying DP in advance.
C. Two implementation styles — memoization and tabulation
DP is divided, by implementation style, into top-down memoization and bottom-up tabulation. Memoization keeps the recursive calls but stores computed results in a cache (array/hash map) and returns them immediately when the same call arrives. Its code is almost identical to the original recurrence, making it intuitive, and it has the advantage of computing only the subproblems actually needed; its downsides are the recursion stack depth limit and function-call overhead.
Tabulation fills a table from the smallest subproblem upward, advancing toward the large problem. Having no recursion, it has no stack overflow, and being loop-based with a small constant factor it is generally faster; however, it computes every subproblem without exception, so some may be unnecessary, and the computation order must be designed by hand. The table below organizes the selection criteria for the two styles; the difference stems not from mere taste but from the problem characteristics of "are there many unnecessary states, is the recursion deep?"
The choice between the two styles comes down, in practice, to concrete constraints. For example, if n exceeds 100,000 and the recursion depth risks surpassing the default stack limit (Python's 1,000, tens of thousands in many languages), recursion-based memoization may die with a stack overflow, forcing tabulation. Conversely, in a 'sparse' problem where the state space is theoretically enormous but the states actually visited are a tiny fraction, memoization — which computes only the needed states — is advantageous in both memory and time. In other words, the basis for the choice is not code taste but the quantitative characteristics of state-space density and recursion depth.
| Category | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Direction | Large → small problem (recursion) | Small → large problem (iteration) |
| Computation scope | Only needed subproblems | All subproblems |
| Advantage | Intuitive, good for sparse states | Stack-safe, small constant, easy space optimization |
| Disadvantage | Recursion overhead, stack limit | Requires order design, possible unnecessary computation |
| Suited for | Large and sparse state space | Dense state space, all needed |
3. Dynamic Programming Design Procedure
In practice, the process of solving a DP problem can be formalized into the following five-step procedure. The crux of this procedure lies not in coding but in the modeling step of 'defining the state and establishing the recurrence.'
flowchart LR
S1["1. Define state<br/>(what to store)"] --> S2["2. Build recurrence<br/>(relation between states)"]
S2 --> S3["3. Base cases<br/>(initial values)"]
S3 --> S4["4. Computation order<br/>(topological by dependency)"]
S4 --> S5["5. Reconstruct solution<br/>(backtracking)"]
Step 1, defining the state, is deciding "the variables that uniquely identify a subproblem." For example, the knapsack problem defines dp[i][w] as "the maximum value when considering only the first i items and the capacity is w." If the state is chosen wrongly, the recurrence does not hold, so this step determines the success or failure of the whole design. Step 2, the recurrence, expresses the dependency between states as a formula. Step 3, base cases, specifies the values of the minimal states at which recursion stops (e.g., dp[0][*]=0). Step 4, computation order, topologically sorts which states must be filled first according to dependencies, which is especially important in tabulation. Step 5, reconstructing the solution, is the step that backtracks to recover not only the optimal value but also "the choices that produced it (which items were packed)," tracing back the stored decision path.
The point where beginners most often fail in this procedure is steps 1–2. If the state is defined too narrowly (failing to capture the needed information in the state), the recurrence depends on past choices and does not hold; if too broadly, the state space explodes and the complexity becomes unrealistically large. Therefore, the key question of state definition is "what is the minimal information needed to make the current decision." The recurrence likewise reduces to the single sentence 'in terms of which smaller states can the current state be expressed,' and once this modeling is clearly laid out on paper, the implementation is close to mechanical work. Even in a professional-engineer answer, it is this trinity of state, recurrence, and base cases — presented as formulas rather than code — that is the center of evaluation.
4. Representative Cases
Before entering the representative cases, confirming DP's effect numerically with the simplest case, Fibonacci, makes the subsequent cases clearer. Solving fib(50) by naive recursion generates about 2×10¹⁰ function calls, taking tens of seconds on an ordinary PC, but filling dp[0]=0, dp[1]=1, dp[i]=dp[i-1]+dp[i-2] bottom-up finishes instantly in 51 additions. Moreover, since Fibonacci depends only on the two immediately preceding values, it can be computed with just two variables (O(1) space) without keeping the entire array. This one example compresses all three cores of DP — removing redundancy, trading space for time, and optimizing the state space.
A. 0/1 Knapsack Problem
The 0/1 knapsack problem fills a backpack of capacity W with items of given weight and value to maximize the total value, where each item is either packed or not (0 or 1), choosing only one of the two. Exhaustive search inspects all 2ⁿ subsets of n items, which is exponential, but DP fills only n×W states with the recurrence dp[i][w] = max(dp[i-1][w], dp[i-1][w-weightᵢ] + valueᵢ) and solves it in O(nW). For example, with n=100, W=1000, exhaustive search is 2¹⁰⁰ (about 10³⁰) operations, whereas DP finishes in 100,000 operations, completely crossing the boundary of practicality.
A point of caution is that this O(nW) is 'pseudo-polynomial.' W is a 'value' of the input, not its 'size (number of bits),' so if W is very large it is still unrealistic. This is exactly why 0/1 knapsack, while classified as NP-hard, is solvable by DP. This case simultaneously illustrates the principle that "DP's complexity is proportional to the size of the state space" and the pitfall when that state space depends on the input value.
B. Longest Common Subsequence (LCS) and Edit Distance
LCS finds the longest subsequence that can be drawn in common, preserving order, from two strings; it defines dp[i][j] as "the LCS length of the first i characters of string1 and the first j characters of string2." If the characters match, fill with dp[i-1][j-1]+1; if they differ, with max(dp[i-1][j], dp[i][j-1]), solving in O(mn). Edit distance (Levenshtein Distance) also computes the minimum number of the three operations — insertion, deletion, substitution — with the same 2D DP.
These two cases are very widely used industrially. LCS is the basis of git diff / version-control difference comparison and DNA sequence alignment (bioinformatics), while edit distance is used in spell correction, search-query typo correction, and DNA similarity measurement. For example, when a search engine suggests a correction for the typo "teh" of "the," it computes via DP the fact that the edit distance between the two words is small and uses it. String similarity, one of the metrics for evaluating generative-AI outputs, is also rooted in this family of DP.
C. Floyd-Warshall (All-Pairs Shortest Paths)
Floyd-Warshall is a DP algorithm that finds the shortest paths between all pairs of vertices in a graph. It defines dp[k][i][j] as "the shortest distance i→j when only vertices 1~k are allowed as intermediate points," and updates with dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]), increasing the intermediate vertex k one at a time. This algorithm, which finds all pairs in O(V³) with three nested loops, is used in routing-table computation, network latency analysis, and transportation-network distance tables. It has the advantages of being more concise to implement than repeating Dijkstra from every vertex and of handling negative weights (excluding negative cycles).
The lesson of Floyd-Warshall is the idea of 'adding a transit-vertex dimension to the state.' Defining the shortest path by distance alone makes the recurrence cyclic and invalid, but putting the "set of allowable transit vertices" as the stage variable k creates an acyclic structure in which k increases monotonically, making DP possible. That the same problem can be solvable or unsolvable depending on how the state is defined shows pointedly why state design is the core of DP.
D. Longest Increasing Subsequence (LIS)
The longest increasing subsequence (LIS) finds the length of the longest 'increasing' subsequence that can be drawn from a sequence while preserving order. The basic DP defines dp[i] as "the LIS length ending at the i-th element" and fills with dp[i] = max(dp[j]) + 1 (where j<i and elementⱼ<elementᵢ), solving in O(n²). For example, the LIS of [10, 9, 2, 5, 3, 7, 101, 18] is [2, 3, 7, 18] with length 4, obtained by having each position inherit the maximum of the dp values of the preceding elements smaller than itself.
LIS matters educationally because it is a typical case of combining DP with another data structure to make it faster. Grafting on binary search, one can find in O(log n) the position at which to insert each element into a 'tail array of increasing sequences,' improving the whole to O(n log n). This is an advanced design pattern of "the DP recurrence itself is O(n²), but the transition cost is reduced with a data structure to lower the overall complexity," and it is the starting point of DP optimization combined with segment trees and Fenwick trees. In practice, it is used in variant forms for job scheduling, version-compatibility path finding, and stock-trend analysis.
5. Comparison with Divide-and-Conquer and Greedy
All three paradigms share the common point of "breaking the problem down small," but they diverge in whether subproblems overlap and in the selection strategy. The table below summarizes the differences, while also looking at the 'reason' the differences arise.
| Category | Dynamic Programming | Divide-and-Conquer | Greedy |
|---|---|---|---|
| Subproblem overlap | Yes (store and reuse) | No (independent) | No |
| Development direction | Both bottom-up/top-down | Top-down (recursion) | Sequential decisions |
| Selection method | Compare all cases, then optimal | Divide then merge | Local optimum each step |
| Optimality guarantee | Always (when conditions met) | Depends on division criterion | Requires greedy-choice property |
| Representative examples | Knapsack, LCS, Floyd | Merge sort, binary search | Coin change, MST, Huffman |
The decisive difference between divide-and-conquer and DP is whether subproblems overlap. Merge sort divides the array in half, but the two halves are completely independent, so there is nothing to reuse. In contrast, Fibonacci's fib(n-1) and fib(n-2) share fib(n-2), so storage pays off. In other words, "do the divided pieces overlap with each other?" decides whether to use DP or divide-and-conquer.
The difference between greedy and DP lies in the revisability of the choice. The greedy method makes the choice that looks best at each step and never looks back. For this to guarantee the global optimum, the 'greedy-choice property' must be proven. For example, the fractional knapsack is optimal with a greedy method that packs in descending order of value per unit weight, but the 0/1 knapsack is not, so one must compare all cases with DP. The practical implication is clear — if the greedy method is correct it is faster and simpler than DP, but if the proof of the greedy-choice property fails, one must safely switch to DP. Premature greedy application produces the most dangerous kind of bug: "mostly correct but occasionally wrong."
In fact, the three paradigms lie on a continuum rather than being mutually exclusive. The greedy method can be seen as "a special DP that leaves only one choice at each step," and divide-and-conquer as "a special DP in which subproblems do not overlap." From this viewpoint, when facing a problem, a decision flow naturally emerges: check in order ① whether subproblems overlap (if not, divide-and-conquer), and ② if they overlap, whether a single choice per step suffices (if so, greedy; otherwise, general DP). At the professional-engineer level, one should embody this discrimination flow itself as design knowledge — beyond memorizing individual algorithms — and be able to present, with grounds, which paradigm suits a given business problem.
6. Advanced Topics: State-Space Optimization and Recent Uses
A practical difficulty of DP is when the state space exceeds memory. A representative remedy is the sliding-window (rolling-array) technique: if the recurrence depends only on the immediately previous row (dp[i-1]), the 2D array is compressed into 1D, reducing space from O(nW) to O(W). An example is obtaining exactly the same answer with just a 1D array by iterating capacity in reverse order in the knapsack problem. In addition, bitmask DP, which encodes the state as a bitmask, solves problems that take a set as the state — such as the traveling salesman problem (TSP) — in O(2ⁿ·n²), which is dramatically faster than exhaustive search's O(n!). At n=15, the difference between 15! (about 1.3 trillion) and 2¹⁵·15² (about 7.4 million) again demonstrates DP's power.
Another representative case in industry is option pricing in financial engineering. The binomial-tree model for valuing an American option (which can be exercised early before maturity) computes the value at each time/price node backward from the value at maturity as max(immediate-exercise value, discounted expected value of holding) — a typical bottom-up DP. Also, a database query optimizer, when deciding the join order of multiple tables, searches with bitmask DP for the minimum-cost join plan per subset, finding the optimal order in O(3ⁿ) (a classic technique since System R). Viterbi decoding in communications likewise finds the maximum-likelihood path of a convolutional code by DP, showing that DP is a core engine across finance, DB, and communications beyond the algorithm textbook.
As a recent trend, DP has permeated machine learning and natural language processing deeply, beyond traditional algorithms. Hidden Markov Model (HMM) decoding, the core of speech recognition and handwriting recognition, finds the optimal state sequence with a DP called the Viterbi algorithm, and the Needleman-Wunsch and Smith-Waterman algorithms for DNA/protein sequence alignment are also edit-distance-family DP. The Bellman Equation of reinforcement learning takes its name directly from the founder of dynamic programming, and Value Iteration and Policy Iteration are both direct applications of DP. From the professional-engineer viewpoint, DP should be understood not as a mere coding technique but as a general thinking framework that decomposes optimal decision-making into multiple stages.
Likely exam directions include: ① deriving the recurrence and complexity of a specific problem (knapsack, LCS, longest increasing subsequence, etc.), ② comparison with divide-and-conquer and greedy and discriminating the application conditions, ③ the rationale for choosing memoization/tabulation, and ④ the relationship between pseudo-polynomial complexity and NP-hardness. When writing an answer, it is a high-scoring strategy to always state the recurrence, derive the complexity from the state-space size, and also describe the grounds for "why DP and not greedy/divide-and-conquer" (optimal substructure, overlapping subproblems).
Illustrating a concrete answer-composition strategy: even for a short-answer item in the first session, depth shows if you have the skeleton "definition → the two conditions → one representative recurrence (e.g., knapsack) → complexity → a one-line comparison with other techniques." For an essay in the second or third session, layer on top of this ⓐ a concept diagram (the difference between exhaustive search and DP), ⓑ the five-step design procedure, ⓒ the recurrence and complexity derivation per case for two or more cases, ⓓ state-space optimization (sliding window, bitmasking) techniques, and ⓔ a professional-engineer-perspective application judgment (the pitfall of pseudo-polynomiality, the paradigm-selection flow). In particular, the grader sees "can you build a recurrence?" and "can you discriminate the application conditions?" as the key differentiators, so it is decisive to reveal in prose the thought process from state definition to recurrence, rather than a memorized result.
7. Considerations and Implications
- Prior verification of application conditions (correctness): DP is not a panacea. One must first verify that both optimal substructure and overlapping subproblems hold; applying DP to a problem like the longest simple path, where combining subsolutions does not guarantee the overall solution, yields a wrong answer. Before design, always prove "does combining subsolutions form the overall solution?"
- Managing the space-time trade-off (resource efficiency): DP trades time for memory. When the state space exceeds the memory limit, a design that reduces space with sliding windows, state compression, or sparse storage (hash maps) is essential. In embedded and large-scale environments, whether this optimization is done governs the feasibility of application.
- The pitfall of pseudo-polynomial complexity (performance judgment): When the complexity is proportional to the input 'value,' as in the knapsack problem's O(nW), it is in effect exponentially slow when the value is large. That an NP-hard problem is solvable by DP does not mean it is practical at all scales, so judge the validity of application based on the input range.
- The strategy of paradigm selection (design judgment): If the greedy method holds, it is faster and simpler than DP, so consider it first; but if the proof of the greedy-choice property fails, switch to DP. If subproblems are independent, divide-and-conquer is right. Rather than seeing the three paradigms as mutually exclusive, the engineer's competence is the discernment to select and combine them according to problem characteristics.
- Extension to a general thinking framework (outlook and related technologies): DP is a general optimization framework that extends to reinforcement learning (the Bellman equation), sequence alignment (bioinformatics), and speech/handwriting recognition (Viterbi). Understanding it as linked to the foundational technologies of the AI/data field, beyond traditional algorithms, greatly broadens its scope of application.
References
- Cormen et al., "Introduction to Algorithms", MIT Press (dynamic programming, optimal substructure)
- R. Bellman, "Dynamic Programming", Princeton University Press, 1957
- cp-algorithms, Dynamic Programming: https://cp-algorithms.com/dynamic_programming/
In one line: Dynamic programming is a technique that, for problems where optimal substructure and overlapping subproblems hold, divides the problem into subproblems and stores and reuses their solutions to reduce exponential search to polynomial time; it is implemented with memoization/tabulation, and — unlike greedy and divide-and-conquer — its core is the design judgment of "compare all cases but compute each duplicate only once."