Source: https://mokxi.com/teachers/plans/dynamic-programming
Updated: 2026-11-19

Lesson plan

# Dynamic programming and optimization lesson plan

Solve a space mission's hard choices with tables on a Raspberry Pi: overlapping subproblems, coin change, knapsack, edit distance, greedy against DP, scheduling, and a route planner between stations.

4 chapters, 7 lessons, about 5 hours, on the Raspberry Pi 4 Model B. Every lesson runs in the browser, with nothing to install.

Start a class from this course

The unit

## Objectives and materials

### By the end, students can

- Spot repeated work and replace it with a table filled bottom up.
- Pack a rocket and fix a garbled command, with the two most famous tables.
- When a quick choice is provably right, and when only a table will do.
- A route planner for ferries between space stations.

### Materials for the whole unit

- Half breadboard
- LED x 2
- Pushbutton
- Raspberry Pi 4 Model B
- Resistor x 2
- Traffic light module

Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.

Chapter 1. About 1 h 20 min

## Think in tables

Spot repeated work and replace it with a table filled bottom up.

Lesson | Time | What students do

Overlapping subproblems A docking ladder climbed 1, 2 or 3 rungs at a time: see the same subproblem solved hundreds of times, memoize it, turn it into a table filled bottom up, and shrink the table to three numbers that climb 1000 rungs where recursion cannot. | 40 min

- Count the ways, slowly
- Count the repeats
- Top down: memoize
- Bottom up: fill a table
- Three numbers are enough

Coin change Thruster burns of fixed sizes: greedy picks three burns where two will do, a DP table finds the fewest, a pick table says which, a second DP counts every mix, and reachability shows which speeds can never be hit. | 40 min

- Greedy takes the big one
- The DP table
- Which burns?
- Count every mix
- Speeds you can never hit

### Materials

- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2

### Check for understanding

Each student finishes "Coin change" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Speeds you can never hit".

Chapter 2. About 1 h 20 min

## The classics

Pack a rocket and fix a garbled command, with the two most famous tables.

Lesson | Time | What students do

Knapsack Pack a rocket's last 10 kg for the most science: brute force over 256 loads, the 0/1 knapsack table, reconstructing the load, the one-row version and the classic bug of looping the wrong way, then 30 crates that brute force could never try. | 40 min

- Try every load
- The knapsack table
- What goes in the rocket
- One row, and the classic bug
- Thirty crates

Edit distance Garbled commands from a probe: why counting mismatched positions fails, the Levenshtein table, printing it, walking it back into a list of edits, and a command line that answers "did you mean DEPLOY?" | 40 min

- Counting positions is not enough
- The Levenshtein table
- Print the table
- Which edits?
- Did you mean?

### Materials

- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2

### Check for understanding

Each student finishes "Edit distance" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Did you mean?".

Chapter 3. About 1 h 20 min

## Greedy or DP

When a quick choice is provably right, and when only a table will do.

Lesson | Time | What students do

Greedy vs DP When a quick greedy choice is provably right and when it fails: satellite passes by earliest end against shortest first, fuel tanks that can be split against ones that cannot, and a test that tells which coin systems greedy can handle. | 40 min

- Earliest end first
- A greedy rule that sounds as good
- Split fuel versus whole tanks
- Which coin systems are greedy-safe?
- Greedy or DP: how to tell

Scheduling Weighted interval scheduling: when passes carry different amounts of data, earliest end first loses 15 MB. A DP with bisect finds the best schedule, a walk back names it, the red LED tracks it in time, and a sweep line counts antennas. | 40 min

- Greedy, with weights
- Take it or leave it, with a table
- The schedule
- Track it on the antenna
- How many antennas for everything?

### Materials

- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2

### Check for understanding

Each student finishes "Scheduling" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "How many antennas for everything?".

Chapter 4. About 55 min

## Project

A route planner for ferries between space stations.

Lesson | Time | What students do

Project: a route planner The project: a ferry route planner between space stations. Shortest times by DP in station order, the route walked back, the best route within a number of legs (Bellman-Ford rounds), and a planner on the traffic lights that takes a destination over serial. | 55 min

- The ferry map
- Shortest times, in order
- The route
- Fewer legs
- The planner, on the lights
- No route to Pluto
- What you built

### Materials

- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module

### Check for understanding

Each student finishes "Project: a route planner" on their own, without opening the hints. The simulator checks 7 of its 7 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "What you built".

Your class

## Teach this unit as a class

Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.

The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.

Start a class from this course See the demo class

More units

## Other lesson plans

Electronics basics 20 lessons, about 10 h. Embedded on the Arduino Uno 16 lessons, about 12 h. Embedded on the ESP32-C3 13 lessons, about 11 h. Embedded on the Raspberry Pi Pico 7 lessons, about 6 h. Build your own fight stick 5 lessons, about 4 h. Embedded on the STM32F411 6 lessons, about 6 h. C++ on a board 13 lessons, about 10 h. Digital logic and memory 4 lessons, about 4 h. Interactive devices on the Uno 9 lessons, about 8 h. From gates to a computer 23 lessons, about 16 h. Build a claw machine 8 lessons, about 6 h. Every unit All the courses as ready-made units, on the teachers page.
