Dynamic Programming = Recursion + Memoization. Use it when subproblems repeat (overlap) and the global optimum can be built from optimal sub-solutions (optimal substructure).

Core Properties

Optimal substructure: an optimal answer contains optimal answers to subproblems.
Overlapping subproblems: the recursion tree re-computes the same cases.

Two Approaches

Top-down (Memoization): keep recursion, cache results.
Bottom-up (Tabulation): fill a table iterating in dependency order.

Example: Fibonacci

Naive recursion is exponential. DP reduces it to linear time.

Top-Down with Memoization

Pseudocode

1function fib(n):
2  if n <= 1: return n
3  if memo[n] exists: return memo[n]
4  memo[n] = fib(n-1) + fib(n-2)
5  return memo[n]

See DP Tables Build Up (LCS)

Visualize how a 2D DP fills cell-by-cell with the LCS of “ABCBDAB” and “BDCABA”.

AB Show traceback

LCS Table Builder

Speed

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0

Step 1 / 42 (i=1, j=1). No match: take max(top, left).

DP Problem Checklist

Define state (what does dp[i][j] represent?).
Identify transitions (recurrence).
Establish base cases.
Choose memoization or tabulation.
Consider space optimization.
Prove correctness and analyze complexity.

Strategies: Memoization & Tabulation

DP in One Line

Dynamic Programming = Recursion + Memoization. Use it when subproblems repeat (overlap) and the global optimum can be built from optimal sub-solutions (optimal substructure).

Core Properties

Optimal substructure: an optimal answer contains optimal answers to subproblems.
Overlapping subproblems: the recursion tree re-computes the same cases.

Two Approaches

Top-down (Memoization): keep recursion, cache results.
Bottom-up (Tabulation): fill a table iterating in dependency order.

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0