Dynamic Programming

This lesson assumes you already know recursion and recurrence relations. Dynamic programming builds directly on those ideas, but adds state management and complexity counting.

What you should be comfortable with

1) Recursion basics

• •You can write a recursive function with a clear base case and recursive case.
• •You understand how recursion creates a call tree.

2) Big-O and state-space counting (lightweight)

• •You can estimate time by counting how many distinct subproblems exist, and how much work you do per subproblem.
• •You understand that recomputation in recursion can turn linear-looking recurrences into exponential time.

3) Arrays / maps / dictionaries

• •You can store values by index (arrays) or by key (hash maps).
• •You can initialize a table like dp[n+1] or dp[n+1][m+1].

4) Indexing and 2D tables

• •You can reason about dp[i] and dp[i][j], and iterate in nested loops.

Common DP edge cases to watch for (we will revisit these)

• •Top-down stack depth: deep recursion can overflow the call stack; bottom-up avoids this.
• •Integer overflow: Fibonacci-style growth can exceed 32-bit integers quickly.
• •Reconstruction: sometimes you need not just the optimal value but also the choices; you’ll use backpointers or re-run decisions.
• •State definition mistakes: the #1 cause of broken DP solutions is a state that doesn’t uniquely capture what matters.

If any of these feel shaky, you can still proceed, but expect to pause and practice implementing small DP tables carefully.

Dynamic programming is a technique for solving problems by:

1) Breaking the problem into subproblems

2) Ensuring each subproblem is solved once

3) Combining subproblem solutions to solve larger problems

DP is not “one algorithm.” It’s a pattern.

Why DP exists (motivation)

Many problems have a natural recursive definition. For example, Fibonacci numbers:

A direct recursive implementation mirrors the math, but it recomputes the same values repeatedly.

If you draw the recursion tree for $F(6)$, you’ll notice the same subcalls appear many times (like $F(3)$, $F(2)$). That repeated work is the key inefficiency.

Two properties that make DP work

1) Overlapping subproblems

The recursion generates the same subproblems again and again.

• •Example: Fibonacci repeatedly asks for $F(3)$.

2) Optimal substructure

An optimal solution to the whole problem can be formed from optimal solutions to its subproblems.

• •Example: shortest path in a DAG can be built from shortest paths to predecessors.

DP typically appears in optimization (min/max) problems, but it also applies to counting (number of ways), decision (is it possible?), and probability.

The key symbol: dp[state]

We store the answer to a subproblem in a table:

• •dp[state] = the computed result for that subproblem

The entire art of DP often reduces to: choose a good state and write a correct recurrence.

Two implementation styles

You should be able to do both. Real interviews and real systems often benefit from being fluent in switching between them.

DP begins with a precise question:

What information do I need to uniquely identify a subproblem?

That “information” is your state.

What makes a good state?

A good DP state is:

• •Minimal: includes only what affects future decisions
• •Unique: two different states must not represent the same subproblem
• •Composable: you can compute the state’s answer from smaller states

If your state is missing information, your recurrence will “pretend” two different situations are the same. That produces wrong answers.

State examples

Example A: Fibonacci

Subproblem: compute $F(n)$.

State: just $n$.

So dp[n] is enough.

Example B: Grid paths (count ways)

Subproblem: number of ways to reach cell $(i,j)$.

State: $(i,j)$.

So dp[i][j].

Example C: Knapsack

Subproblem: best value using first $i$ items with capacity $w$.

State: $(i,w)$.

So dp[i][w].

The “state-space counting” habit

Once you define state, you can estimate complexity by counting how many states exist.

• •If dp[n]: you have $n$ states → often $O(n)$ time if each is $O(1)$.
• •If dp[i][w] with $i \in [0..n]$ and $w \in [0..W]$: you have $(n+1)(W+1)$ states → often $O(nW)$ time.

This is essential: DP often replaces exponential recursion with polynomial-time via “compute each state once.”

A common pitfall: state that is too big

If you include unnecessary information in state, the number of states can explode.

Example: using the entire partial solution history as part of state makes DP infeasible.

Another pitfall: state that is too small

If you leave out necessary information, you merge distinct subproblems.

