13.1 Introduction to Dynamic Programming

Prerequisites: Recursion, Divide and Conquer, and Backtracking. This lesson begins with the repeated function calls in the Fibonacci sequence to establish key concepts (state, transition, boundaries, and computation order) and validates the model through examples like the staircase climbing problem and the house selection problem.

Compute Each State Once

Different choice paths can reach the same state. Naive recursion repeats the remaining computation; memoization saves the first answer and reads it on later visits.

Dynamic programming is well-suited for problems with overlapping subproblems; if the current solution also depends on combining smaller sub-solutions, then both the state and the transition logic must be clearly defined. A typical workflow includes:

1. State: What do the function parameters or table indices represent?
2. Transition: Which smaller states does the current state depend on?
3. Boundary: Which states can be answered directly without further computation?
4. Order: Dependencies must be resolved before the current state is processed.
5. Answer: Which state holds the final result, and is it necessary to reconstruct the solution path?

Having recursion is not enough for dynamic programming. Using an array alone isn't sufficient either. The core idea is that each state’s answer is computed only once, and the transition rules cover all valid choices.

Fibonacci: Two Directions of the Same Transition

The first three functions require a non-negative integer n. The last accepts an iterable of non-negative integers, consumes it once, and allows selecting nothing; empty input returns 0. Invalid numeric inputs raise ValueError.

from functools import lru_cache

def _require_non_negative(n):
    if not isinstance(n, int) or n < 0:
        raise ValueError("n must be a non-negative integer")

def fib_top_down(n):
    _require_non_negative(n)

    @lru_cache(maxsize=None)
    def solve(index):
        if index < 2:
            return index
        return solve(index - 1) + solve(index - 2)

    return solve(n)

def fib_bottom_up(n):
    _require_non_negative(n)
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

def climb_stairs(n):
    """Count ways to take 1 or 2 steps; an empty staircase has one empty path."""
    _require_non_negative(n)
    previous, current = 1, 1  # ways(0), ways(1)
    for _ in range(n):
        previous, current = current, previous + current
    return previous

def max_non_adjacent_sum(values):
    """Find a non-adjacent sum of non-negative integers; allow an empty choice."""
    skip, take = 0, 0
    for value in values:
        if not isinstance(value, int) or value < 0:
            raise ValueError("values must be non-negative integers")
        skip, take = max(skip, take), skip + value
    return max(skip, take)

if __name__ == "__main__":
    for n in range(101):
        assert fib_top_down(n) == fib_bottom_up(n)

    assert fib_bottom_up(50) == 12_586_269_025
    assert climb_stairs(0) == 1
    assert climb_stairs(1) == 1
    assert climb_stairs(10) == 89
    assert max_non_adjacent_sum([2, 7, 9, 3, 1]) == 12
    assert max_non_adjacent_sum([]) == 0
    print("DP introduction checks passed")

Top-down evaluation follows dependencies from the target; in this single-threaded code, each index is expanded once. Bottom-up evaluation iterates from base cases toward the target. Counting each addition as constant time, both take Θ(n+1) time. Memoization keeps O(n+1) cache entries and O(n+1) stack frames; iterative Fibonacci retains two adjacent states. The cache is local to each public call: fib_top_down(51) does not reuse results from an earlier fib_top_down(50). The lru_cache documentation explains that maxsize=None leaves the entry count unbounded.

Python integers can grow dynamically in memory. Java int will overflow early in Fibonacci computations, and long can only support a limited range of indices; for higher precision, use BigInteger or explicitly apply modular arithmetic. F(n) has Θ(n) bits. Counting memory in bits, the iterative version retains Θ(n) bits of integers, while caching all results takes Θ(n²) bits. With linear-time big-integer addition, both versions spend Θ(n²) time on additions in total. Two states do not mean constant-bit memory.

How to Derive State from Recursive Parameters

The result of a naive Fibonacci function depends only on n, so n is sufficient to represent the state. If the result also depends on the current position, remaining capacity, or another string index, those quantities must be included in the cache key or DP dimension. Omitting any one of them will cause different subproblems to be incorrectly merged.

Conversely, if a parameter does not influence the outcome of future computations, it should not be included in the state. Extra dimensions increase both time and space complexity and may obscure the true transition relationships between states.

Overlapping Subproblems

fib(n-1) and fib(n-2) both trigger further requests to fib(n-3). This is a classic case of overlapping subproblems, identical parameters reappearing in multiple recursive calls. In contrast, divide-and-conquer algorithms like merge sort process disjoint intervals (left and right halves), so there's no need to cache identical subintervals.

Optimal Substructure

For non-adjacent item selection, define the state as "the maximum sum after processing the first i items." The formula below numbers items from 1. Item i has two choices:

Skip house i: best[i-1]
Choose house i: best[i-2] + value[i]

Set best[0]=0 and treat the nonexistent prefix before item 1 as 0. In the code, skip is the best sum with the previous item omitted, and take is the best sum with it selected; the initial zeros represent an empty prefix. Python evaluates the right side before assigning either variable, so the new take reads the old skip. Taking the maximum of the two choices is sufficient because they cover all valid configurations, and each relies on the optimal solution of its corresponding prefix. Optimal substructure isn't just a slogan; it's the rigorous argument that if a subproblem's solution is suboptimal, it can be replaced to improve the overall result.

Why Table Orientation Affects the Answer

If dp[i] depends on dp[i-1], the computation must proceed from smallest to largest. The same principle applies to two-dimensional tables: first draw the arrows indicating dependencies, then determine the direction of iteration. Caution is especially required during space compression, as writes in the current iteration may overwrite values still needed from the previous iteration.

Top-down approaches typically only access states that are reachable from the target, but are constrained by recursion depth. Bottom-up methods avoid recursion stacks but may compute states that are ultimately unused. The engineering choice depends on the sparsity of the state graph, its depth, constant overhead, and the requirements for reconstructing paths.

Common Order for Debugging Errors

1. Write a complete sentence describing the state meaning, including "the first few items" and whether the capacity is exactly matched or merely not exceeded.
2. List all valid choices, ensuring no transitions are missed and no elements are reused.
3. Handle the empty input and minimal input cases separately to establish baseline behavior.
4. Draw dependency arrows to verify there are no cyclic dependencies and that compressed updates preserve needed values.
5. Use small-scale brute-force enumeration as an oracle, then validate against random inputs.
6. If you need to reconstruct the solution path, store parent choices in addition to the final result, never keep only the final value.

Build the States

1. Count the number of distinct parameter values actually expanded by fib_top_down.
2. Modify max_non_adjacent_sum to return the selected indices as well as the sum.
3. If property values can be negative, what are the differences in boundary conditions between "select none" and "select at least one"?
4. Write out the state and boundary conditions for the grid path counting problem, then determine whether it can be compressed into a one-dimensional representation.
5. Compare the two business semantics implied by climb_stairs(0) returning 0 versus 1.

State Definitions Determine What Can Be Reused

Dynamic programming is not about "converting recursion into arrays." It's about establishing a unique meaning for reusable states. Once the state, transition, boundary conditions, and evaluation order are consistent, memoization and tabulation are merely different directions of computation.

Next, we move into 0-1 Knapsack, LCS, and Edit Distance, extending one-dimensional states to capacity and handling two sequences.