Dynamic programming: from Fibonacci to coin change

9 steps · about 12 h 42 min · Beginner

  1. Dynamic Programming (DP) Introduction (article, GeeksforGeeks, 20 min)

    It defines overlapping subproblems and the memoization versus tabulation split before you meet any problem.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.