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 BFree7 lessons5 h4 chapters2,530 XPCoding · Advanced+250 XP

0 of 7 done

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.

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

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

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

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

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

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

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

  1. Overlapping subproblemsA 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.
  2. Coin changeThruster 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

  1. KnapsackPack 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.
  2. Edit distanceGarbled 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

  1. Greedy vs DPWhen 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.
  2. SchedulingWeighted 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

  1. Project: a route plannerThe 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.