One-dimensional dynamic programming

Dynamic programming is not a family of tricks but a discipline: state the subproblem precisely, enumerate the last decision exhaustively, and cover every base case including the impossible ones. This guide works through that discipline on one-dimensional problems — prefix recurrences, take-or-skip subsets, maximum subarray, coin change, and longest increasing subsequence — and is deliberate about the errors that produce plausible wrong answers: a base case of zero where the identity is one, an ending-here value reported as the overall best, and a loop nesting that answers the permutation question rather than the combination one. It closes on complexity read directly from the state definition, the pseudo-polynomial classification, and the boundaries against greedy and backtracking.

the two conditions for dynamic programming

Dynamic programming is useful when subproblems overlap and their answers compose into larger answers; optimisation problems call the latter property optimal substructure.

Optimal substructure means an optimum is built from subproblem optima; overlapping subproblems means the same state is reached many times, which is what caching exploits. Without overlap, the same recurrence may be valid but memoisation buys nothing.

Both, or the cache never hits and the recurrence is wrong.

# Fibonacci: fib(5) needs fib(3) twice -> overlapping. Optimal substructure trivially.
# Merge sort: two halves, never the same subproblem twice -> memoising buys nothing.

Interview trap. Applying it without overlapping subproblems adds a cache that never hits, and applying it without optimal substructure produces a recurrence that is simply wrong.

Engineering practice. State both conditions explicitly for the problem at hand before writing any recurrence.

defining the state

The state is the smallest set of parameters that determines the rest of the solution, and choosing it correctly is most of the work.

A state that omits a needed parameter makes the recurrence wrong; a state that includes an unnecessary one multiplies the table size for nothing.

Write it as a sentence before writing any code.

# "dp[i] = the maximum total from the first i houses, house i-1 optional."
# Not "dp[i] = something about house i" - that is where the recurrence goes wrong.

Interview trap. Copying a state definition from a similar problem is how a solution ends up correct on the samples and wrong on a constraint the original did not have.

Engineering practice. Write the state as an English sentence — 'the best result considering the first i items with j budget remaining' — before writing the transition.

the transition

The transition enumerates the last decision, and correctness follows from that enumeration being exhaustive and non-overlapping.

Each state's value combines the values of the states reachable by undoing one decision, which is why the decision must be the last one rather than an arbitrary one.

Enumerate the last decision, exhaustively and without overlap.

dp[i] = max(dp[i - 1],              # skip item i-1
            dp[i - 2] + a[i - 1])   # take it
# The two cases partition every solution: it either uses the last item or it does not.

Interview trap. An enumeration that misses a case gives an answer that is too small, and one that double counts gives an answer that is too large — both without any error.

Engineering practice. List the possible last decisions exhaustively and check that they partition the solution space.

base cases

The base cases must cover every state the recurrence can reach without recursing further, including the empty and impossible ones.

An impossible state usually needs a sentinel — negative infinity for a maximisation, or a distinguished unreachable marker — rather than zero.

Unreachable is not zero.

NEG = float("-inf")
dp = [NEG] * (target + 1)
dp[0] = 0            # the empty solution is reachable with value 0
# Initialising everything to 0 makes every amount look achievable.

Interview trap. Using zero for an impossible state makes it look achievable, which propagates a wrong answer through every state that depends on it.

Engineering practice. Distinguish 'zero value' from 'unreachable', and use a sentinel that cannot be produced by a legitimate combination.

memoisation versus tabulation

Top-down memoisation and bottom-up tabulation compute the same recurrence, and the choice is about which states are visited and how deep the recursion goes.

Memoisation visits only reachable states and follows the natural recursion; tabulation visits all states in a fixed order and avoids the call stack entirely.

Same recurrence; different visited set and stack usage.

from functools import cache
@cache
def f(i): return 0 if i < 0 else max(f(i - 1), f(i - 2) + a[i])   # only reachable states

dp = [0] * (n + 2)   # dp[0] and dp[1] are the two empty-prefix bases
for i in range(2, n + 2): dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 2])   # no stack

Interview trap. Choosing memoisation for a state space with linear depth reintroduces the recursion-limit problem that tabulation does not have.

Engineering practice. Use memoisation when the reachable state space is much smaller than the full one, and tabulation when depth or constant factors matter.

the iteration order in tabulation

A bottom-up table must be filled in an order where every dependency is already computed.

For a one-dimensional table over indices this is usually increasing order, but a recurrence that looks forward requires decreasing order instead.

