18:35 3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method Abdul Bari
4.7M views · 73.6K 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.4M views · 88.3K likes · 1 year ago
48:57 Acing Google Coding Interview as an 18 year old High School Student William Lin (tmwilliamlin168)
2.9M views · 50.2K likes · 6 years ago
8:26 Namaste DSA 🚀 - Zero to Hero course for Data Structures & Algorithm Akshay Saini
2.5M views · 3.1K likes · 1 year ago
Dynamic Programming Educators
Gate Smashers
@gatesmashers
Web Dev
Welcome to Gate Smashers, one of the fastest-growing EdTech communities with 2.6 M+ learners. 🎓 We provide complete lec...
2.7M Subs
2.1K Videos
8.6K Avg Views
4.33% Engagement
GeeksforGeeks
@geeksforgeeksvideos
Web Dev
Welcome to the Official Channel of GeekforGeeks, your one-stop destination for diverse tech education! 🚀 Tech Variety:...
1.2M Subs
4.1K Videos
5.8K Avg Views
4.96% Engagement
NeetCode
@neetcode
CS
Preparing for technical interviews? Checkout neetcode.io
1.1M Subs
432 Videos
42K Avg Views
2.87% Engagement
NeuralNine
@neuralnine
AI Coding
NeuralNine is an educational brand focusing on programming, machine learning and computer science in general! Let's deve...
471K Subs
1K Videos
6.2K Avg Views
4.65% 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.