Dynamic Programming

Introduction and Context

Dynamic programming (DP) is a general algorithm-design paradigm for solving problems whose solutions can be assembled from solutions to smaller, related subproblems. Its central contribution is not a particular data structure or programming language technique, but a way of recognizing and exploiting two structural properties: optimal substructure and overlapping subproblems.

The method was formalized by Richard Bellman in the 1950s. The word “programming” originally referred to planning or optimization rather than software development. DP is especially important in artificial intelligence and machine learning because many inference, planning, sequence-processing, resource-allocation, and decision problems can be expressed as optimization over a sequence of states.

A naïve recursive algorithm may solve the same subproblem repeatedly, producing exponential running time. Dynamic programming stores each subproblem’s result once, usually reducing the time complexity to the number of distinct states multiplied by the work required per state.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Explain optimal substructure and overlapping subproblems.
2. Formulate a state space, recurrence relation, boundary conditions, and evaluation order.
3. Distinguish memoization from tabulation and analyze their complexities.
4. Apply DP to sequences, graphs, resource allocation, and probabilistic inference.
5. Reconstruct an optimal solution rather than merely its value.
6. Evaluate assumptions, scalability, numerical issues, and implementation risks.
7. Design and critically assess DP solutions for AI and machine-learning applications.

1. The Core Idea

Suppose a problem has an input instance of size n. A recursive decomposition produces smaller instances. If different branches generate the same instance, the recursion tree contains repeated work. DP converts that recursion tree into a directed acyclic graph (DAG) of states and computes each state once.

Two conditions are fundamental.

Optimal substructure

A problem has optimal substructure if an optimal solution contains optimal solutions to its relevant subproblems. For example, if the shortest path from u to v passes through w, then the portion from u to w must itself be a shortest path; otherwise the complete path could be improved.

This property is not universal. It depends on the objective and constraints. A locally optimal subsolution may fail to be globally useful when constraints couple otherwise independent decisions.

Overlapping subproblems

Subproblems overlap when the same subproblem occurs in multiple recursive branches. Fibonacci computation illustrates this. The recurrence is:

The naïve recursion has exponential time, approximately O(φⁿ), where φ = (1 + √5)/2, because values such as F(n − 2) are recomputed. With a table, each F(i), 0 ≤ i ≤ n, is computed once, giving O(n) time and O(n) space; an iterative version can reduce auxiliary space to O(1).

2. A General DP Design Framework

A reliable DP design usually follows these steps:

1. Define the state. Specify exactly what information identifies a subproblem.
2. Define the value. State what the DP entry represents: a minimum cost, maximum value, count, probability, or Boolean feasibility result.
3. Derive the recurrence. Condition on the final decision, first decision, or last transition.
4. Specify boundary conditions. Define states with no remaining decisions or empty inputs.
5. Choose an evaluation order. Ensure every dependency is available before a state is evaluated.
6. Determine complexity. Count states and transitions, and account for storage.
7. Store decisions when reconstruction is required. A value table alone may not identify the solution.
8. Validate the formulation. Test empty, minimal, maximal, infeasible, and tied cases.

For a state set S, if each state s has at most d transitions and transition evaluation costs O(1), then the usual running time is O(|S|d), and the memory requirement is O(|S|), unless states are safely discarded after use.

A recurrence alone is not an algorithm. Correctness also requires a state definition, initialization, termination, and an argument that all dependencies are evaluated.

3. Top-Down and Bottom-Up Methods

Memoization: top-down DP

Memoization retains the recursive formulation but caches computed results. It is useful when only a fraction of the theoretically possible states is reachable.

Solve(state):
    if state is in cache: return cache[state]
    if state is a base case: return base_value
    best ← combine(Solve(next_state) for each valid next_state)
    cache[state] ← best
    return best

Advantages include direct correspondence with the recurrence and natural handling of sparse state spaces. Disadvantages include recursion overhead, possible stack overflow, and the need to manage cycles carefully.

Tabulation: bottom-up DP

Tabulation computes states in an order determined by their dependencies. It normally avoids recursion and often permits space compression.

Advantages include predictable memory use, efficient iteration, and easy control of resource limits. It may calculate states that are unreachable from the initial state.

