RavnaryA Knowledge Platform
Colour theme

Card 02/ 10

Take the quiz

WalkthroughDifficulty: Intermediate3 min

Define a State and a Recurrence, Then Check Them by Hand

Say what one table entry means, how it follows from smaller ones, and test that on four values before coding.

Designing a dynamic programme comes down to four decisions, the state, the recurrence, the base cases and where the answer sits, and a hand check on a small input before any code is written. This card makes the four decisions for one problem and checks them on four values.

A market runs four stalls in a row, and the stalls' takings for a day are 3, 2, 7 and 10. An inspector can audit any of them but never two neighbours on the same day, since neighbours share a till. Which stalls should be audited to cover the largest total takings?

  1. The state says what one entry of the table means, in words. Here dp[i] is the largest total that can be audited from stalls 0 to i alone.
  2. The recurrence says how an entry follows from smaller ones. Stall i is either skipped, leaving the best from stalls 0 to i − 1, or audited, which rules out stall i − 1 and leaves the best from stalls 0 to i − 2. So dp[i] = max(dp[i − 1], dp[i − 2] + takings[i]).
  3. The base cases are the entries the recurrence cannot reach back from. dp[0] is stall 0's takings, and dp[1] is the larger of the first two.
  4. The answer is the entry for the whole input, dp[3].
Before reading on: what is the largest total, and from which stalls?

13, from stalls 0 and 3, which are not neighbours: 3 + 10. Stalls 2 and 3 hold the most between them, 17, but they are neighbours.

The hand check fills the table in order and compares each entry with what you can see directly. A run printed the table after each step.

Filling the best-total table for stall takings 3 2 7 10

Input3 2 7 10

  1. Empty table

    1. -
    2. -
    3. -
    4. -

    The table has one entry per stall, and entry i will hold the best total from the first i + 1 stalls. Nothing is filled yet.

  2. dp[0] = 3

    1. 3i
    2. -
    3. -
    4. -

    With one stall the only choice is to take it, so dp[0] is its takings, 3.

  3. dp[1] = max(3, 2)

    1. 3
    2. 3i
    3. -
    4. -

    With two stalls you can take only one of them, so dp[1] is the larger, 3.

  4. dp[2] = max(3, 3 + 7)

    1. 3
    2. 3
    3. 10i
    4. -

    Stall 2 can be skipped, keeping dp[1] = 3, or taken with the best from two stalls back, dp[0] + 7 = 10. Taking it wins.

  5. dp[3] = max(10, 3 + 10)

    1. 3
    2. 3
    3. 10
    4. 13i

    Stall 3 can be skipped, keeping 10, or taken with dp[1] + 10 = 13. Taking it wins, and 13 is the answer: stalls 0 and 3.

Result13

Each frame computed one entry from at most two earlier ones, and every entry agreed with a direct look at that many stalls. The hand check is worth doing for this reason: four values are few enough to see the right answer by eye, so a wrong state or recurrence shows up here, where it costs a minute, rather than in code that runs and prints a plausible wrong number. Swapping the Two Choices in the Recurrence shows the mistake it catches most often.

Once the check passes, the table has n entries, each filled in O(1), so the whole computation is O(n) time and O(n) space. The same four decisions design every dynamic programme in Knapsack and Grid Dynamic Programming and Sequence Dynamic Programming, later topics; only the state grows, to two indices for a knapsack or for two strings.

← → move through sections and cards