learningto/pass

Dynamic Programming

ExpertAlgorithms

DP is the hardest category but appears in ~30% of Google hard problems. The key insight: optimal substructure + overlapping subproblems. Master the pattern recognition across 1D, 2D, and interval DP.

AVG TIME
O(n^2)
SPACE
O(n)
BEST
O(n)
WORST
O(n^2)

Step-by-Step Walkthrough

step-by-step walkthrough

Dynamic Programming - Climbing Stairs

1 / 6
algorithm.py
1def climb_stairs(n):
2 # DP approach: build up from base cases
3 if n <= 2:
4 return n
5
6 dp = [0] * (n + 1)
7 dp[1] = 1 # 1 way to reach step 1
8 dp[2] = 2 # 2 ways to reach step 2
9
10 for i in range(3, n + 1):
11 dp[i] = dp[i-1] + dp[i-2]
12
13 return dp[n]
visualization
dp table (ways to reach each stair)
0
0
0
1
0
2
0
3
0
4
0
5
variable inspectorBuilding DP table...
n=5
dp=[]
The Problem
You're climbing stairs. Each step you can go 1 stair or 2 stairs. How many different ways can you reach stair N? For N=5: there are 8 ways. Let's find a pattern by solving smaller cases first.
speedmed
← →space

In Python

Concept to Code- 2 structures for this topic
declare
nums = [1, 2, 3]
common ops
nums.append(x)
O(1)
nums.pop()
O(1)
nums[i]
O(1)
nums.insert(i, x)
O(n)
x in nums
O(n)
nums.sort()
O(n log n)
len(nums)
O(1)
say in interview
"I'll use an array to store the elements"
Python lists ARE dynamic arrays (like ArrayList in Java), NOT linked lists. Access by index is O(1).

Math You Need For This

A crossword grid. You fill in cells from the top-left. Each cell's answer depends on its neighbors to the top and left (already filled). The final answer is in the bottom-right corner. Fill time = number of cells = n×m.

Required concepts
Key math ideas
1 / 3

Exponents - doubling chains

2ⁿ means you start with 1 and double it n times. n=10 gives you 1,024. n=20 gives you 1,048,576. n=30 gives you over a billion. It grows terrifyingly fast.

Step 0: 2^0 =
1

Think of it this way: A chain letter. You send it to 2 friends. Each of them sends it to 2 friends. After 30 rounds, over a billion letters have been sent.

For algorithms: Brute-force recursive solutions that branch into 2 sub-problems at every step hit O(2ⁿ). That is why memoization and dynamic programming matter so much.

Interactive 3D Visualization

Array
Access: O(1)Search: O(n)Space: O(n)
Drag to orbit - Scroll to zoom

Brute Force vs Optimized

Interview Strategy - Fibonacci / Climbing Stairs

Start brute force, explain it, THEN optimize. "I can see a straightforward approach. Let me start there, then we can optimize."

Brute Force
Naive Recursion
TimeO(2^n)
SpaceO(n)

"Recursively compute fib(n-1) + fib(n-2). Recomputes the same values over and over."

Pros
  • +Directly mirrors the mathematical definition
  • +Easy to write
Cons
  • -Exponentially slow - fib(40) takes over a billion calls
  • -Massive duplicated work
Optimized
Bottom-Up DP (Tabulation)
TimeO(n)
SpaceO(1)

"Build answer from the bottom. Only need the last two values at each step."

Pros
  • +Linear time
  • +Constant space with the two-variable trick
  • +No recursion overhead
Cons
  • -Less intuitive than recursion for some people
The Tradeoff

From O(2^n) to O(n) - exponential to linear. For n=40: recursion makes 1,073,741,824 calls. DP does 40 iterations. This is the biggest speedup you will ever see.

For n=40
Brute Force1,073,741,824 ops
Optimized40 ops
Say This

Say: "The recursive solution has overlapping subproblems - fib(3) gets computed many times. By storing results bottom-up, we eliminate all duplicate work."

Python Implementation

example.py
Loading...
Now try it yourself
2 challenges with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Dynamic Programming into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: BFS & DFS
Dynamic Programming
Next: BFS & DFS