MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns  Module 24 – Dynamic programming: foundations

Designing DP states and transitions

Design a DP state as the least you must know to decide the rest, then write its transitions, base cases and answer, and test it against a brute force.

  • Beginner
  • 35 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0, quickjs 0.32.0, Java 25.0.4.1, Clang 21.0.0 and Go 1.27.1
  • By MySmartCoPilot
Free: A revision plan with rest days · The brute force: every plan · What the rest of the plan needs to know · 4 more sections. With a pass: 3 in-depth parts and 3 interview answers, about 24 minutes.

What you will learn

  • Define a DP state as the least information the rest of the problem needs
  • Write the transitions, base cases and answer of a DP in words before coding it
  • Classify a DP question as counting, optimisation or feasibility
  • Test a state design against a brute force to catch missing or surplus information
  • Rebuild the choices behind a DP's answer from its table

Before you start

What you’ll learn · Before you start

What you will learn

  • Define a DP state as the least information the rest of the problem needs
  • Write the transitions, base cases and answer of a DP in words before coding it
  • Classify a DP question as counting, optimisation or feasibility
  • Test a state design against a brute force to catch missing or surplus information
  • Rebuild the choices behind a DP's answer from its table

Before you start

On this page

Designing DP states means deciding what one entry of a dynamic-programming table stands for. A good state is the least information about the choices already made that the rest of the problem needs. The test is simple: two partial solutions that reach the same state must allow exactly the same ways to finish, so the table can keep the better of them, or their count. Around the state you write the transitions (the choices a state has and where each leads), the base cases (states with nothing left to decide) and the answer (the state the problem starts from). A wrong state returns wrong numbers and raises no error, so every design is checked against a brute force, as in the stress-testing lesson.

This lesson works through designing DP states for one original problem: its brute force first, then the state, its transitions and a table filled by hand.

A revision plan with rest days

The problem

There are n days before an exam. Studying on day i is worth values[i] points, and the rule is that you may study on at most k days in a row: after k study days in a row the next day must be a rest day. Return the largest total a plan can earn. Limits: 0 ≤ n ≤ 100,000, 1 ≤ k ≤ 20 and 0 ≤ values[i] ≤ 10,000.

  • [5, 3, 8, 6, 2] with k = 2 gives 19: study on days 0, 2 and 3, rest on days 1 and 4.
  • The same days give 15 with k = 1 (days 0, 2 and 4) and 24 with k = 5 (every day).
  • No days at all give 0.

The brute force: every plan

A plan says, for each day, study or rest, so n days have 2ⁿ plans. Try each one, drop those with more than k study days in a row, and keep the best total:

Every plan tried, and how many there are Python · brute/plans_brute.py 
from itertools import product


def best_plan_brute(values, k):
    """Tries every study-or-rest plan and keeps the best one with at most k study days in a row."""
    best, best_days, checked = 0, [], 0
    for plan in product((False, True), repeat=len(values)):  # True: study that day
        checked += 1
        run = longest = 0
        for study in plan:
            run = run + 1 if study else 0
            longest = max(longest, run)
        if longest <= k:
            total = sum(v for v, study in zip(values, plan) if study)
            if total > best:
                best, best_days = total, [day for day, study in enumerate(plan) if study]
    return best, best_days, checked


for values, k in [([5, 3, 8, 6, 2], 2), ([5, 3, 8, 6, 2], 1), ([5, 3, 8, 6, 2], 5), ([], 2)]:
    best, days, checked = best_plan_brute(values, k)
    studied = f"days {', '.join(map(str, days))}" if days else "no day"
    plans = "plan" if checked == 1 else "plans"
    print(f"{values}, k = {k}: best {best}, studying on {studied} ({checked} {plans} checked)")

for n in (8, 12, 16):
    *_, checked = best_plan_brute([1] * n, 2)
    print(f"{n} days: {checked:,} plans checked")

Output

[5, 3, 8, 6, 2], k = 2: best 19, studying on days 0, 2, 3 (32 plans checked)
[5, 3, 8, 6, 2], k = 1: best 15, studying on days 0, 2, 4 (32 plans checked)
[5, 3, 8, 6, 2], k = 5: best 24, studying on days 0, 1, 2, 3, 4 (32 plans checked)
[], k = 2: best 0, studying on no day (1 plan checked)
8 days: 256 plans checked
12 days: 4,096 plans checked
16 days: 65,536 plans checked

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 plans_brute.py

