Source: https://mokxi.com/learn/path/dynamic-programming
Updated: 2026-11-20

All paths

# Dynamic programming and optimization

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.

Raspberry Pi 4 Model B Free 7 lessons 5 h 4 chapters 2,530 XP Coding · Advanced +250 XP

0 of 7 done

Start the course free Overlapping subproblems Lesson plan for teachers

What you will build

## 3 projects, built step by step

7 lessons in 4 chapters, about 5 hours on a simulated Raspberry Pi 4 Model B. Free, in your browser, every step checked by the simulator.

Chapter 1 project

### 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.
Open it in the simulator

Chapter 2 project

### 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?"
Open it in the simulator

Chapter 3 project

### 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.
Open it in the simulator

The map

## Chapter by chapter

Each lesson opens when the one before it is done, and each chapter ends in a project.

Chapter 1

## Think in tables

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

Open 250 XP

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

0 of 5 steps

Start What is in it

Project Locked 500 XP

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

0 of 5 steps

5 questions, graded as you go.

Chapter 2

## The classics

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

Locked 250 XP

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

0 of 5 steps

Project Locked 500 XP

### 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?"

0 of 5 steps

4 questions, graded as you go.

Chapter 3

## Greedy or DP

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

Locked 227 XP

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

0 of 5 steps

Project Locked 500 XP

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

0 of 5 steps

4 questions, graded as you go.

Chapter 4

## Project

A route planner for ferries between space stations.

Locked 303 XP

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

0 of 7 steps

3 questions, graded as you go.

Syllabus

## Every lesson in the course

All 7 lessons, in order, each with what it covers. Any of them opens in the editor right away.

Chapter 1

### Think in tables

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

Chapter 2

### The classics

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

Chapter 3

### Greedy or DP

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

Chapter 4

### Project

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

Kits

## Build it on your bench too

Every lesson runs in the simulator with nothing to buy. When you want the real thing, these kits have the parts.

Have a kit already?

### Find your kit

Pick the starter kit you own and run every lesson in its manual with the same parts on the same pins.
See every kit

Questions

## About Dynamic programming and optimization

Is Dynamic programming and optimization free?

Yes. All 7 lessons of Dynamic programming and optimization are free and run in your browser, with nothing to install and no parts to buy before you start.

Do I need a real Raspberry Pi 4 Model B?

No. Every lesson runs on a simulated Raspberry Pi 4 Model B with its parts on the canvas, and the simulator checks each step as you go. When you want to build it for real, the same wiring and code work on a real board.

How long does Dynamic programming and optimization take?

About 5 hours: 7 lessons in 4 chapters, each one a few short steps. Your progress is kept, so you can stop after any lesson and pick up where you left off.

What will I build?

Each chapter ends in a project that puts it together: Coin change, Edit distance and Scheduling.

Where do I start?

With "Overlapping subproblems", and each lesson builds on the one before it. New to circuits? Electronics basics is the course that starts from zero.
