Dynamic Programming

📋 Quick Reference

Property	Value
Type	Optimization technique
Key Idea	Break into subproblems, store results, avoid recomputation
Requirements	Optimal substructure + overlapping subproblems
Approaches	Top-down (memoization) or Bottom-up (tabulation)
Best For	Optimization problems, counting problems

One-liner: Solve complex problems by breaking into overlapping subproblems and caching results.

🎮 Interactive Visualizer

Watch how DP builds solutions from smaller subproblems:

0/1 Knapsack (Dynamic Programming)
Time: O(nW)Space: O(nW)
1 / 34
Initialize DP table: 5 rows (items) × 9 cols (capacity). Base case: dp[0][*] = 0
DP problems:Knapsack, LCS, edit distance, coin change, shortest paths
Key insight:Optimal substructure + overlapping subproblems = memoize!
DP Recurrence Formula
dp[i][w] = max( skip, take)
skip = dp[i-1][w]Don't take item i
take = dp[i-1][w-weight] + valueTake item i
Current cell calculation will appear here...
Items (i = item index):
i=1: w=2, v=3
i=2: w=3, v=4
i=3: w=4, v=5
i=4: w=5, v=6
Max Capacity: 8
DP Table (w = current capacity):
i\w 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
Pseudocode
1for i = 1 to n:
2  for w = 1 to capacity:
3    if item[i].weight > w:
4      dp[i][w] = dp[i-1][w]
5    else:
6      skip = dp[i-1][w]
7      take = dp[i-1][w-weight] + value
8      dp[i][w] = max(skip, take)
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Not computed
Not computed
Computed
Computed
Take item
Take item
Skip item
Skip item
P · [ ] · R
Loading visualizer...

i\w	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0	0

Try these operations:

See Fibonacci with memoization - avoid redundant calls
Watch the DP table fill for knapsack
Observe how subproblems build on each other
Compare top-down vs bottom-up approaches

🔧 Classic Problems

Fibonacci (Top-Down with Memoization)

JAVA(12 lines)
Code
Loading syntax highlighter...

Fibonacci (Bottom-Up with Tabulation)

JAVA(27 lines)
Code
Loading syntax highlighter...

0/1 Knapsack

JAVA(19 lines)
Code
Loading syntax highlighter...

Longest Common Subsequence (LCS)

JAVA(16 lines)
Code
Loading syntax highlighter...

Coin Change (Minimum Coins)

JAVA(15 lines)
Code
Loading syntax highlighter...

📊 DP Patterns

Pattern 1: Linear DP

JAVA(13 lines)
Code
Loading syntax highlighter...

Pattern 2: 2D Grid DP

JAVA(18 lines)
Code
Loading syntax highlighter...

Pattern 3: String DP

JAVA(24 lines)
Code
Loading syntax highlighter...

Pattern 4: Interval DP

JAVA(23 lines)
Code
Loading syntax highlighter...

✅ When to Use DP

Good Indicators

"Minimum/maximum" - optimization problem
"Count the ways" - counting problem
"Can it be done?" - feasibility problem
Overlapping subproblems - same states computed repeatedly
Optimal substructure - optimal solution uses optimal sub-solutions

Common DP Problems

Category	Examples
Sequence	Fibonacci, Climbing Stairs, LIS
Grid	Unique Paths, Minimum Path Sum
String	LCS, Edit Distance, Palindrome
Knapsack	0/1 Knapsack, Coin Change
Interval	Matrix Chain, Burst Balloons
Tree	Tree DP, Binary Tree Maximum Path

🔄 Top-Down vs Bottom-Up

Aspect	Top-Down (Memoization)	Bottom-Up (Tabulation)
Direction	Start from problem, recurse	Start from base cases
Computation	Only needed subproblems	All subproblems
Stack	Recursion overhead	Iterative
Debugging	Easier to understand	Easier to trace
Space Optimization	Harder	Often possible

JAVA(16 lines)
Code
Loading syntax highlighter...

⚠️ Common Pitfalls

1. Wrong Base Case

JAVA(10 lines)
Code
Loading syntax highlighter...

2. Wrong Recurrence Relation

JAVA(5 lines)
Code
Loading syntax highlighter...

3. Index Out of Bounds

JAVA(5 lines)
Code
Loading syntax highlighter...

4. Not Recognizing DP Problem

JAVA(6 lines)
Code
Loading syntax highlighter...

🎤 Interview Tips

Q: How do you identify a DP problem?

"

Look for optimization/counting problems with overlapping subproblems. If you see the same recursive calls being made, it's likely DP. Common patterns: "minimum/maximum", "count ways", "is it possible".

Q: Top-down or bottom-up?

"

Top-down is often easier to derive (just add memoization to recursion). Bottom-up can be more efficient (no recursion overhead) and easier to optimize space. Start with top-down, convert to bottom-up if needed.

Q: How do you derive the recurrence?

"

Think about the last decision/step. What choices lead to the current state? Express the answer in terms of smaller subproblems. Draw decision trees if stuck.

Q: How do you optimize DP space?

"

If dp[i] only depends on dp[i-1] and dp[i-2], you only need two variables, not an array. For 2D DP, if you only look at the previous row, use a 1D array.

Previous: Part 12: Dijkstra's Algorithm

Next: Part 14: ConcurrentHashMap

Visualizer: DP from @tomaszjarosz/react-visualizers