The answers are right, so the brute force will judge faster versions, but each extra day doubles the work: 65,536 plans for 16 days, and for 100,000 days a number of plans with 30,103 digits.

What the rest of the plan needs to know

Stand at the start of day i with the earlier days already planned, and ask which of those decisions can change what is allowed from now on. The points they earned cannot: they are banked. Which days they were cannot either. Only one fact matters, the streak: how many study days in a row end just before day i. If the streak is k, day i must be a rest day; otherwise both choices are open, and each choice sets the next streak. Two partial plans with the same day and streak can be finished in exactly the same ways, so the table only needs the better of them.

Three states of a revision plan for k = 2, streak 0, 1 and 2, linked by study arrows that add one and rest arrows back to streak 0.streak 0the day before was a rest day,or there was no day beforestreak 1one study day just beforestreak 2two study days in a row:today must be a rest daystudy (+ value of the day)study (+ value of the day)restrestrest

What the rest of the plan needs to know, for k = 2

Text description of the diagram

The diagram has three boxes, one for each value of the streak, the number of study days in a row just before the day being decided, when at most two study days in a row are allowed.

  1. Streak 0: the day before was a rest day, or there was no day before. Studying today adds the day's value and leads to streak 1; resting keeps the streak at 0.
  2. Streak 1: one study day just before. Studying adds the day's value and leads to streak 2; resting leads back to streak 0.
  3. Streak 2: two study days in a row. Today must be a rest day, so the only arrow leads back to streak 0.

Everything else about the days already planned, which days they were and what they earned, makes no difference to which plans for the remaining days are allowed. That is why the state is the day and the streak, and nothing more.

The state and its transitions, in words

  1. State: best(i, s) is the most points days i to n − 1 can still add when the s days just before day i were all study days, for 0 ≤ s ≤ k.
  2. Transitions: a rest on day i leads to best(i + 1, 0). A study day, allowed only when s < k, earns values[i] and leads to best(i + 1, s + 1). best(i, s) is the larger of the allowed choices.
  3. Base cases: best(n, s) = 0 for every s, because no days are left to earn anything.
  4. Answer: best(0, 0), since no study day comes before day 0.

There are (n + 1)(k + 1) states, 2,100,021 at the largest limits, each with at most two choices, so the table costs O(n·k) time. Row i reads only row i + 1, so it can be filled from the last day backwards.

The table, filled by hand

The table for [5, 3, 8, 6, 2] and k = 2, from the last row up:

Day i values[i] s = 0 s = 1 s = 2
5 (no days left) — 0 0 0
4 2 2 2 0
3 6 8 6 2
2 8 14 10 8
1 3 14 14 14
0 5 19 19 14

Take day 2 with s = 0: studying earns 8 plus best(3, 1) = 6, which makes 14, and resting gives best(3, 0) = 8, so the entry is 14. At s = 2 only a rest is allowed. The answer best(0, 0) = 19 matches the brute force, and following the choice behind each maximum gives the plan: study on days 0, 2 and 3.

Counting, optimisation and feasibility

The same state answers three kinds of question, and only the way choices combine changes:

  • Optimisation keeps the larger or smaller choice, as above, and its empty rest of a plan is worth 0.
  • Counting adds the counts of the choices, so the empty rest counts as 1 way, usually modulo a prime.
  • Feasibility asks whether any choice works, so the empty rest counts as true.

Exercise

Exercise · Easy · Python

Count the rows of festival lights with no three alike

A row of n festival bulbs is to be strung, and each bulb can be any of c colours. The only rule: no three bulbs next to each other may have the same colour. Write light_rows(n, c), the number of different rows, modulo 1,000,000,007, for 1 ≤ n ≤ 100,000 and 1 ≤ c ≤ 100,000.

light_rows(1, 3)  # 3
light_rows(3, 3)  # 24: all 27 rows except red-red-red, green-green-green and yellow-yellow-yellow
light_rows(4, 2)  # 10