Memoization and tabulation have the same asymptotic complexity when all states are reached, but their practical behavior may differ substantially.

4. Worked Example: 0/1 Knapsack

In the 0/1 knapsack problem, there are n items. Item i has value vᵢ and weight wᵢ. A knapsack has capacity W. Each item may be selected at most once. The objective is to maximize total value subject to total weight not exceeding W.

Define V(i, c) as the maximum value obtainable using the first i items with capacity c, where 0 ≤ i ≤ n and 0 ≤ c ≤ W. For item i, either it is excluded or, if wᵢ ≤ c, included:

The boundary condition is V(0, c) = 0 for every c, and V(i, 0) = 0 for every i. The table has (n + 1)(W + 1) states, so time and space are O(nW). This is pseudo-polynomial, not polynomial in the binary input length, because W may be exponentially larger than log₂W.

Consider capacity W = 7 and items:

The best feasible combination is items 2 and 4, with weight 8, which is infeasible. Items 1 and 4 have weight 7 and value 10; items 2 and 3 have weight 7 and value 9. Therefore the optimum is 10, obtained by items 1 and 4.

A one-dimensional implementation uses:

dp[0..W] ← 0
for each item (w, v):
    for c from W down to w:
        dp[c] ← max(dp[c], v + dp[c − w])

The descending capacity order is essential. It prevents the current item from being reused in the same iteration, thereby preserving the 0/1 restriction. If capacity is iterated upward, the algorithm instead behaves like an unbounded-knapsack algorithm.

5. Sequence and String Problems

Longest common subsequence

Given sequences X = x₁…xₘ and Y = y₁…yₙ, a subsequence preserves order but need not be contiguous. Let L(i, j) be the length of a longest common subsequence of prefixes X[1..i] and Y[1..j].

Boundary conditions are L(0, j) = L(i, 0) = 0. The time complexity is O(mn), and the full table requires O(mn) space. If only the length is needed, two rows suffice; if an actual subsequence is required, predecessor information or a reconstruction procedure is needed.

LCS is used in version comparison, bioinformatics, plagiarism analysis, and change detection. It should not be confused with longest common substring, which requires contiguity and has a different recurrence.

Edit distance

For strings X and Y, edit distance is the minimum number of insertions, deletions, and substitutions needed to transform X into Y, with each operation assigned a cost. Let D(i, j) denote the minimum cost for prefixes of lengths i and j. With insertion cost cᵢₙₛ, deletion cost c_dₑₗ, and substitution cost cₛᵤᵦ(xᵢ, yⱼ):

The boundary values are D(i, 0) = i c_dₑₗ and D(0, j) = j cᵢₙₛ. The recurrence assumes additive operation costs and that edits are applied sequentially. Under unit costs, the usual Levenshtein distance is obtained. The standard complexity is O(mn).

6. Interval and Partition DP

Some problems are naturally defined over contiguous intervals. Matrix-chain multiplication is a canonical example. Given matrices A₁…Aₙ, where Aᵢ has dimensions pᵢ₋₁ × pᵢ, the multiplication order affects scalar multiplication cost but not the result.

Let M(i, j) be the minimum number of scalar multiplications needed to compute Aᵢ…Aⱼ. Then:

The base case is M(i, i) = 0. Filling intervals by increasing length yields O(n³) time and O(n²) space. The split k must be recorded to reconstruct the parenthesization.

Interval DP appears in parsing, optimal binary search trees, polygon triangulation, RNA secondary-structure prediction, and segmentation. Its principal design question is often: “At which boundary or split was the last combination performed?”

7. Graph and State-Space DP

Directed acyclic graphs

For a DAG, shortest paths can be found by processing vertices in topological order. If dist(s) = 0 and all other distances initially represent infinity, then for each edge u → v with weight w(u,v):

Because every edge points from an earlier to a later topological position, no repeated relaxation is needed. The complexity is O(|V| + |E|). Negative edge weights are permitted in a DAG, provided there is no cycle; a negative cycle cannot occur in a DAG.

Bellman–Ford as repeated relaxation

