Dynamic Programming Fundamentals
You know recursion. Now see how memoization and tabulation turn exponential solutions into polynomial ones.
Lessons
1. Intro
The power of optimization
2. LeetCode 509 Fibonacci - Problem Statement
LC 509 classic
3. LeetCode 509 Fibonacci - Base Cases
Two starting points
4. LeetCode 509 Fibonacci - Recursive Formula
Two calls
5. LeetCode 509 Fibonacci - Naive Implementation
Direct translation
6. Visualization - Fibonacci Tree
Explosion of calls
7. Vocabulary - Overlapping Subproblems
Same work repeated
8. Time Complexity - Exponential Growth
O(2^n) disaster
9. The Main Idea
Remember results
10. Socratic Checkpoint
Test your understanding
11. Recursion to DP
The bridge
12. What Is Memoization?
Caching results
13. Vocabulary - Top-Down DP
Starting from the top
14. LeetCode 509 Fibonacci - Memoization Setup
Adding memory
15. LeetCode 509 Fibonacci - Memoized Code
Three extra lines
16. Memoization - Time Complexity
O(n) now!
17. Memoization - Space Complexity
O(n) cost
18. LeetCode 70 Climbing Stairs - Problem Statement
LC 70 Fibonacci disguise
19. LeetCode 70 Climbing Stairs - Recursive Intuition
DP basics
20. LeetCode 70 Climbing Stairs - Memoized Solution
Apply the pattern
21. LeetCode 70 Climbing Stairs - Implementation
The code
22. Quiz: Memoization Complexity
Knowledge check
23. Lessons from Memoization
Pattern recap
24. What Is Tabulation?
Building from ground up
25. Vocabulary - Bottom-Up DP
Why called bottom-up
26. LeetCode 509 Fibonacci - Tabulation Implementation
Iterative solution
27. Space Optimization
Only keep what you need
28. LeetCode 509 Fibonacci - O(1) Space
Most efficient
29. Top-Down vs Bottom-Up
When to use each
30. LeetCode 746 Min Cost Climbing Stairs - Problem Statement
Your first cost problem
31. LeetCode 746 Min Cost Climbing Stairs - State Definition
What dp[i] means
32. LeetCode 746 Min Cost Climbing Stairs - Transition
Choose cheaper path
33. LeetCode 746 Min Cost Climbing Stairs - Implementation
Full solution
34. LeetCode 152 Maximum Product Subarray - Problem Statement
Read the problem
35. LeetCode 152 Maximum Product Subarray - Why It's Tricky
Negative numbers twist
36. LeetCode 152 Maximum Product Subarray - Tracking Two States
Track min and max
37. LeetCode 152 Maximum Product Subarray - Implementation
Full solution
38. Quiz: Simple DP Patterns
Knowledge check
39. LeetCode 91 Decode Ways - Problem Statement
LeetCode 91
40. LeetCode 91 Decode Ways - The Choices
One or two digits
41. LeetCode 91 Decode Ways - Edge Cases
Leading zeros
42. LeetCode 91 Decode Ways - State Definition
Ways to decode
43. LeetCode 91 Decode Ways - Transition
Two choices
44. LeetCode 91 Decode Ways - Implementation
The code
45. Section Recap
What we learned
Practice Problems
Show how memoization reduces execution time by preventing recalculation.
Shows how Fibonacci patterns extend to any recurrence with more terms
The perfect first DP problem - simple state, clear transitions, builds intuition for optimal substructure.
Digit manipulation with greedy DP approach - bridges greedy and DP
Classic digit DP that naturally shows overlapping subproblems
Variable jumps and memoization combine to show how pruning works
Unbounded coins hit the same subproblems repeatedly, making memoization essential
Teaches cost optimization in climbing stairs pattern with choice
Naive recursion times out, but adding one memo layer makes it instant - the DP awakening
Teaches you how to compress O(n) space down to O(1) using just two variables
String branching with memoization shows why top-down DP feels natural