Design the state before you write any code. Say in words what the rest of the row needs to know about the bulbs already placed, check the words against a few rows written out by hand, and only then write the transitions, the base case and the answer.

The sample tests compare your function with a listing of every row for small n and c, try one colour (where a row of three or more bulbs is impossible), and run n = c = 100,000, where the counts must come back reduced.

Starter code · lights.py 

MOD = 1_000_000_007


def light_rows(n, c):
    """The number of rows of n bulbs in c colours with no three neighbours alike, modulo MOD."""
    # Replace this line with your code.
    return 0
The sample tests · test_lights.py 
from itertools import product

from lights import light_rows

MOD = 1_000_000_007


def listed(n, c):
    """The answer the tests trust for small rows: every row of n bulbs in c colours, written out and checked."""
    return sum(
        all(not (row[i] == row[i + 1] == row[i + 2]) for i in range(n - 2))
        for row in product(range(c), repeat=n)
    )


def test_the_examples():
    """the examples of the prompt"""
    assert light_rows(1, 3) == 3
    assert light_rows(3, 3) == 24
    assert light_rows(4, 2) == 10


def test_small_rows_against_a_listing():
    """n = 1 to 7 and c = 2 to 4, each compared with every row listed one by one"""
    for n in range(1, 8):
        for c in range(2, 5):
            assert light_rows(n, c) == listed(n, c), f"light_rows({n}, {c})"


def test_one_colour():
    """with one colour, one or two bulbs make one row, and three or more make none"""
    assert [light_rows(n, 1) for n in (1, 2, 3, 10)] == [1, 1, 0, 0]


def test_counts_above_the_modulus():
    """n = 40 and c = 3: the count is far above 1,000,000,007, so it must come back reduced"""
    assert light_rows(40, 3) == 340_831_928_248_172_544 % MOD


def test_a_long_row_of_many_colours():
    """n = c = 100,000: a loop over the positions, with the counts reduced as it goes"""
    assert light_rows(100_000, 100_000) == 948_181_920
A hint

The next bulb does not care which colours came before it, only whether it may repeat the last colour. When is that allowed? Two numbers per position are enough: the rows that end with two bulbs of the same colour, and the rows that do not.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Python Online Compiler Run the brute force on plans of your own, and fill a table for them by hand to compare.

Check yourself

6 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.

  1. Question 1 of 6 Sketch 1. Count the ways to climb a staircase of n steps, taking 1 or 2 steps at a time. What is the least the rest of the climb needs to know?

    Choose one answer.

    Show the answer

    Answer: The step you are standing on

    The ways to finish the climb from step i are the same however you reached step i, so the step alone is the state: n + 1 states. The last stride or the number of strides would matter only if the problem had a rule about them, such as "never two strides of 2 in a row", and then that rule's information joins the state.

  2. Question 2 of 6 Sketch 2. Paint a row of n houses, each red, green or blue at a cost that depends on the house and the colour, so that no two neighbours share a colour. What is the state for the cheapest painting?

    Choose one answer.

    Show the answer

    Answer: The house to paint next and the colour of the house before it

    The only rule looks one house back, so the next house needs to know the colour of the previous one and nothing else: 3n states. The house alone loses that colour, so the table could paint two neighbours alike. Every earlier colour is right but makes 3ⁿ states, and the cost so far is what the DP computes, never part of its state.

  3. Question 3 of 6 Sketch 3. A trader holds at most one unit of a commodity, buys and sells at each day's price, and must wait one full day after a sale before buying again. What is the state for the largest profit?

    Choose one answer.

    Show the answer

    Answer: The day, and which of three situations the trader is in: holding, waiting a day after a sale, or able to buy

    What may happen next depends on whether a unit is held and, if not, on whether a sale happened yesterday. Two situations are not enough: "not holding" mixes a trader who may buy today with one who may not. The price paid is not needed either, because the profit of a purchase can be counted the day it is made.

  4. Question 4 of 6 Sketch 4. Decide whether some of n coins, each used at most once, add up to exactly T. What is the state?

    Choose one answer.

    Show the answer

    Answer: The next coin to consider and the amount still to make

    Whether the rest of the coins can finish the job depends on which coins are left and how much is still missing, so both belong in the state: up to n × (T + 1) states. The amount alone would let a coin be used twice; the set of coins used is right but has 2ⁿ values, most of them leading to the same amount.

  5. Question 5 of 6 Sketch 5. Count the routes across a grid from the top-left cell to the bottom-right, moving right or down, that pass through at most one toll cell. What is the state?

    Choose one answer.

    Show the answer

    Answer: The cell, and whether a toll cell has been passed already

    A route that has already paid a toll may not enter another toll cell, while one that has not may, so the two must be counted apart: two states per cell. The number of cells visited is the same for every route to a cell (its row plus its column), so it adds nothing.

  6. Question 6 of 6 The table of the revision plan keeps, for each state, the most points the remaining days can add. To count the valid plans instead, what changes?

    Choose one answer.

    Show the answer

    Answer: Each state adds up the counts of its choices instead of taking the larger, and the last day's states start at 1 instead of 0

    The state and the transitions stay the same; only the way choices are combined changes. Optimisation keeps the larger choice, counting adds the choices up, and feasibility asks whether any choice works. The base case changes with it: an empty rest of a plan earns 0 points but can be finished in exactly 1 way, by doing nothing.

