18:35 3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method Abdul Bari
4.6M views · 72.1K likes · 8 years ago
What Is Dynamic Programming?
Dynamic programming (DP) solves complex problems by breaking them into overlapping subproblems and storing their solutions to avoid redundant computation. Instead of recalculating fibonacci(5) three times in a recursive tree, compute it once and cache the result. DP turns exponential algorithms into polynomial ones.
How Dynamic Programming Works
Fibonacci without DP: O(2^n) — recalculates the same values repeatedly. With DP (memoization): O(n) — calculate each value once, store in an array. fib(50) goes from billions of operations to 50 operations.
Classic DP problems: longest common subsequence, knapsack problem, coin change, edit distance, and many LeetCode problems. The pattern: define subproblems, write the recurrence relation, add memoization or build bottom-up.
Key Concepts
- Memoization (Top-Down) — Cache recursive function results — if already computed, return the cached value
- Tabulation (Bottom-Up) — Build a table from smallest subproblems up — avoids recursion overhead
- Optimal Substructure — The optimal solution contains optimal solutions to subproblems
- Overlapping Subproblems — The same subproblems are solved multiple times — caching eliminates redundancy
Learn Dynamic Programming — Top Videos
18:35 
36:54 But what is quantum computing? (Grover's Algorithm) 3Blue1Brown
3.1M views · 84.5K likes · 10 months ago
48:57 Acing Google Coding Interview as an 18 year old High School Student William Lin (tmwilliamlin168)
2.9M views · 50.1K likes · 5 years ago
8:26 Namaste DSA 🚀 - Zero to Hero course for Data Structures & Algorithm Akshay Saini
2.5M views · 3.1K likes · 9 months ago
Dynamic Programming Educators
Gate Smashers
@gatesmashers
Data Science
Welcome to Gate Smashers, one of the fastest-growing EdTech communities with 2.6 M+ learners. 🎓 We provide complete lec...
2.6M Subs
2K Videos
13.8K Avg Views
1.58% Engagement
NeetCode
@neetcode
CS
Current NEET and ex-Google SWE, also I love teaching! N.E.E.T. = (Not in education, employment or training) Preparing ...
1.1M Subs
414 Videos
128.4K Avg Views
3.99% Engagement
NeuralNine
@neuralnine
Web Dev
NeuralNine is an educational brand focusing on programming, machine learning and computer science in general! Let's deve...
461K Subs
1K Videos
14.3K Avg Views
4.77% Engagement
Greg Hogg
@greghogg
Data Science
Today, Greg is driven by a single mission: to help engineers master the complex technical skills required to land roles ...
309K Subs
1.3K Videos
9.1K Avg Views
3.31% Engagement
Frequently Asked Questions
How do I recognize DP problems?
Ask: can I break this into overlapping subproblems? Is there a recurrence relation? Does the problem ask for optimization (min/max) or counting? If yes, try DP.
Is dynamic programming hard?
DP has a learning curve. Start with 1D problems (climbing stairs, coin change), then 2D (grid paths, longest common subsequence). Practice recognizing patterns rather than memorizing solutions.
Want a structured learning path?
Plan a Dynamic Programming Lesson →