For general directed graphs, Bellman–Ford performs up to |V| − 1 rounds of edge relaxation and detects reachable negative cycles with an additional round. Its O(|V||E|) complexity can be understood as DP over the number of edges permitted in a path. This illustrates that DP can be used even when the state graph is not explicitly constructed, provided a bounded progression measure exists.

Resource-constrained paths

A state may combine a graph vertex with a resource quantity, such as time, energy, or budget: state (v, b). This often yields pseudo-polynomial complexity O(|E|B), where B is a numeric resource bound. Such formulations are useful in routing and scheduling but can become infeasible when resources are large or multidimensional.

8. Dynamic Programming in AI and Machine Learning

Hidden Markov models

In a hidden Markov model, hidden state zₜ emits observation xₜ. The Viterbi algorithm finds the most probable hidden-state sequence. Let δₜ(j) be the maximum probability of a state sequence ending in state j at time t. With initial probability πⱼ, transition probability aᵢⱼ, and emission probability bⱼ(xₜ):

Backpointers identify the maximizing predecessor. For T observations and K states, the ordinary implementation requires O(TK²) time and O(TK) storage, or O(K) storage when only the final score is required. For numerical stability, probabilities are commonly represented in log space, converting multiplication into addition and avoiding underflow.

The forward algorithm replaces maximum with summation to calculate observation likelihoods; the backward algorithm processes evidence from the opposite direction. These are distinct objectives and should not be conflated with Viterbi decoding.

Reinforcement learning and planning

Finite-horizon optimal control uses a Bellman recurrence. Let Vₜ(s) be the optimal expected return from state s at time t, reward r(s,a), transition probability P(s′|s,a), discount factor γ, and terminal value V_T(s). Then:

The equation assumes a Markov state representation: the current state contains all information needed to predict future rewards and transitions. If the state omits relevant history, the recurrence may produce an invalid policy. In infinite-horizon discounted problems, 0 ≤ γ < 1 commonly supports convergence under standard bounded-reward assumptions, although convergence and uniqueness depend on the model and operator conditions.

Modern reinforcement learning often approximates value functions rather than storing a table. Approximation improves scalability but introduces estimation error, instability, and exploration concerns; it is not equivalent to exact tabular DP.

9. Correctness and Complexity Analysis

A DP correctness proof commonly uses induction on a state measure such as prefix length, interval length, time, or topological rank.

1. Base case: Show that boundary states have the correct values.
2. Inductive hypothesis: Assume all smaller states are correct.
3. Inductive step: Show that the recurrence considers every feasible final decision and combines correct subproblem values, so it returns the optimum for the current state.

Complexity should be separated into:

• Number of states: for example, O(mn) prefix pairs.
• Transitions per state: for example, O(K) predecessor states.
• Transition cost: comparison, arithmetic, or a more expensive operation.
• Storage: values, backpointers, and input representation.

Space optimization is valid only when discarded states will never be needed again. For example, a row-compressed LCS table preserves length but generally loses direct reconstruction information. In-place updates also require a dependency-aware iteration direction.

10. Case Study: Dynamic Programming for Workforce Scheduling

This is an illustrative case. A service centre must schedule staff over T days. On day t, demand requires a minimum number of workers. Employees can be assigned to a regular shift or an overtime shift. A worker scheduled today may affect tomorrow’s availability because of rest requirements.

Background and problem

Management wants the minimum total labour cost while satisfying daily demand and legal rest constraints. A greedy strategy that selects the cheapest shift each day can create an expensive shortage on the next day.

State formulation

Let s represent the number of workers available at the beginning of day t. Define C(t, s) as the minimum cost from day t through day T. An action a specifies the number assigned to regular and overtime shifts. The transition produces next availability s′ = f(s, a), subject to demand and labour regulations.

The terminal condition is C(T + 1, s) = 0 for every permissible terminal state. A decision table records the action attaining each minimum.

Analysis and solution

The state must include every factor that affects future feasibility. If worker skill categories or accumulated hours affect future choices, they must be added to the state; omitting them violates the Markov assumption. The algorithm evaluates days backward or uses memoized recursion. If there are T days, S availability levels, and A feasible actions per state, its time complexity is O(TSA), with O(TS) storage when decisions are retained.

