Dynamic programming: from Fibonacci to coin change
9 steps · about 12 h 42 min · Beginner
- Dynamic Programming (DP) Introduction (article, GeeksforGeeks, 20 min)
It defines overlapping subproblems and the memoization versus tabulation split before you meet any problem.
- Dynamic Programming 101 (article, Masai School, 20 min)
It lists the keywords that signal a DP problem and suggests an order for practising: stairs, house robber, coin change, knapsack, then LCS and edit distance.
- Dynamic Programming for Beginners (video, freeCodeCamp (Alvin Zablan), 5 h)
This long course covers Fibonacci, grid paths and coin change with memoization first, then tabulation. Watch it in sections.
- Learn Dynamic Programming with Animations (video, freeCodeCamp.org / AlgoMonster, 2 h)
Animated tables make the recurring DP patterns easier to see. Use it to reinforce what the first course taught.
- Coin Change Problem (video, Geekific, 7 min)
A short walkthrough of one classic problem. It goes from a 2D table to a 1D table in Java.
- 322. Coin Change - In-Depth Explanation (article, AlgoMonster, 15 min)
It explains the state transition and why reusing a coin makes this an unbounded knapsack.
- Lecture 15: Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling (video, MIT OpenCourseWare (Erik Demaine), 50 min)
It gives you a reusable framework, SRTBOT, for designing any DP solution and checking its running time.
- Lecture 18: Dynamic Programming, Part 4: Rods, Subset Sum, Pseudopolynomial (video, MIT OpenCourseWare (Erik Demaine), 50 min)
It covers rod cutting and subset sum, then explains pseudopolynomial time, which is the usual cost of knapsack-style DP.
- CSES Problem Set index (offbeatcc/cses) (reference, GitHub (offbeatcc), 3 h)
It indexes the 19 CSES DP problems, from Dice Combinations to Counting Numbers. Solve them in order to practise on your own.