Dynamic Programming — Optimal Substructure, Overlapping Subproblems, When to Apply

Dynamic programming breaks a problem into smaller subproblems, stores their answers, and reuses them to avoid recomputation.

Two prerequisites

1. Optimal substructure

• Optimal solution to the big problem = combine optimal solutions of subproblems
• Example (works): shortest path from A to C through B = shortest A→B + shortest B→C
• Counter-example: longest simple path in a graph — paths can't share nodes, so subproblems aren't independent

2. Overlapping subproblems

• Naive recursion solves the same subproblem multiple times
• Example: Fibonacci — fib(5) needs fib(3) twice
• Counter-example: merge sort divides into non-overlapping halves — nothing to memoize, that's divide and conquer

Both must hold for DP to be useful.

The transformation

• Naive Fibonacci: O(2^n) time — exponential
• Memoized Fibonacci: O(n) time — each subproblem solved once
• General formula: time = (unique subproblems) × (work per subproblem)

How to recognize DP problems

Optimization

• 'Find the minimum/maximum ...'
• 'Find the longest/shortest ...'

Counting

• 'Count the number of ways to ...'
• 'In how many ways can ...?'

Decision

• 'Is it possible to ...?'
• 'Can you partition ...?'

Constraints (often state dimensions)

• 'with at most K ...'
• 'within budget/capacity ...'

Structure

• subsequence, palindrome, path in grid, knapsack, partition

Test: if you can write brute-force recursion that branches exponentially AND takes a small argument set, DP probably applies.

The state-and-transition framework

State = smallest set of variables identifying a subproblem

• Fibonacci: (n)
• LCS: (i, j) = LCS of prefixes A[0..i], B[0..j]
• Knapsack: (item_idx, capacity_left)
• Edit distance: (i, j) = edits A[0..i] → B[0..j]
• TSP: (current_city, visited_bitmask)

Transition = recurrence relating dp[state] to smaller states

• Fibonacci: dp[n] = dp[n-1] + dp[n-2]
• LCS: if match dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1])
• Knapsack: max(skip, take + value)

Base cases = smallest subproblems with obvious answers.

Time = states × work per state. Space = states (often reducible via rolling arrays).

DP categories

Linear DP (1D state)

• Fibonacci, climbing stairs, house robber

Grid DP (2D state on a matrix)

• Unique paths, min path sum

Subsequence DP (string DP)

• LCS, LIS, edit distance

Subset/Knapsack DP (binary choice per item)

• 0/1 knapsack, subset sum, partition

Interval DP (state on range [i, j])

• Matrix chain multiplication, palindromic partitioning

Tree DP (state on tree nodes)

• Max path sum in tree, robbery in tree

Bitmask DP (state includes a small set as bitmask)

• TSP, set cover (n ≤ 20)

Digit DP (state on positions of decimal digits)

• Count numbers with property in [L, R]

DP vs other techniques

Brute force

• All possibilities, exponential
• Only for tiny n

Divide and conquer

• Independent (non-overlapping) subproblems
• Master theorem; often O(n log n)
• Merge sort, FFT

Greedy

• Local best choice = global optimum
• Simpler than DP when applicable
• Hard part: proving optimality
• Activity selection, Dijkstra, Kruskal

DP

• Optimal substructure + overlap
• More design effort but reliable
• Use when greedy fails

Decision tree

1. 1
   Greedy works? → greedy
2. 2
   Independent subproblems? → divide and conquer
3. 3
   Both DP prereqs hold? → DP
4. 4
   Tiny n, no structure? → brute force / bitmask
5. 5
   Huge n, no DP structure? → approximation / ML

Common pitfalls

• Confusing DP with divide and conquer (D&C lacks overlap)
• Trying DP on longest simple path (no optimal substructure)
• Wrong state design (missing a dimension)
• Off-by-one in indexing
• Wrong base case
• Treating DP as one algorithm instead of a design strategy
• Greedy that 'looks right' but fails on edge cases (coin change with arbitrary denominations)

Recommendation: Master the two prerequisites — optimal substructure and overlapping subproblems — because if either is missing, DP either doesn't apply or gives no speedup. The hardest part of DP isn't the implementation; it's identifying the state — the smallest set of variables that uniquely characterizes a subproblem — and the transition — the recurrence relating that state to smaller ones. Train on the classic categories (linear, grid, subsequence, knapsack, interval, tree, bitmask) so you instantly recognize patterns. Use keyword cues in problem statements: 'min/max/longest/shortest', 'count the number of ways', 'is it possible', 'with at most K' — these almost always signal DP. Time complexity is just states × work-per-state, so the moment you've nailed the state, you know whether your solution will be fast enough. Always try greedy first if it has a clean argument (e.g., exchange argument); fall back to DP when greedy demonstrably fails. For tiny n (≤ 20), bitmask DP makes 2^n state spaces tractable. Don't confuse DP with divide and conquer — D&C has independent subproblems (merge sort), DP has overlapping ones (Fibonacci). Don't confuse it with greedy — greedy commits to one local choice, DP explores all and picks the best. The mental model: DP = explore all paths in a DAG of subproblems, store each node's answer once, combine via recurrence. Once you internalize state-and-transition thinking, every DP problem becomes the same template with different state variables.