Dynamic Programming by Hand: Overlapping Subproblems, Memo Tables, Coin Change, Knapsack, Longest Common Subsequence & Grid Paths
Fill the tables that dynamic programming is built on. You will count how often a naive recursion repeats itself, build memo tables bottom-up, solve stair-climbing and coin-change problems, fill a 0/1 knapsack grid, trace a longest common subsequence back through its table, count grid paths around obstacles and compare the work against brute force, with every cell checked as you go.
One-time payment · lifetime access · lessons, labs, exam and certificate included · no subscription.
About this course
This course shows how dynamic programming works by filling every table cell by cell. You count how many calls a naive recursion makes and compare them with a memo table and the bound 2^n, then build bottom-up tables for climbing stairs. You find the fewest tokens for an amount with XLOOKUP and MIN, see where the greedy rule fails, and count the ways to make an amount token by token. You fill a 0/1 knapsack grid with MAX(skip, take) and trace back the packed items, build a longest common subsequence grid with MID, count robot paths around blocked squares, find the cheapest path through a cost grid and finish with the longest increasing subsequence and a brute-force cost chart.
Lessons
- Overlapping Subproblems: Counting the Calls of a Naive Recursion Pro
- Bottom-Up Tables: Ways to Climb n Stairs with 1-, 2- or 3-Steps Pro
- Coin Change I: The Fewest Tokens for an Amount, Impossible Amounts & Why Greedy Fails Pro
- Coin Change II: Counting the Ways Token by Token – and Why Loop Order Matters Pro
- 0/1 Knapsack: The Capacity × Item Grid, MAX(Skip, Take) and the Traceback Pro
- Longest Common Subsequence: Letters with MID, the LCS Grid and the Traceback Pro
- Grid Paths & Cheapest Paths: Blocked Squares, Cost Grids and the Way Back Pro
- Capstone: Longest Increasing Subsequence and Brute Force vs Dynamic Programming Pro