Fill in dependency order, not by habit.

for i in range(1, n + 1):   dp[i] = dp[i - 1] + ...     # depends on smaller i
for i in range(n - 1, -1, -1): dp[i] = dp[i + 1] + ...  # depends on larger i

Getting this backwards reads uninitialised entries and produces data-dependent wrong answers.

Interview trap. Filling in the wrong direction reads uninitialised or stale entries and produces answers that are wrong in a data-dependent way.

Engineering practice. Derive the order from the dependency direction of the recurrence rather than defaulting to increasing.

the Fibonacci example and its lesson

Naive recursive Fibonacci is exponential and memoised Fibonacci is linear, which demonstrates the entire value of the technique in one line of change.

The exponential version recomputes the same subproblems repeatedly; the cache turns the call tree into a directed acyclic graph visited once per node.

Exponential to linear with one decorator.

def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)
fib(35)              # ~29,860,703 calls, several seconds

@cache
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)
fib(35)              # 36 calls

Interview trap. Treating Fibonacci as the model for all dynamic programming understates the difficulty, since real problems hide the state definition rather than handing it over.

Engineering practice. Use it to explain the mechanism, and move to a problem where the state must be discovered when demonstrating skill.

climbing stairs and counting paths

Counting the ways to reach a position is a sum over the ways to reach each predecessor.

The recurrence adds rather than maximises, and the base case is one way to be at the start rather than zero.

The empty-solution base case is 1, not 0.

dp = [0] * (n + 1)
dp[0] = 1                        # one way to be at the start
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + (dp[i - 2] if i > 1 else 0)
# dp[0] = 0 makes every entry 0.

Interview trap. Setting the base case to zero produces a total of zero everywhere, which is the most common error in counting problems.

Engineering practice. Set the empty-solution base case to one for counting problems, and to the identity of the operator generally.

the house-robber recurrence

When choosing a subset with an adjacency restriction, the state is the best result up to each index and the transition is take-or-skip.

Taking an element adds it to the best result two positions back; skipping it inherits the best result one position back.

State is the best over a prefix, not the best ending at i.

prev2 = prev1 = 0
for v in a:
    prev2, prev1 = prev1, max(prev1, prev2 + v)
return prev1

# [2, 7, 9, 3, 1] -> 12 (2 + 9 + 1)

Interview trap. Comparing only the two immediately preceding values without carrying the running best breaks when the optimal solution skips several elements.

Engineering practice. Define the state as the best over a prefix rather than as the value ending at the index, and check which of the two the recurrence needs.

ending-here versus best-so-far

Many one-dimensional problems need two quantities: the best solution ending exactly at the current index, and the best seen anywhere.

The ending-here value is what the recurrence extends, and the best-so-far value is what the answer reports; conflating them breaks either the extension or the answer.

Two quantities; reporting the wrong one gives the wrong answer.

ending_here = best = a[0]
for v in a[1:]:
    ending_here = max(v, ending_here + v)   # what the recurrence extends
    best = max(best, ending_here)           # what the answer reports

Interview trap. Reporting the final ending-here value as the answer gives the best solution that ends at the last element, not the best overall.

Engineering practice. Track both explicitly, and name the variables so the difference is visible.

maximum subarray

Kadane's algorithm computes the maximum subarray sum in one pass by deciding at each element whether to extend the previous subarray or start a new one.

The decision is local because a negative running sum can never help a later subarray, so discarding it is always at least as good.

Initialise from the first element, not from zero.

a = [-3, -1, -2]
# best = 0 initialiser -> 0 (wrong, no empty subarray allowed)
# best = a[0] initialiser -> -1 (correct)

Interview trap. Initialising the best to zero returns zero for an all-negative array, when the correct answer is the largest single element.

Engineering practice. Initialise from the first element rather than from zero, and test an all-negative input.

the coin-change recurrences

The minimum-coin and count-the-ways versions of coin change need different loop structures, and swapping them changes the answer.

Iterating coins outermost counts combinations; iterating amounts outermost counts permutations, which is a different question.

The loop order decides whether you count combinations or permutations.

# Combinations (order does not matter): coins outermost
for c in coins:
    for amt in range(c, target + 1): dp[amt] += dp[amt - c]

# Permutations (order matters): amounts outermost
for amt in range(1, target + 1):
    for c in coins:
        if c <= amt: dp[amt] += dp[amt - c]

# coins = [1, 2], target = 3 -> 2 combinations, 3 permutations.

