Topic notebook / 08
Dynamic programming
A DP state represents one precise subproblem. Its recurrence combines already-computed states.
What to look for
- Define the state in words.
- Choose correct base cases.
- Compute dependencies before their consumers.
Work through a question
9 availableCount Routes Up the Observatory
An observatory stairway allows moves of one or two steps. Return the number of ordered move sequences that reach exactly n steps. Original scenario; n = 0 is explicitly one empty route.
Easy / One-dimensional prefix DP / interactiveSelect a Rising Sensor Trail
Readings arrive in time order. Select a strictly increasing subsequence, allowing skipped readings, and return its largest possible length. Original sensor scenario; equal readings cannot extend a trail.
Medium / DP by subsequence endpoint / interactiveAlign Two Beacon Transcripts
Two lowercase beacon transcripts may skip letters. Return the length of their longest shared subsequence, preserving order in both. Original alignment scenario; this is not a common substring.
Medium / Two-dimensional prefix DP / interactiveSplit a Joined Field Note
A lowercase field note lost its spaces. Decide whether the whole note can be split into dictionary words, reusing words as needed. Original scenario; the empty note is explicitly segmentable. Supply distinct dictionary words as comma-separated plain parameter text.
Medium / Reachable-prefix DP / interactiveCount Ordered Token Programs
A program consists of positive-valued tokens. Count ordered token sequences whose values total the requested amount; each token value can be used repeatedly. Original program scenario; [1,3] and [3,1] are different programs.
Medium / DP by final choice / interactiveSchedule Nonadjacent Gallery Checks
A line of galleries offers nonnegative inspection rewards. Adjacent galleries share a guard shift, so select no two neighbors. Return the greatest total reward; checking none is allowed. Original inspection scenario; the nonadjacent-maximization task is unchanged.
Medium / Take-or-skip prefix DP / interactiveSchedule Checks Around a Courtyard
Gallery rewards form a ring: the first and last galleries are also neighbors. Select no adjacent galleries and return the largest reward. Original courtyard scenario; one gallery can be checked, and an empty ring earns 0.
Medium / Two linear DPs for a cycle / interactiveRead a Numbered Beacon Message
Beacon letters use numbers 1 through 26. Count the ways to split a digit message into valid letter numbers. A lone zero and a leading-zero number are invalid. Original beacon scenario; an empty received message returns 0.
Medium / One- or two-digit prefix DP / interactiveCount Routes Across a Roof Garden
A rectangular roof garden has no blocked cells. Count paths from its top-left cell to its bottom-right cell, moving only right or down. Original garden scenario; the standard dimensions-and-count contract is unchanged.
Medium / Grid DP from above and left / interactiveWhere this leads
Return to the roadmap to try a different kind of problem.