Dynamic Programming

What it is

Dynamic programming (DP) solves a problem by defining smaller subproblems, solving each once, and reusing their answers. It applies when different decision paths reach the same subproblem and a larger answer can be constructed from smaller answers.

A naive recursive search may explore exponentially many decision sequences. DP merges paths that have the same relevant state. For example, many sequences of choices can leave the same remaining resource total; their future possibilities depend on that total, not on the full history.

The crucial step is defining a state: enough information to determine future choices, but no irrelevant history. Depending on the objective, each state stores a minimum cost, maximum reward, count of constructions, or Boolean feasibility.

DP does not always produce a polynomial-time algorithm. A subset-based DP can still have exponentially many states, while improving substantially over enumerating every permutation.

How to recognize it

Look for these signals:

• The objective is to minimize, maximize, count, or decide feasibility across many choices.
• Choices process a sequence, consume a resource, split an interval, or build a subset.
• Different partial solutions can have identical future possibilities.
• A small summary of the past determines which choices are legal next.
• Constraints suggest an array indexed by position, amount, interval endpoints, or a bitmask is affordable.

Common wording includes “exactly this total,” “at most one per group,” “nonoverlapping,” “switching cost,” and “subject to prerequisite constraints.” These are clues, not proof: the recurrence must still account for every legal solution.

The core technique

1. Define states and choose an evaluation order

Write down five things before coding:

1. What each state means.
2. Which smaller states it depends on.
3. How candidate answers combine.
4. The base cases and unreachable-state value.
5. An order that evaluates dependencies first.

For minimization, unreachable states usually contain positive infinity; for maximization, negative infinity. Counting states usually start at zero.

Top-down memoization follows the recurrence recursively and caches results. Bottom-up tabulation evaluates states explicitly in dependency order. They implement the same mathematical idea; memoization can avoid unused states, while tabulation avoids recursion-depth limits.

This memoized recurrence minimizes the number of reusable positive-sized choices needed for an exact total:

from functools import cache

sizes = tuple(sizes)  # Every size must be positive.

@cache
def best(remaining):
    if remaining == 0:
        return 0
    return min(
        (1 + best(remaining - s)
         for s in sizes if s <= remaining),
        default=float('inf'),
    )

Every transition reduces the remaining amount, so dependencies cannot cycle. Return an impossible-result indicator if the target remains infinite.

2. Sequence and finite-state DP

Use prefix DP when decisions consume an ordered sequence. Define dp[i] as the best answer for the first i items. If legal packages cover either one item or two adjacent items, compare a transition from dp[i-1] with one from dp[i-2], adding the relevant package cost.

Sometimes the prefix alone is insufficient. If each position has two options and switching incurs a fee, track the best total ending in each option. The next cost for option A is its local cost plus the minimum of staying in A or switching from B. Compute both new values from the previous pair before replacing either.

A useful distinction is ending here versus best so far. For maximum contiguous sums, an ending-here state either extends the previous segment or starts a new one. A separate prefix-best state remembers the best segment anywhere so far:

def prefix_max_sums(values):
    ending = best = values[0]  # Requires nonempty input.
    answers = [best]
    for x in values[1:]:
        ending = max(x, ending + x)
        best = max(best, ending)
        answers.append(best)
    return answers

More elaborate state machines add dimensions. For transaction decisions, maintain flat and holding states indexed by exact completed transaction count. Define when that count increases, and read transitions only from the previous day. Initialize impossible counts accordingly.

For weighted nonoverlapping intervals, sort by finishing time. Each prefix chooses between skipping the newest interval and taking it after a compatible predecessor. Binary search finds that predecessor. A limited-use rule change can be represented by additional budget layers, with transitions distinguishing ordinary actions from budget-consuming ones.

3. Resource and counting DP

Use an amount-indexed state when choices consume discrete resources. Distinguish exactly an amount from at most an amount: their initialization and final answer selection differ.

For grouped choices, where at most one option may be selected from each group, isolate each group's transitions. Read from the old array and write to a new one:

def grouped_rewards(groups, capacity):
    neg_inf = float('-inf')
    dp = [neg_inf] * (capacity + 1)
    dp[0] = 0
    for group in groups:
        nxt = dp[:]  # Skip this group.
        for used, reward in enumerate(dp):
            if reward == neg_inf:
                continue
            for cost, gain in group:
                if used + cost <= capacity:
                    nxt[used + cost] = max(
                        nxt[used + cost], reward + gain
                    )
        dp = nxt
    return dp  # Best reward for each exact total.

For ordinary knapsack, loop direction controls reuse: descending amounts prevent reusing a single item; ascending amounts allow reusable positive-sized choices.

Counting DP adds predecessor counts rather than taking minima or maxima. If valid predecessors form a contiguous range, prefix sums turn that range sum into a constant-time transition. This often appears when building bounded integer sequences whose allowed values vary by position. If a modulus is required, apply it consistently, including after subtraction.

4. Interval and subset DP

Interval DP uses states such as dp[l][r] for a contiguous range. Evaluate shorter intervals first. Transitions often split at an internal boundary or combine endpoint decisions. If interactions cross a subproblem boundary, endpoints alone may be insufficient: add the context needed to evaluate that interaction, such as a carried count of matching elements.

Subset DP records which elements have been used, commonly as a bitmask. When transition cost depends on the latest element, use dp[mask][last]. Add an unused element only when its prerequisites are already in the mask.

To count optimal constructions as well as optimize cost, store a cost and count together. A better candidate replaces both; an equal-cost candidate adds its count. Initialize each valid starting construction once.

Common mistakes

• Defining a state that omits information needed by future decisions.
• Initializing unreachable exact-total states to zero.
• Updating in place when transitions require a previous day, group, or layer.
• Using the wrong amount-loop direction and accidentally allowing reuse.
• Mixing empty and nonempty solutions, especially with negative rewards.
• Miscomputing compatibility boundaries or ignoring prerequisite legality.
• Compressing storage before understanding dependencies, making reconstruction or correctness harder.

Complexity

Estimate number of states × work per state, including preprocessing.

• Sequence DP with constant-sized state: typically O(n) time and O(1) auxiliary space, excluding stored outputs.
• Resource DP with target A and m choices: often O(mA) time and O(A) space. This is pseudo-polynomial in numeric input values.
• Weighted interval scheduling: typically O(n log n) time and O(n) space.
• Interval DP with all split points: commonly O(n³) time and O(n²) space; added context dimensions increase these costs.
• Subset-and-last DP: commonly O(n² 2^n) time and O(n 2^n) space.

Memoization stores reached states plus the recursion stack. Rolling arrays save space only when older layers are no longer needed.