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
Apna College
@apnacollegeofficial
Web Dev
ApnaCollege is where Tech Education meets Real-world needs. Started with a vision to provide ‘Quality’ & ‘Practical’ le...
7.8M Subs
1K Videos
87.5K Avg Views
4.42% Engagement
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.8M Subs
2.2K Videos
16.6K Avg Views
3.63% 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
6.1K Avg Views
6.45% Engagement
NeetCode
@neetcode
CS
Preparing for technical interviews? Checkout neetcode.io
1.1M Subs
455 Videos
34.2K Avg Views
3.23% 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.