Interview trap. Writing the loops in the order that feels natural yields a plausible number that answers the other question entirely.

Engineering practice. Decide whether order matters in the answer, and choose the loop nesting from that rather than from convenience.

unbounded versus zero-one items

Whether an item may be used repeatedly determines the direction of the inner loop in the one-dimensional knapsack formulation.

Iterating capacities upward reuses the current item's already-updated entries, giving unlimited use; iterating downward reads only the previous item's entries, giving at most one use.

The inner loop direction is the whole difference.

for amt in range(c, target + 1): dp[amt] += dp[amt - c]        # unbounded reuse
for amt in range(target, c - 1, -1): dp[amt] += dp[amt - c]    # each item once

Interview trap. Using the upward direction for a zero-one problem silently permits reusing an item, and the answer is too good rather than obviously wrong.

Engineering practice. Match the loop direction to the item semantics, and verify with an instance where reuse would change the optimum.

space optimisation by rolling arrays

When a state depends only on the previous row or the previous few indices, the table collapses to a constant number of arrays or variables.

The reduction changes memory from proportional to the state space to proportional to one slice, without changing the time bound.

Two variables instead of n, at the cost of the reconstruction.

# dp[i] depends only on dp[i-1] and dp[i-2]:
prev2, prev1 = 0, 0
# Memory drops from O(n) to O(1) - and the choice sequence is gone.

Interview trap. Collapsing the table destroys the information needed to reconstruct the solution itself, leaving only its value.

Engineering practice. Collapse only when the value suffices, and keep the full table or a decision record when the solution must be reported.

reconstructing the solution

Recovering which choices produced the optimum requires either the full table or a stored decision per state.

Walking backwards from the final state and asking which predecessor achieved its value reconstructs the sequence in time proportional to its length.

Keep the table or a decision per state.

choice = [None] * (n + 1)
...
choice[i] = "take" if take > skip else "skip"
# Walk backwards from n reading `choice` to recover which items were used.

Interview trap. An ordinary backward walk cannot reconstruct from a space-optimised table, because the intermediate rows it needs no longer exist; recomputation or a specialised divide-and-conquer method is a separate algorithm.

Engineering practice. Decide up front whether the caller needs the value or the choices, and size the memory accordingly.

longest increasing subsequence

The quadratic formulation is a direct recurrence over prefixes, and a patience-sorting variant with binary search brings it to linearithmic time.

The faster version maintains the smallest possible tail for each achievable length, which is monotone and therefore binary searchable.

The tails array gives the length, not the subsequence.

import bisect
tails = []
for v in a:
    i = bisect.bisect_left(tails, v)
    if i == len(tails): tails.append(v)
    else: tails[i] = v
len(tails)      # correct length, O(n log n)

# a = [3, 4, 1] -> tails ends as [1, 4], which is not an increasing subsequence of a.

Interview trap. The tails array is not itself a valid increasing subsequence, so returning it as the answer is wrong even though its length is right.

Engineering practice. Use the tails array for the length and keep predecessor links when the subsequence itself is required.

the complexity of a dynamic program

The running time is the number of states multiplied by the cost of each transition.

This makes the complexity readable directly from the state definition, which is why the state should be written down before the code.

States times transition cost - name both.

# dp[i][w]: n x W states, O(1) transition   -> O(nW)
# dp[i][j] over intervals: n^2 states, O(n) split -> O(n^3)

Interview trap. Quoting the time as the state count alone ignores transitions that loop over a range, which is where the extra factor lives.

Engineering practice. Give the bound as states times transition cost, and name both factors.

pseudo-polynomial complexity

A knapsack solution running in time proportional to the capacity is pseudo-polynomial, not polynomial, because the capacity is exponential in its own encoding length.

The distinction matters because the running time grows with the numeric value of an input rather than with the number of inputs.

O(nW) grows with the value of W, not with its encoding length.

# n = 100 items, W = 1,000        -> 100,000 cells: instant
# n = 100 items, W = 1,000,000,000 -> 10^11 cells: impossible
# Same input size on the page; the knapsack problem is still NP-hard.

Interview trap. Calling the knapsack dynamic program polynomial contradicts the problem's NP-hardness and signals a misunderstanding of the classification.

Engineering practice. Use the term pseudo-polynomial, and note the input magnitude at which the table becomes too large.

state-space explosion

Each additional state dimension multiplies the table size, which is why dynamic programming has a practical ceiling.

