Dynamic Programming Patterns: A Practical Guide

A four-step framework

1. Define the state. What smaller question does each DP entry answer? Include enough parameters to distinguish subproblems.
2. Write the transition. Express a state using states that are strictly smaller or already computed.
3. Set base cases. Cover the smallest inputs explicitly, including empty input where appropriate.
4. Choose an evaluation order. Memoization follows recursive dependencies; tabulation fills entries in a topological order of those dependencies.

DP is useful when a problem has optimal substructure and overlapping subproblems. If the same state is recalculated in many recursive branches, caching can reduce exponential exploration to a number of states times the work per state.

Example: climbing stairs

If each move advances one or two steps, let dp[i] be the number of ways to reach step i. The final move came from either i - 1 or i - 2, so dp[i] = dp[i - 1] + dp[i - 2]. The base values are dp[0] = 1 (one way to stay at the start) and dp[1] = 1.

def climb_stairs(n):
    if n < 0:
        return 0
    two_back, one_back = 1, 1
    for _ in range(2, n + 1):
        two_back, one_back = one_back, two_back + one_back
    return one_back

This runs in O(n) time and uses O(1) extra space. The variables only store the two earlier states that the next transition needs.

Common patterns to recognize

• One-dimensional sequence DP: each position depends on nearby positions, as in stair climbing or house robber.
• Grid DP: state coordinates describe a cell; transitions usually come from permitted neighboring cells.
• Knapsack / take-or-skip: state includes an item position and a capacity or target sum. Be careful whether each item can be used once or repeatedly.
• Subsequence DP: state may use two indices, such as prefixes of two strings for edit distance or longest common subsequence.
• Interval DP: state describes a subarray or substring; process shorter intervals before longer ones.
• State-machine DP: add a small state such as holding/not holding a stock to represent the legal condition at each day.

These are organizational patterns rather than recipes. A problem can combine patterns, and the state should be derived from the exact choices and constraints.

Ordering, memoization, and space

Memoization is often easiest to derive because the recurrence mirrors the problem statement. Tabulation avoids recursion depth and makes memory usage visible. To compress space, first check which prior states are still needed; a rolling array is safe only when discarded values cannot be referenced later.

To verify a recurrence, manually compute a tiny input, test boundary cases, and check that every transition reduces the problem or points to an earlier state. Common mistakes include mixing “best value” with “number of ways,” using the wrong iteration direction for 0/1 versus unbounded knapsack, and forgetting that impossible states need a sentinel value.