Dynamic Programming — Mathematics Knowledge System

Overview

Dynamic programming (DP) is an optimisation paradigm that decomposes multi-stage decision problems into simpler subproblems, storing their solutions to avoid redundant computation. It applies whenever a problem has optimal substructure (optimal solutions contain optimal sub-solutions) and overlapping subproblems (the same subproblems recur). DP solves problems in discrete (sequence alignment, shortest path, knapsack) and continuous (Bellman's optimality equation in control theory) settings.

Intuition

Dynamic programming is about 'remembering answers to sub-questions.' If you solve the problem by recursion and notice you're solving the same sub-problem over and over, DP says: solve each sub-problem once, store the answer, and look it up whenever needed. The trick is identifying the right 'state' that captures all information needed to optimally extend partial solutions.

Formal Definition

Definition

A DP problem has: states s ∈ S, actions a ∈ A(s), a transition function, and a cost. Bellman's principle of optimality states that an optimal policy has the property that, at any intermediate state, the remaining decisions must also form an optimal policy for the remaining problem.

V^*(s) = \min_{a \in A(s)} \left\{ c(s,a) + V^*(s') \right\}

Bellman optimality equation (deterministic)

V^*(s) = \min_{a \in A(s)} \left\{ c(s,a) + \sum_{s'} P(s'|s,a) V^*(s') \right\}

Bellman equation (stochastic / MDP)

\text{OPT}(i, W) = \max\left(\text{OPT}(i-1, W),\; v_i + \text{OPT}(i-1, W-w_i)\right)

0-1 knapsack recurrence

Notation

Notation	Meaning
$V^*(s)$	Optimal value function at state s
$\text{OPT}(i, \cdot)$	Optimal value of subproblem involving first i items/stages
$P(s'\|s,a)$	Transition probability from state s to s' under action a
$c(s,a)$	Cost of taking action a in state s

Properties

Principle of optimality

\text{An optimal policy has the property that, whatever the initial state and decision, the remaining decisions must form an optimal policy with respect to the state resulting from the first decision}

Complexity saving

\text{DP solves problems with } |S| \cdot |A| \text{ state-action pairs in polynomial time instead of exponential exhaustive search}

Memoisation equivalence

\text{Top-down memoised recursion and bottom-up DP compute the same results with the same asymptotic complexity}

Worked Examples

1
Define OPT(n) = minimum coins to make n. Base case OPT(0) = 0.
$\text{OPT}(0) = 0$
2
Recurrence: OPT(n) = 1 + min(OPT(n-1), OPT(n-5), OPT(n-10)) for applicable denominations.
$\text{OPT}(n) = 1 + \min_{d \in \{1,5,10\}, d \le n} \text{OPT}(n-d)$
3
Build table: OPT(0..18). OPT(10)=1, OPT(15)=2, OPT(18)=OPT(8)+1=OPT(3)+1+1=4.
$\text{OPT}(18) = 4 \quad (10+5+1+1+1 \text{ — wait: } 10+5+3\cdot1 = 4 \text{ coins})$

✓ Answer

Minimum 4 coins: one 10, one 5, three 1s (wait — that's 5). Correct: 10+5+1+1+1 = 5 coins. With 10+8: OPT(8) = OPT(3)+1 = 4, so OPT(18) = 5. Optimal: 10,5,1,1,1 = 5 coins.

Practice Problems

Mediumfree response

State and solve the 0-1 knapsack problem for items (value,weight) = {(3,2),(4,3),(5,4)} with capacity W=6.

Common Mistakes

Common Mistake

Confusing dynamic programming with divide-and-conquer

Both decompose problems, but divide-and-conquer subproblems are independent (no overlap), while DP subproblems overlap and share solutions. Mergesort is D&C; matrix chain multiplication is DP.

Common Mistake

Assuming DP always runs in polynomial time

DP's complexity depends on the number of distinct states. For the knapsack problem with capacity W, the table has O(nW) entries — pseudo-polynomial in the capacity W, not truly polynomial.

Quiz

Dynamic programming applies when a problem has:

A greedy-choice property and optimal substructureOptimal substructure and overlapping subproblemsA convex objective and linear constraintsA unique optimal solution

Historical Background

Richard Bellman introduced dynamic programming in 1953 at the RAND Corporation to analyse optimal sequential decision processes, coining the term to avoid the word 'mathematical' (which he thought the US Secretary of Defense would dislike). His Bellman equation — a functional equation for the optimal value function — also underpins continuous-time optimal control and reinforcement learning.

1953
Bellman introduces dynamic programming and the principle of optimality
Richard Bellman
1957
Bellman's book 'Dynamic Programming' published by Princeton University Press
Richard Bellman
1965
Pontryagin's maximum principle connects DP to continuous optimal control
Lev Pontryagin

Summary

Dynamic programming solves optimisation problems with optimal substructure and overlapping subproblems.
Bellman's principle: the optimal continuation from any intermediate state is independent of how that state was reached.
Implementation: bottom-up (fill table iteratively) or top-down (recursion with memoisation).
Applications: shortest paths (Bellman-Ford, Floyd-Warshall), sequence alignment, knapsack, reinforcement learning.

References

BookBellman, R. — Dynamic Programming (1957), Princeton University Press
WebsiteWikipedia — Dynamic programming
WebsiteMathWorld — Dynamic Programming