Handbooks / Data Structures & Algorithms / Chapter 5

Dynamic Programming and Greedy

7 pages · ~5 min✓ Reviewed

Builds on Trees and Graphs.

Data Structures & AlgorithmsPage 1

Recursion and the DP Mental Model

1. Recursion

Recursion = base case + recursive case that shrinks the problem
Missing or unreachable base case → stack overflow
Each call gets its own stack frame; depth n costs O(n) space
Python's default limit is ~1000 frames, then RecursionError

2. When DP Applies

Overlapping subproblems: the same state is needed again and again
Optimal substructure: the best answer is built from best sub-answers
Both must hold, otherwise DP is the wrong tool

	Naive fib	DP fib
Recurrence	`fib(n-1) + fib(n-2)`	same recurrence
Time	O(2^n)	O(n)
Why	same subproblems recomputed	each state solved once

3. The DP Recipe

Statewhat dp[i] means
Recurrencefrom smaller states
Base casessmallest states
Orderdeps first
Answerread off dp

Remember

Recompute the same state twice? Cache it. Define the state first; the recurrence follows from it.

Data Structures & AlgorithmsPage 2

Memoization vs Tabulation

1. Two Ways to Fill the Table

Memoization = top-down: recursion + cache keyed by state (dict or @lru_cache)
Tabulation = bottom-up: fill a table in a loop from the base cases
Same time for both: states × work per transition

	Memoization	Tabulation
Computes	only reached states	every state
Stack	recursion depth risk	none

python

@lru_cache(None)
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

memo: cache key is n

2. Save Space and Choose

Rolling array: keep only what the next step reads
fib needs two variables; a 2D table reading the previous row needs one row

python

a, b = 0, 1
for _ in range(n):
    a, b = b, a + b

tabulation, O(1) space: a is fib(n)

Pick memo: few states reachable or awkward order
Pick tabulation: deep recursion or space optimization matters

Mutable cache key

A list argument is unhashable, so the cache fails. Pass a tuple or an index instead.

Data Structures & AlgorithmsPage 3

Knapsack, Coin Change and Grid Paths

1. Knapsack: 0/1 vs Unbounded

dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])
O(nW) time
1D version: loop w downward, so an item is not reused

Variant	Items	Loop over w
0/1 knapsack	once	downward
Unbounded, coin change	may repeat	upward

2. Coin Change

Min coins: dp[a] = min(dp[a-c] + 1), dp[0]=0, rest start at infinity
Unreachable stays infinity, so return -1
Count ways: coins outer, amounts inner gives combinations; swap the loops for permutations

python

def fewest(coins, amount):
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a-c] + 1)
    return -1 if dp[amount] == float('inf') else dp[amount]
print(fewest([1, 3, 4], 6), fewest([5], 3))

coins {1,3,4}, amount 6 is 3+3

output

2 -1

3. Grid Paths

dp[r][c] = dp[r-1][c] + dp[r][c-1]
First row and column: 1 up to the first obstacle, 0 from it onward
Obstacle cells = 0
O(mn) time, one row of space

Direction

An upward loop in 0/1 knapsack reuses an item.

Data Structures & AlgorithmsPage 4

LIS and LCS

1. LCS

State: dp[i][j] = LCS length of first i chars of a, first j of b
Match: dp[i-1][j-1] + 1
No match: max(dp[i-1][j], dp[i][j-1])
Time and space O(mn)

	Subsequence	Substring
Order kept	yes	yes
May skip chars	yes	no
`ace` in `abcde`	yes	no

2. LIS

O(n²): dp[i] = 1 + max(dp[j]) over j<i with a[j]<a[i]
Answer is max(dp), not dp[n-1]
O(n log n): keep a tails array, find the slot with bisect_left
bisect_right allows equal values (non-decreasing)

python

from bisect import bisect_left
tails = []
for x in [5, 6, 1]:
    i = bisect_left(tails, x)
    tails[i:i+1] = [x]
print(len(tails), tails)

output

2 [1, 6]

tails is not the LIS

Its length is the answer, but [1, 6] is not a subsequence of the input.

3. Interview Point

Why is LIS max(dp)? The best sequence can end at any index.
Subsequence vs substring? Subsequence may skip characters; substring is contiguous.
Why bisect_left? Equal values replace a tail, so the result stays strictly increasing.

Data Structures & AlgorithmsPage 5

Greedy and Backtracking

1. Greedy: When It Works

Takes the locally best choice and never revisits it
Correct only with the greedy-choice property
Usually proven by an exchange argument

Works	Greedy rule
Interval scheduling	sort by end time, take if free
Fractional knapsack	sort by value/weight
Huffman coding	merge the two rarest symbols

Coins {1,3,4}, amount 6: greedy 4+1+1 = 3 coins
Optimum is 3+3 = 2 coins
0/1 knapsack needs DP

2. Backtracking Template

Chooseappend to path
Recursego deeper
Un-choosepop
Leafsave a copy of path

python

def go(start):  # a is sorted
    res.append(path[:])  # copy
    for i in range(start, len(a)):
        if i > start and a[i] == a[i-1]: continue
        path.append(a[i])  # choose
        go(i + 1)  # recurse
        path.pop()  # un-choose

unique subsets

Used for subsets, permutations, N-Queens
Prune early: check constraints before recursing
Sort, then skip equal neighbours to avoid duplicates

Cost

Subsets O(2^n), permutations O(n!). Backtracking is exponential: if subproblems overlap, use DP instead.

Data Structures & AlgorithmsPage 6

DP and Greedy Cheat Sheet

1. Pick the pattern

Signal	Pattern
Choose or skip	Knapsack
Compare two sequences	LCS
Best ending at i	LIS
Reach target, repeats allowed	Coin change
Move right or down	Grid: edge 1 until first obstacle, 0 after

2. Loop direction and cost

0/1 knapsack 1D: w goes downward (item used once)
Unbounded and coin change: w goes upward (items repeat)

Problem	Time
fib memo	O(n)
knapsack	O(nW)
LCS	O(mn)
LIS	O(n log n)
coin change	O(amount × coins)

3. Decision order

Greedyfind a counterexample
DPsubproblems overlap
Backtrackingneed all solutions

4. Interview Point

Memo or tabulation? State? Top-down cache vs bottom-up table; state = the indices, e.g. (i, w)
Greedy on coins {1,3,4}, amount 6? Takes 4+1+1 = 3 coins; 3+3 = 2 is optimal
Duplicate subsets? Sort, then skip when i>start and a[i]==a[i-1]

Data Structures & AlgorithmsPage 7

Check yourself

Coins {1,3,4}, amount 6. Greedy takes the largest coin first. How many coins, and is that minimal?

4+1+1 is 3 coins
Not minimal: 3+3 is 2 coins
Greedy never revisits a choice

A 1D 0/1 knapsack loops for w in range(c, W+1). What breaks?

w goes upward, so one item can be used again
Loop w downward from W to c

Coins [1,2], amount 3, amounts in the outer loop and coins inner. What does the count give?

3, counting 1+1+1, 1+2 and 2+1 as ordered
Coins in the outer loop gives 2 combinations