...
All chaptersLeaderboard

Chapter 20 - Python Quest

Dynamic Programming Workshop

Solve smaller states once, save their answers, and reuse them for routes, costs, and combinations.

XP
0Level 1
Stars
0/30quest stars
Combo
0clean runs
Rank
Seed0/160 Python score
Building and returning a DP table

Firefly Signal Notebook

100 XP

A firefly team sends one signal in rounds 0 and 1. Every later round combines the signal counts from the previous two rounds, and the team wants the entire notebook so it can inspect every saved answer.

Write signal_notebook(rounds) so it returns a list of saved signal counts from round 0 through rounds. Round 0 is 1, round 1 is 1, and every later value is the sum of the previous two saved values. rounds is a nonnegative integer.

Interactive trace

Build every route count through step 6

Bottom-up DP starts with the smallest finished answers, then fills one new notebook cell at a time.

Saved answerReused sourceWriting nowCache hit
  1. ?
    0
  2. ?
    1
  3. ?
    2
  4. ?
    3
  5. ?
    4
  6. ?
    5
  7. ?
    6

Start with complete base states, then move left to right.

goal
6
writing
-
writes
0
states solved
0
1
def hop_table(steps):
2
    dp = [0] * (steps + 1)
3
    dp[0] = 1
4
    if steps >= 1:
5
        dp[1] = 1
6
    for step in range(2, steps + 1):
7
        dp[step] = dp[step - 1] + dp[step - 2]
8
    return dp
1 / 24

Sample checks

signal_notebook(rounds=0)returns[1]

Explanation: the notebook includes round zero itself, whose one empty starting signal is already a complete base answer, so the returned list has one cell

signal_notebook(rounds=1)returns[1,1]

Explanation: rounds zero and one are both base states with one signal each, producing the two saved entries 1 and 1 without a recurrence step

Hint

Hints are ready when you want one.

Lesson reference

Review: Fill a table from complete smaller answers

Your Python

signal_notebook

Loading editor

Judge

Ready

0/6

Run your code when it feels ready.