Dynamic Programming by Hand: Overlapping Subproblems, Memo Tables, Coin Change, Knapsack, Longest Common Subsequence & Grid Paths

What you'll build

What you will be able to do

Each lab ends with a concrete result that you build yourself and the checker confirms, cell by cell.

• Fill a toy recursion f(n) = f(n−1) + f(n−2), count how many calls the naive version makes for every n, compare that with the n + 1 entries of a memo table and with the bound 2^n, and work out the saving factor.
• Build two bottom-up tables for climbing 12 stairs, one with 1- or 2-steps and one that also allows 3-steps, compare the two counts and count the ways that must stop on a landing.
• Check a half-filled fewest-tokens table with three “via” columns built from XLOOKUP, extend it to amounts 13–15 with MIN, and show that the greedy rule pays amount 10 with more tokens than the table.
• Fill a ways table token by token for amounts 0–12, check one cell against a hand list, then count ordered sequences in a second row and see how much larger that count is.
• Fill a 5-item × 11-capacity knapsack grid with MAX(skip, take), read off the best value for a 10 kg hamper and trace back which items were packed.
• Split two toy words into letters with MID, fill the longest-common-subsequence grid, read the LCS length, turn it into a similarity score and trace the common letters back.
• Count a robot’s right/down paths around blocked squares, find the cheapest route through a cost grid, measure the saving against the edge route and read which way the best path arrives.
• Fill a longest-increasing-subsequence table with MAXIFS, read the longest rising run, and compare the steps of brute force (2^n) with DP tables (n² and n·(W + 1)) in a table and a chart.