The Central Idea
Dynamic programming avoids solving the same smaller problem again and again.
The basic pattern is:
- identify the smaller subproblems;
- solve each distinct subproblem once;
- store its answer;
- reuse that answer whenever it is needed again.
The key resource is remembered intermediate information.
When Dynamic Programming Is Useful
Dynamic programming is especially useful when two structural properties appear:
- overlapping subproblems;
- optimal substructure.
These properties help distinguish dynamic programming from ordinary divide-and-conquer recursion.
Overlapping Subproblems
Subproblems overlap when the same smaller problem is encountered from several different larger problems.
If a recursive algorithm recomputes that smaller answer each time, work is duplicated.
Dynamic programming stores the result so later calls can reuse it.
Fibonacci as the Standard Example
The Fibonacci recurrence is
\[ F_0=0,\qquad F_1=1 \]and
\[ F_n=F_{n-1}+F_{n-2}. \]A direct recursive algorithm follows this definition naturally.
But many Fibonacci subproblems are recomputed repeatedly.
Repeated Work in Fibonacci Recursion
To compute \(F_5\), direct recursion asks for
\[ F_4 \]and
\[ F_3. \]But computing \(F_4\) itself also asks for
\[ F_3. \]The same subproblem has appeared more than once.
Store the Answer Once
Suppose we compute
\[ F_3=2. \]Instead of recomputing \(F_3\) later, store
\[ F_3\mapsto2. \]Every later request for \(F_3\) can then retrieve the stored value.
This simple idea can eliminate enormous amounts of repeated work.
Memoization
Memoization is a top-down dynamic-programming strategy.
It begins with the original problem and uses recursion.
Before solving a subproblem, the algorithm checks whether its result has already been stored.
If so, the stored answer is returned immediately.
Memoized Fibonacci
A memoized Fibonacci procedure follows this logic:
- If \(n=0\), return \(0\).
- If \(n=1\), return \(1\).
- If \(F_n\) is already stored, return it.
- Otherwise compute \(F_{n-1}+F_{n-2}\).
- Store the result as \(F_n\).
- Return the stored value.
Tabulation
Tabulation is a bottom-up dynamic-programming strategy.
Instead of starting with the largest problem, it begins with the smallest known states and fills a table in an order that makes later states computable.
For Fibonacci:
\[ F_0=0,\qquad F_1=1, \]then compute
\[ F_2,\ F_3,\ F_4,\ldots. \]Bottom-Up Fibonacci Table
Begin with
\[ F_0=0,\qquad F_1=1. \]Then
\[ F_2=F_1+F_0=1, \] \[ F_3=F_2+F_1=2, \] \[ F_4=F_3+F_2=3, \] \[ F_5=F_4+F_3=5. \]Each value is computed once.
Memoization and Tabulation Solve the Same Dependency Structure
Memoization and tabulation differ mainly in order of evaluation.
- Memoization: begin with the target and recursively request needed states.
- Tabulation: begin with base states and systematically build upward.
Both rely on storing previously computed results.
States
A dynamic-programming state represents one distinct subproblem.
Choosing the right state is one of the most important design decisions.
A state should contain enough information to determine the answer to the subproblem, but not unnecessary information that creates too many distinct cases.
State Parameters
A state may be identified by one parameter:
\[ D(n), \]or several parameters:
\[ D(i,j), \] \[ D(i,c), \]and so on.
Each parameter should encode a meaningful part of the remaining problem.
State Meaning Must Be Precise
Before writing a recurrence, define exactly what each state means.
For example:
\(D(i)\) is the minimum cost needed to reach position \(i\).
A precise state definition prevents ambiguity when constructing transitions and base cases.
Transitions
A transition explains how one state depends on earlier or smaller states.
For example,
\[ D(i)=\min\{D(i-1)+a_i,\ D(i-2)+b_i\} \]says that the best answer for state \(i\) comes from comparing two possible predecessor states.
Base States
Dynamic programming requires base states just as recursion requires base cases.
These are the smallest subproblems whose answers are known directly.
Every other state must ultimately depend on them through valid transitions.
Dependency Order
In tabulation, states must be computed in an order that respects dependencies.
If
\[ D(i) \]depends on
\[ D(i-1), \]then \(D(i-1)\) must be known before \(D(i)\) is evaluated.
The table order is therefore part of the algorithm.
Optimal Substructure
A problem has optimal substructure when an optimal solution to the whole problem can be built from optimal solutions to appropriate smaller subproblems.
This property allows a dynamic-programming recurrence to compare optimal subproblem values and construct an optimal larger value.
Optimization Recurrences
Many dynamic-programming recurrences use
\[ \min \]or
\[ \max \]because several possible previous decisions can lead to the same state.
The recurrence compares those alternatives and stores the best result.
A Minimum-Cost Path on a Line
Suppose positions
\[ 0,1,2,\ldots,n \]can be reached by moving one or two steps at a time.
Let \(c_i\) be the cost of landing on position \(i\).
Define
\[ D(i)=\text{minimum cost to reach position }i. \]Minimum-Cost Transition
To reach \(i\), the final move must come from either
\[ i-1 \]or
\[ i-2. \]Therefore,
\[ \boxed{D(i)=c_i+\min\{D(i-1),D(i-2)\}}. \]The recurrence examines all possible final moves.
Why the Recurrence Is Correct
Every valid path to \(i\) must end with one of the allowed predecessor positions.
If the best path to \(i\) came from \(i-1\), then using a nonoptimal path to \(i-1\) could be improved.
Therefore, an optimal path to \(i\) must contain an optimal path to its chosen predecessor.
Counting Problems Can Also Use Dynamic Programming
Dynamic programming is not limited to minimization and maximization.
It can also count the number of ways to reach states.
Suppose one may climb \(1\) or \(2\) steps at a time.
Let
\[ W(n)=\text{number of ways to reach step }n. \]Counting Staircase Paths
Any path to step \(n\) ends with either:
- a \(1\)-step move from \(n-1\);
- a \(2\)-step move from \(n-2\).
Therefore,
\[ \boxed{W(n)=W(n-1)+W(n-2)}. \]With suitable base states, the table can be filled from small \(n\) upward.
Dynamic Programming as a Directed Dependency Graph
States can be viewed as vertices in a directed graph.
Draw an edge
\[ A\to B \]when state \(B\) depends on state \(A\).
Tabulation computes states in an order consistent with this dependency structure.
Two-Dimensional Dynamic Programming
Some problems require states with two parameters.
For example,
\[ D(i,j) \]may describe a problem involving the first \(i\) objects and the first \(j\) positions, symbols, capacities, or choices.
The resulting table is often visualized as a grid.
Grid Path Example
Suppose movement in a grid is allowed only rightward or downward.
Let
\[ P(i,j) \]be the number of paths from the upper-left corner to cell \((i,j)\).
Every path into \((i,j)\) must arrive from either the cell above or the cell to the left.
Grid Path Recurrence
Therefore,
\[ \boxed{P(i,j)=P(i-1,j)+P(i,j-1)}. \]Boundary cells supply the base states.
The table can then be filled row by row or column by column.
Reconstructing an Optimal Solution
Sometimes the dynamic-programming table stores only the optimal value.
But a problem may also ask for the choices that produce that value.
To reconstruct the solution, store additional information such as:
- the chosen predecessor;
- the chosen item;
- the selected transition;
- a parent pointer.
Value Versus Decision
A state may store a number such as
\[ D(i)=17, \]but that alone may not tell us which earlier state produced \(17\).
If solution reconstruction matters, the algorithm should also remember the decision that achieved the optimum.
Space Optimization
A full table is not always necessary.
If
\[ D(i) \]depends only on
\[ D(i-1) \]and
\[ D(i-2), \]then only the last two values may be needed during computation.
This can reduce memory usage substantially.
When Full Storage Is Still Useful
Even when only a few recent values are needed to compute the final optimum, the full table may still be useful if we need:
- all intermediate answers;
- solution reconstruction;
- debugging information;
- later queries about earlier states.
Space optimization therefore depends on the output requirements.
Dynamic Programming Versus Divide and Conquer
Both methods break a problem into subproblems.
Divide-and-conquer is most natural when subproblems are largely independent.
Dynamic programming is especially useful when subproblems overlap and would otherwise be solved repeatedly.
Dynamic Programming Versus Greedy Methods
A greedy method commits to one locally attractive decision.
Dynamic programming generally compares several alternatives and records the best value for each state.
Greedy methods are often simpler, but dynamic programming can solve broader optimization problems when greedy-choice arguments do not apply.
Dynamic Programming Versus Backtracking
Backtracking explores alternative choices and may undo decisions.
Dynamic programming instead identifies repeated states and stores their answers.
A backtracking search may be improved by memoization when many different choice paths lead to the same remaining subproblem.
State Compression
Sometimes two different histories lead to exactly the same future possibilities.
If so, dynamic programming can represent both histories with one state.
This is powerful because the state records only information that matters for the future, not the entire path used to arrive there.
The Principle of Relevant History
A good state remembers enough of the past to determine future decisions, but forgets details that no longer matter.
This balance is central to efficient dynamic-programming design.
Too little information makes transitions incorrect.
Too much information creates unnecessarily many states.
Time Complexity from Number of States
A useful first estimate is:
\[ \text{time} \approx (\text{number of states}) \times (\text{work per state}). \]If there are \(n\) states and each takes constant work, total time is often proportional to
\[ n. \]Two-Dimensional Table Cost
If a dynamic-programming table has
\[ n \]rows and
\[ m \]columns, then it contains
\[ nm \]states.
If each state takes constant work, the total time is often proportional to
\[ nm. \]Top-Down Can Skip Unneeded States
Memoization computes only states that are actually requested by the recursion.
If many theoretically possible states are unreachable or irrelevant, this can save work.
Tabulation often fills a larger predefined region of the state space.
Bottom-Up Avoids Recursive Overhead
Tabulation does not require recursive calls.
This can simplify control flow and avoid call-stack overhead.
It also makes dependency order explicit.
The best choice between memoization and tabulation depends on the structure of the problem.
Dynamic-Programming Correctness
Correctness usually depends on showing:
- the state definition captures the intended subproblem;
- the base states are correct;
- the recurrence considers every valid way to enter or construct the current state;
- the recurrence chooses or combines those possibilities correctly;
- the evaluation order respects dependencies.
Why Missing a Transition Is Dangerous
Suppose an optimal state can be reached in three different structural ways, but the recurrence considers only two.
Then the true optimum may be excluded from the table.
Dynamic programming is correct only when the recurrence covers every relevant possibility.
Why Invalid Transitions Are Also Dangerous
A recurrence must not include impossible predecessor states or illegal decisions.
Including an invalid transition can produce a value that appears better than every valid solution but cannot actually be realized.
Feasibility remains part of the state transition logic.
Common Error: Using Dynamic Programming Without Overlap
If subproblems are completely independent and never repeated, storing every result may add complexity without providing much benefit.
In such cases, ordinary divide and conquer may be more natural.
Common Error: Poor State Definition
If the state omits information that affects future choices, two genuinely different subproblems may be treated as if they were identical.
The recurrence can then return incorrect answers.
Common Error: Storing Too Much State
At the other extreme, storing the entire history of every partial solution may create an enormous state space.
The goal is to retain only information needed to determine future behavior.
Common Error: Wrong Table Order
In bottom-up tabulation, computing a state before its dependencies are known produces undefined or incomplete values.
The fill order must respect the recurrence.
Common Error: Forgetting Base States
A recurrence cannot start itself.
Base states anchor the table and give the first known values from which later states are computed.
Common Error: Confusing the Table with the Problem
The table is only a storage mechanism.
The real design work lies in:
- defining the state;
- finding the recurrence;
- establishing base states;
- choosing a valid evaluation order.
Common Error: Returning Only the Optimal Value When the Path Is Required
A dynamic-programming computation may correctly find the best score while losing the choices that produced it.
If the problem asks for the actual solution, store predecessor or decision information during the computation.
A Reliable Procedure for Designing Dynamic Programming
- Define the full problem precisely.
- Identify smaller subproblems that recur.
- Define a state using only information relevant to the future.
- State exactly what the value of each state means.
- Identify the base states.
- List all valid transitions into each state.
- Write a recurrence that combines those transitions.
- Choose memoization or tabulation.
- Choose an evaluation order that respects dependencies.
- Store reconstruction information if the actual choices are required.
- Count the states and estimate work per state.
Example: Staircase Counting
Suppose a person may climb \(1\) or \(2\) steps at a time.
Let
\[ W(0)=1 \]represent one way to remain at the starting position, and let
\[ W(1)=1. \]Then
\[ W(n)=W(n-1)+W(n-2). \]Tabulating the Staircase Example
Compute:
\[ W(0)=1, \] \[ W(1)=1, \] \[ W(2)=2, \] \[ W(3)=3, \] \[ W(4)=5, \] \[ \boxed{W(5)=8}. \]Example: Minimum Cost
Suppose landing costs are
\[ c_0=0,\quad c_1=4,\quad c_2=2,\quad c_3=7,\quad c_4=1. \]A move may advance one or two positions.
Let
\[ D(i)=\text{minimum cost to reach }i. \]Computing the Minimum-Cost Table
Use
\[ D(i)=c_i+\min\{D(i-1),D(i-2)\}. \]With
\[ D(0)=0,\qquad D(1)=4, \]we obtain
\[ D(2)=2+\min\{4,0\}=2, \] \[ D(3)=7+\min\{2,4\}=9, \] \[ D(4)=1+\min\{9,2\}=3. \]Therefore,
\[ \boxed{D(4)=3}. \]Practice 1: Identify the Dynamic-Programming Signal
What property of naive Fibonacci recursion suggests that dynamic programming may help?
Practice 2: Memoization
In a memoized algorithm, what should happen when the requested state has already been computed?
Practice 3: Tabulation
Using
\[ F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}, \]tabulate through \(F_6\).
Practice 4: State Meaning
Why should the meaning of a state such as \(D(i)\) be stated explicitly before writing the recurrence?
Practice 5: Staircase Counting
If
\[ W(0)=1,\qquad W(1)=1,\qquad W(n)=W(n-1)+W(n-2), \]compute \(W(6)\).
Practice 6: Dependency Order
If
\[ D(i) \]depends on \(D(i-1)\) and \(D(i-2)\), why should a bottom-up table usually be filled in increasing order of \(i\)?
Practice 7: Space Optimization
If each state depends only on the previous two states and only the final value is needed, how much of the table must be retained at once?
Practice 8: Overlap Versus Independence
What is the main structural difference between a typical dynamic-programming problem and a clean divide-and-conquer problem?
Practice 9: Reconstructing a Solution
What additional information can be stored if the problem asks for the actual sequence of decisions, not merely the optimal value?
Practice 10: Count the States
A dynamic-programming table has \(20\) rows and \(15\) columns.
How many states does the table contain?
Practice Answers
Practice 1
The same Fibonacci subproblems are computed repeatedly.
This
\[ \boxed{\text{overlap among subproblems}} \]is the main signal.
Practice 2
Return the stored answer immediately rather than recomputing the state.
Practice 3
\[ F_0=0, \] \[ F_1=1, \] \[ F_2=1, \] \[ F_3=2, \] \[ F_4=3, \] \[ F_5=5, \] \[ \boxed{F_6=8}. \]Practice 4
The state meaning determines what information the recurrence must compute and what predecessor states are valid. Without a precise definition, the recurrence can become ambiguous or incorrect.
Practice 5
\[ W(2)=2, \] \[ W(3)=3, \] \[ W(4)=5, \] \[ W(5)=8, \] \[ \boxed{W(6)=13}. \]Practice 6
Increasing order ensures that \(D(i-1)\) and \(D(i-2)\) have already been computed before \(D(i)\) is evaluated.
Practice 7
Only the two most recent states need to be retained, along with temporary storage for the new value.
Practice 8
Dynamic-programming subproblems often overlap, so the same states recur. Clean divide-and-conquer subproblems are typically more independent.
Practice 9
Store a predecessor, parent pointer, selected transition, or other record of the decision that produced each state's value.
Practice 10
\[ 20\cdot15=\boxed{300}. \]What to Remember
- Dynamic programming solves each distinct subproblem once and reuses its result.
- Overlapping subproblems and optimal substructure are central signals.
- Memoization is top-down; tabulation is bottom-up.
- A state must represent one precise subproblem.
- Transitions describe how states depend on smaller or earlier states.
- Base states anchor the computation.
- Bottom-up evaluation order must respect dependencies.
- Optimal-solution reconstruction may require storing predecessor decisions.
- Time is often estimated from the number of states times the work per state.
The most important habit is to ask: What information completely describes the remaining subproblem, and how can I avoid solving that same state twice?
Where We Go Next
Dynamic programming stores and reuses answers to repeated subproblems. Another important strategy explores possible decisions directly, reversing choices when they lead to dead ends.
The next lesson, Backtracking, develops decision trees, partial solutions, constraint checks, pruning, undoing choices, and systematic exploration of finite search spaces.