A state of index plus remaining budget plus a mode flag is the product of three domains, and the memory is that product times the entry size.

Each dimension multiplies; compute the size before implementing.

# (index 1,000) x (budget 1,000) x (mode 3) = 3,000,000 cells x 8 bytes = 24 MB: fine.
# Add (keys 2^10) and it is 3 x 10^9 cells: not fine.

Interview trap. Adding a dimension to fix a wrong answer without checking the resulting size produces a solution that is correct and unrunnable.

Engineering practice. Compute the state count before implementing, and look for a dimension that can be eliminated by a smarter formulation.

cache keys and hashability

Memoisation requires the state to be hashable and to capture everything the result depends on.

A key that omits a parameter returns a cached result computed under different conditions, which is a wrong answer rather than a cache miss.

Every dependency must be an argument, or the cache lies.

@cache
def f(i, remaining): ...        # pure: safe

@cache
def g(self, i): ...             # depends on self.state, which is not in the key

Interview trap. Memoising a method whose result depends on mutable instance state produces results that depend on call order.

Engineering practice. Make every dependency an explicit parameter, and keep memoised functions pure.

recursion limits in top-down solutions

Top-down dynamic programming recurses to a depth equal to the longest dependency chain, which is often the input size.

A ten-thousand-element input therefore exceeds default recursion limits in several languages before the algorithm's own bounds bite.

The dependency chain is the recursion depth.

@cache
def suffix(i): return 0 if i == len(a) else a[i] + suffix(i + 1)
suffix(0)      # len(a) = 10,000: RecursionError - convert to a loop

Interview trap. Raising the recursion limit turns a clean exception into a process-level crash, since the native stack is unchanged.

Engineering practice. Convert to bottom-up tabulation when the dependency chain is proportional to the input size.

greedy versus dynamic programming

A greedy algorithm is correct only when a local rule is provably optimal, and dynamic programming is the fallback when it is not.

Coin change is the standard example: greedy works for some coin systems and fails for others, while the dynamic program is correct for all.

Coins [1, 3, 4], target 6: greedy gives 3, the optimum is 2.

# Greedy: 4 + 1 + 1 = three coins.
# DP:     3 + 3     = two coins.
# US coin denominations happen to be canonical, which is why greedy looks right.

Interview trap. Assuming greedy works because it does on the sample inputs is the most common source of wrong answers in this area.

Engineering practice. Demand an exchange argument for any greedy claim, and use dynamic programming when none is available.

verifying against brute force

A dynamic program's recurrence is best validated by comparing it with exhaustive search on small random inputs.

The defects — a missed transition case, a wrong base case, an off-by-one in the state — all show up as differing answers on inputs small enough to enumerate.

Random small inputs against exhaustive search find the missed case.

for _ in range(5_000):
    a = [random.randint(-5, 5) for _ in range(random.randint(0, 8))]
    assert dp_solution(a) == brute_force(a)

Interview trap. Testing on the provided examples validates the examples, not the recurrence, and these defects are specifically the kind examples miss.

Engineering practice. Write the brute-force reference first and run randomised comparison before optimising anything.

numeric overflow in counting problems

Counting dynamic programs overflow quickly, which is why such problems usually specify a modulus.

Applying the modulus at every addition keeps values bounded; applying it only at the end is too late in fixed-width arithmetic.

Reduce at every operation, and normalise subtractions.

MOD = 10 ** 9 + 7
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD          # every step
diff = (a - b) % MOD                            # Python: already non-negative
# In C/Java: ((a - b) % MOD + MOD) % MOD

Interview trap. Taking the modulus of a subtraction can produce a negative value in languages where the operator follows the sign of the dividend.

Engineering practice. Reduce at every operation, and normalise subtractions by adding the modulus before reducing.

recognising a dynamic-programming problem

The signals are a request for a count or an optimum, a sequence of decisions, and a compact state that summarises the decisions already made.

If the answer is an enumeration, backtracking fits; if a local rule is provably optimal, greedy fits; if the state is compact and reused, dynamic programming fits.

If the state does not fit in a sentence, it is probably not a DP.

Signal	Fit
Count or optimum over a sequence of decisions	yes
Compact state that summarises the past	yes
Enumerate every configuration	backtracking
A provable local rule	greedy

Interview trap. Reaching for dynamic programming because the problem sounds hard produces an over-complicated solution to a problem with a direct greedy or two-pointer answer.

Engineering practice. Try to define the state in one sentence; if that is difficult, the problem is probably not a dynamic program.