Outcome and learning points

The resulting schedule is globally optimal for the specified cost model and constraints. It also exposes trade-offs through sensitivity analysis: changing overtime cost, demand, or rest rules changes the recurrence inputs. The case demonstrates that DP is not merely a coding technique. It is a modelling discipline: poor state definitions produce confidently incorrect schedules.

11. Limitations, Risks, and Best Practices

The principal limitation is the curse of dimensionality. If a state has d dimensions and each dimension has m possible values, the table may require O(mᵈ) entries. Continuous variables require discretization, which introduces approximation error. Large numeric capacities can cause pseudo-polynomial algorithms to become impractical.

Other limitations include:

• A recurrence may be difficult to discover or prove.
• State compression can remove information needed for reconstruction.
• Floating-point probabilities may underflow or accumulate rounding error.
• Ties require a documented tie-breaking policy if reproducibility matters.
• Infeasible states must be represented explicitly, not confused with valid zero-cost states.
• Hidden constraints can invalidate optimal substructure.
• Parallelization may be limited by dependencies between states.

Best practices include writing the semantic meaning of every state before coding, testing boundary cases, using exact integers where appropriate, using log probabilities for long sequences, checking monotonicity or known bounds, profiling reachable-state density, and separating value computation from policy reconstruction.

In regulated or high-impact AI systems, DP-based decisions should be auditable. The system should retain model assumptions, cost weights, constraints, data provenance, and selected actions. Optimization can reproduce social or organizational bias when the objective or constraints encode discriminatory priorities. A mathematically optimal schedule is not automatically ethically acceptable. Human review, fairness analysis, privacy protection, and domain-specific legal compliance remain necessary.

12. Contemporary Developments

Current research combines DP with approximation, machine learning, and specialized hardware. Approximate dynamic programming uses function approximation to represent values compactly. Sparse and factored representations exploit structure in large state spaces. Neural networks may approximate value functions or guide search, while differentiable relaxations make some optimization procedures compatible with gradient-based learning.

These developments improve scale but weaken guarantees. Approximation error can alter policy rankings, and learned heuristics may fail outside their training distribution. Consequently, advanced systems should report performance bounds where available, conduct out-of-distribution testing, and preserve interpretable constraints even when value estimation is learned.

Chapter Summary

Dynamic programming solves optimization and counting problems by decomposing them into states with optimal substructure and overlapping subproblems. A complete DP design specifies state semantics, recurrence, boundary conditions, evaluation order, complexity, and—when needed—backpointers for reconstruction. Memoization is top-down and often sparse; tabulation is bottom-up and offers predictable iteration and memory behavior.

The chapter applied DP to knapsack, LCS, edit distance, matrix-chain multiplication, DAG shortest paths, hidden Markov models, reinforcement learning, and workforce scheduling. Complexity depends on the number of states and transitions, and numeric bounds may make an algorithm pseudo-polynomial. In AI, Bellman-style recurrences support probabilistic decoding and sequential decision-making, but assumptions such as the Markov property must be justified. Scalability, numerical stability, ethical objectives, auditability, and approximation error are central professional concerns.

Key Terms

Dynamic programming: An algorithmic paradigm that stores solutions to subproblems and combines them to solve a larger problem.

State: A precise representation of the information defining a subproblem.

Optimal substructure: The property that an optimal solution contains optimal solutions to relevant subproblems.

Overlapping subproblems: Repeated occurrence of identical subproblems in recursive decomposition.

Recurrence: An equation defining a state value using other state values.

Boundary condition: A value assigned to a smallest or terminal state.

Memoization: Top-down caching of recursively computed results.

Tabulation: Bottom-up computation of a table in dependency order.

Backpointer: Stored predecessor or decision used to reconstruct a solution.

State transition: A permitted movement from one state to another.

Pseudo-polynomial: Polynomial in a numeric value, but not necessarily in the input’s bit length.

Interval DP: Dynamic programming over contiguous ranges or intervals.

Topological order: An ordering of DAG vertices in which every edge goes forward.

Bellman recurrence: A recurrence expressing optimal future value through current decisions and successor states.