Example idea: Suppose a path problem where whether you can step on a cell depends on whether you already used a “skip” power-up. Then state must include usedSkip ∈ {0,1}; dp[i][j] alone is too small.

Practical guidance

When you’re stuck:

1) Write the recursive function signature you wish you had.

2) The arguments to that function are usually your state.

3) Then ask: can I memoize those arguments?

Once you have a state, you need a recurrence: how do you compute dp[state] from smaller states?

Why recurrence comes after state

If you don’t know what the subproblem is, you can’t correctly express how it relates to smaller subproblems.

Template for top-down DP

You write a recursive function solve(state):

1) If state is a base case, return base answer.

2) If answer is already memoized, return it.

3) Otherwise, compute answer by trying choices that reduce the problem.

4) Store in dp[state], return it.

Pseudo-pattern:

solve(state):
  if base(state): return baseValue
  if dp has state: return dp[state]
  ans = combine( solve(nextState1), solve(nextState2), ... )
  dp[state] = ans
  return ans

Example: Fibonacci with memoization

The recurrence is:

A memoized version computes each $F(k)$ once, turning exponential recursion into linear time.

Complexity:

• •States: $n+1$
• •Work per state: $O(1)$
• •Total time: $O(n)$
• •Space: $O(n)$ for dp, plus recursion stack up to $O(n)$

Edge case: stack depth

For large $n$ (like $10^6$), recursion may overflow. That’s a reason to prefer bottom-up.

Edge case: integer overflow

$F(n)$ grows roughly like $\varphi^n/\sqrt{5}$, so it exceeds 32-bit quickly (e.g., $F(47)$ > 2³¹−1). Use 64-bit (long long) or big integers, or compute modulo.

Memoization data structures

Memoization is conceptually simple, but it only works if your state uniquely identifies subproblems.

Bottom-up DP computes answers for small states first, then builds up to the target.

Why bottom-up exists

• •Avoid recursion stack limits
• •Often better constant factors
• •Naturally supports iterative reconstruction (when storing backpointers)

The key requirement: a valid evaluation order

Your recurrence defines dependencies. You must fill the table so that when computing dp[state], all required smaller states are already computed.

Example: Fibonacci bottom-up

We can compute:

• •dp[0]=0
• •dp[1]=1
• •for i=2..n: dp[i]=dp[i-1]+dp[i-2]

This order works because dp[i] depends only on earlier indices.

Example: grid paths ordering

If dp[i][j] depends on dp[i-1][j] and dp[i][j-1], then scanning rows top-to-bottom and columns left-to-right works.

Space optimization

Often you don’t need the whole table.

Fibonacci: O(1) space

Since dp[i] depends only on last two values:

• •Keep prev2 = dp[i-2], prev1 = dp[i-1].

General pattern

If state uses dimension i and only depends on i-1, you can compress:

• •from 2D dp[i][w] to 1D dp[w] (careful with iteration direction!)

Caution: iteration direction matters

For 0/1 knapsack, if you compress dp[i][w] → dp[w], you must iterate w descending to avoid reusing item i multiple times.

This is a classic DP bug: same recurrence, wrong loop order, wrong meaning.

DP isn’t just a coding trick; it’s a general method for sequential decision problems.

DP as “value of a state”

In many problems, dp[state] represents the best achievable value from that state onward.

That’s exactly the mindset used in Markov Decision Processes (MDPs): define a value function over states.

Bellman-style recurrence (intuition)

In optimization DP, a common form is:

or for maximizing rewards:

This is a Bellman equation idea: the value of a state equals the best immediate choice plus the value of the next state.

Why DP prerequisites matter for MDPs

MDPs generalize DP to settings with uncertainty and expectations. Instead of next(s,a) being a single next state, it’s a distribution, and you compute expected value:

If you understand:

• •defining a good state,
• •writing correct recurrences,
• •and computing them efficiently,

then Bellman equations feel like the same pattern, just with probabilities.

DP in practice: beyond toy problems

DP appears in:

• •sequence alignment (bioinformatics)
• •edit distance / diff tools
• •parsing (context-free grammars)
• •resource allocation and scheduling
• •shortest paths on structured graphs

The recurring workflow is:

1) model as states

2) define transitions/choices

3) compute values efficiently

4) optionally reconstruct the solution path