Algorithms: Dynamic Programming

Dynamic programming (DP) is a core algorithmic technique for solving optimization and counting problems that have a recursive structure. It is most useful when a problem can be broken into smaller subproblems that repeat, and when the best solution to the full problem can be assembled from best solutions to those subproblems. DP is behind many classic algorithms, including the knapsack problem and the longest common subsequence (LCS), and it shows up in practical systems from scheduling to sequence alignment.

At its heart, DP replaces repeated computation with reuse. Instead of recomputing the same sub-results over and over in a recursive tree, DP stores them once and builds on them.

When dynamic programming applies

Two properties usually signal that DP is a good fit: optimal substructure and overlapping subproblems.

Optimal substructure

A problem has optimal substructure when an optimal solution can be constructed from optimal solutions to its subproblems. This is what makes “build up from smaller answers” correct.

A simple example is shortest paths in certain formulations: the shortest path to a node can be formed from shortest paths to predecessors plus one edge. In knapsack and LCS, the optimal answer for a prefix of the input depends on optimal answers to smaller prefixes.

Optimal substructure is not just “it uses recursion.” It is a correctness condition. If local optimal choices do not compose into a global optimum, then DP might not work without additional state or a different approach.

Overlapping subproblems

Overlapping subproblems means the recursive decomposition leads to the same subproblems being solved many times. A naive recursive LCS implementation is the textbook illustration: it branches on whether the last characters match, and it revisits the same prefix pairs repeatedly. DP removes that waste by caching or tabulating the result for each subproblem state.

If subproblems do not overlap (for example, a recursion that forms a tree with unique nodes), memoization may not help much, and divide-and-conquer might be more appropriate.

The DP mindset: state, recurrence, and answer

Most DP solutions follow a disciplined pattern:

1. Define the state: what parameters uniquely identify a subproblem?
2. Write the recurrence: how does the answer for a state depend on smaller states?
3. Choose a computation order: top-down with memoization or bottom-up with tabulation.
4. Return the final answer: the state corresponding to the full input.
5. Optionally: reconstruct the solution, not just its value.

Getting the state right is the most important step. Too little state makes the recurrence incorrect; too much state increases time and memory.

Memoization vs. tabulation

Dynamic programming is commonly implemented in two styles.

Memoization (top-down)

Memoization starts from the original problem and uses recursion to explore needed subproblems. Each time a subproblem is solved, its result is stored (often in an array or hash map) so future calls can reuse it.

This style has two practical advantages:

• It is often easier to write because it mirrors the natural recursive definition.
• It computes only the states that are actually reachable from the starting state.

The main downside is recursion overhead and the risk of deep recursion hitting stack limits, depending on the language and input size.

Tabulation (bottom-up)

Tabulation computes answers in an order where all dependencies of a state are computed before the state itself, typically by filling in a table.

This style is iterative, avoids recursion, and can be easier to optimize for performance. It often makes space optimization more straightforward because you can see which previous rows or columns are needed.

The downside is that you may fill states that are never used, especially when the state space is large but sparse.

Classic example: 0/1 knapsack

In the 0/1 knapsack problem, you have items with weights and values and a capacity $W$. Each item can be chosen at most once. The goal is to maximize total value without exceeding capacity.

State and recurrence

A common DP state is:

• $dp[i][w]$ = maximum value achievable using the first $i$ items with capacity limit $w$.

Recurrence:

• If you do not take item $i$, value is $dp[i-1][w]$.
• If you take item $i$ (weight $w{t}_i\le w$), value is $dp[i-1][w-w{t}_i]+va{l}_i$.

So:

$$dp[i][w]=\max \left(dp[i-1][w],dp[i-1][w-w{t}_i]+va{l}_i\right)$$

The answer is $dp[n][W]$.

Complexity and practical notes

The standard DP runs in $O(nW)$ time and uses $O(nW)$ space. When $W$ is large (for example, up to millions), that may be impractical. A common optimization uses a 1D array $dp[w]$ and iterates $w$ downward to preserve correctness for 0/1 selection. This reduces space to $O(W)$ while keeping time $O(nW)$.

This illustrates an important practical lesson: DP complexity often depends on numeric parameters like capacity, not just input length. In such cases, the algorithm is sometimes called “pseudo-polynomial.”

Classic example: longest common subsequence (LCS)

Given two strings $A$ and $B$, the LCS problem asks for the longest sequence of characters that appears in both strings in order (not necessarily contiguously). LCS is widely used as a building block in diff tools and sequence comparison.

State and recurrence

Let:

• $dp[i][j]$ = length of LCS of prefixes $A[\mathrm{0..}i-1]$ and $B[\mathrm{0..}j-1]$.

Recurrence:

• If $A[i-1]=B[j-1]$, then the character can extend a common subsequence:

$$dp[i][j]=dp[i-1][j-1]+1$$

• Otherwise, the best LCS comes from dropping one character from either prefix:

$$dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$$

The final length is $dp[|A|][|B|]$.

Reconstructing the subsequence

DP tables can store more than lengths. If you need the actual subsequence, you can backtrack from $dp[m][n]$:

• If characters match, include it and move diagonally.
• Otherwise, move to the neighbor (up or left) that preserved the maximum.

This is a recurring DP theme: the table provides both the optimal value and a trail of decisions, enabling reconstruction of an optimal solution.

How to recognize and design DP solutions

Dynamic programming problems vary, but several patterns recur.

Choose a state that captures “what’s left”

The state should summarize everything needed for optimal decisions. For knapsack, it is “how many items considered” and “remaining capacity.” For LCS, it is “how far into each string.” In scheduling problems, it might be “time index” and “last chosen job.” The state is a compact memory of the past that makes the future independent.

Ensure subproblems get smaller

A valid recurrence must move toward base cases. This is not just for termination; it determines the order needed for tabulation. If dependencies form cycles, you may need a different formulation.

Pay attention to memory

DP tables can grow quickly. Common tactics include:

• Rolling arrays (keeping only the previous row/column when the recurrence allows it).
• Sparse memoization with maps when only a small subset of states is reached.
• Storing only what you need for the final value, unless reconstruction is required.

Common pitfalls

• Incorrect state: forgetting a constraint that affects future choices leads to wrong answers.
• Double counting in counting DPs: ensure each state represents a unique subproblem.
• Wrong iteration order: especially in 1D optimizations like knapsack, iterating the capacity in the wrong direction changes the meaning (0/1 vs unbounded).
• Assuming DP always means polynomial: complexity depends on the size of the state space, which can be exponential if the state is not carefully designed.

Why dynamic programming matters

Dynamic programming is not a single algorithm but a method for turning recursive structure into efficient computation. It is a practical bridge between mathematical recurrence relations and working software: you define subproblems, reuse their solutions, and systematically reach an optimal result. Mastering optimal substructure, overlapping subproblems, memoization, and tabulation gives you a toolkit that applies across classic interview problems and real-world optimization tasks alike.