Two wrong states and one right one, tested against the brute force Pro

A state that lacks information returns wrong numbers without any error. Here two tempting designs run against the brute force until they fail, a design with too much information is measured, and an empty input breaks a table.

In this part:

  • Too little state, reproduced: two designs that forget the streak
  • Too much state, measured: the whole plan as the key
  • A base-case bug that only an empty input shows
  • A checklist for any state you design

3 runnable examples (Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

The revision plan proved, in O(k) memory, in five languages Pro

The table becomes a loop of a few lines. This part proves the loop right, cuts its memory to two rows of k + 1 numbers, and runs it in five languages on the same six inputs.

In this part:

  • Why the table is right, by induction from the last day
  • Two rows of k + 1 numbers instead of a table
  • The code in five languages
  • The cost, state by state

2 runnable examples (C++, Go, Java, JavaScript, Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

One state, three questions: counting, feasibility and the plan itself Pro

A state that is right for the best total is right for other questions about the same plans. Here it counts the plans, decides whether fixed study and rest days can be kept, and rebuilds the best plan from the full table.

In this part:

  • Counting the valid plans modulo 1,000,000,007
  • Required and blocked days, as a yes-or-no table
  • Rebuilding the best plan from the table
  • Practice: five sketches and the state each needs

1 runnable example (Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

  1. Fresher to mid · Warm-up

    What is a state in dynamic programming, and how do you check that a state carries enough information?

    A state is one entry of the table: a few values, such as a position and a count, that summarise the choices made so far. It must hold the least information the rest of the problem needs. The check is to take two different partial solutions that reach the same state and ask whether they allow exactly the same ways to finish. If they do, the table may keep only the better one, or only their count. If a completion is allowed after one and forbidden after the other, the state is missing what tells them apart. In the revision plan of the lesson, the day alone fails this test, because a streak of k study days and a rest the day before look the same; the day and the streak pass it. Then compare the design with a brute force on small inputs.

  2. Mid to senior

    Your DP for a scheduling problem passes the examples, but on a hidden test it reports a total higher than any valid schedule can earn. You suspect the state. How do you find what the state is missing, and how do you fix it without guessing?

    First step and follow-ups

  3. Mid to senior

    A memoised solution of the revision plan keys its cache on the day and a bitmask of the last k decisions, with k up to 20 and n up to 100,000, and it runs out of memory. How many states can it create, what smaller state would you use, and why does it lose nothing?

    First step and follow-ups

  4. Senior to staff

    Besides the best total of the revision plan, return how many different plans reach that total, modulo 1,000,000,007. What does each state store, how do ties combine, and what does it cost?

    First step and follow-ups

Key takeaways

  • A DP state is the least the rest of the problem needs to know: for the revision plan, the day and the streak.
  • Two partial solutions in the same state must allow the same completions.
  • Write the state, transitions, base cases and answer in words first, and fill a small table by hand.
  • Optimisation, counting and feasibility share a state; only how choices combine and the base case change.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. JavaScript & TypeScript Online Compiler Write, run and debug JS or TS snippets — safely sandboxed, nothing to install.

Report a problem with this lesson