Viterbi algorithm: DP for the most probable hidden-state sequence in a hidden Markov model.

Value function: The optimal expected return associated with a state.

Curse of dimensionality: Rapid growth of state-space size as state dimensions increase.

State compression: Reducing stored DP information while preserving the required result.

Review Questions

Short Answer Questions

1. What are the two structural properties that make dynamic programming applicable?
2. Distinguish memoization from tabulation.
3. Why must capacity be iterated downward in one-dimensional 0/1 knapsack DP?
4. What information does a backpointer store?
5. Why is the standard knapsack algorithm called pseudo-polynomial?

Long Answer Questions

1. Derive the LCS recurrence, including boundary conditions, and explain how an LCS can be reconstructed.
2. Explain the design and correctness proof of matrix-chain multiplication DP.
3. Compare DAG shortest-path DP with Bellman–Ford relaxation.
4. Explain the Viterbi recurrence and discuss numerical underflow in long sequences.
5. Discuss the curse of dimensionality and evaluate methods for making large DP models practical.

Analytical / Application Questions

1. Design a DP formulation for selecting projects under a budget when each project may be selected at most once. Define the state, recurrence, base cases, complexity, and reconstruction method.
2. A sequence-decoding system has 500 time steps and 20 hidden states. Derive the asymptotic time and storage complexity of ordinary Viterbi decoding, and explain how storage changes if only the final score is required.
3. Critically assess whether a workforce-scheduling DP remains valid if employee fatigue depends on the complete history of assignments rather than a bounded summary. Propose a revised state representation or explain why approximation may be necessary.

Multiple Choice Questions with Answers

Question 1

Which property means that an optimal solution contains optimal solutions to its subproblems?

A. Greedy-choice property

B. Optimal substructure

C. Random access

D. Amortized optimality

Correct Answer: B. Optimal substructure

Question 2

What is the time complexity of the standard LCS dynamic-programming algorithm for sequences of lengths m and n?

A. O(m + n)

B. O(m log n)

C. O(mn)

D. O(2^(m+n))

Correct Answer: C. O(mn)

Question 3

Why is the capacity loop usually processed from W downward in one-dimensional 0/1 knapsack DP?

A. To sort items by value

B. To prevent an item from being reused in the same iteration

C. To guarantee fractional selection

D. To reduce the number of items

Correct Answer: B. To prevent an item from being reused in the same iteration

Question 4

For a DAG with V vertices and E edges, shortest paths using topological-order relaxation take what time?

A. O(V + E)

B. O(VE)

C. O(V²E)

D. O(2^V)

Correct Answer: A. O(V + E)

Question 5

In a hidden Markov model, the Viterbi algorithm computes which quantity?

A. The marginal probability of every observation independently

B. The most probable hidden-state sequence

C. The shortest graph cycle

D. The number of model parameters

Correct Answer: B. The most probable hidden-state sequence

Question 6

A knapsack has capacity 7. Items have (weight, value): (2,3), (3,4), (4,5), and (5,7). What is the maximum value in the 0/1 version?

A. 7

B. 9

C. 10

D. 12

Correct Answer: C. 10

Question 7

What is the base condition for matrix-chain multiplication when the interval contains one matrix Aᵢ?

A. M(i,i) = 1

B. M(i,i) = pᵢ

C. M(i,i) = 0

D. M(i,i) = ∞

Correct Answer: C. M(i,i) = 0

Question 8

If a DP has |S| states and at most d constant-time transitions per state, what is its typical time complexity?

A. O(|S| + d)

B. O(|S|d)

C. O(d^|S|)

D. O(|S|/d)

Correct Answer: B. O(|S|d)

Question 9

For Viterbi decoding with T time steps and K hidden states, the ordinary transition computation requires what time complexity?

A. O(TK)

B. O(K²)

C. O(TK²)

D. O(2^K)

Correct Answer: C. O(TK²)

Question 10

What is the principal danger of omitting a variable that affects future feasibility from a DP state?

A. The table becomes automatically sorted

B. The Markov assumption and recurrence may become invalid

C. The algorithm always becomes polynomial

D. Backpointers become unnecessary

Correct Answer: B. The Markov assumption and recurrence may become invalid