Dynamic Programming Pattern: Template + 481 LeetCode Problems

What the dynamic programming pattern is

Dynamic programming applies when a problem has optimal substructure — the best answer is built from the best answers to smaller versions — and overlapping subproblems, meaning the naive recursion asks the same question many times. The work is entirely in the first line: choosing a state, the smallest set of numbers that fully describes a subproblem. Everything else follows, because the transition is just the answer to "what were the last choices that could have led here?" and the base case is the state small enough to answer without recursing. Write it as recursion with a cache first; that version is easier to get right because the transition reads like the problem statement. Convert to a bottom-up table only once it works, and only for the two things a table buys: no recursion limit, and the chance to notice that row i depends only on row i-1, which is what collapses an O(n·m) table into O(m) space.

When to use it

• —The problem asks for a count, a maximum, a minimum, or whether something is possible — not for the arrangement itself.
• —A greedy choice is provably wrong because a locally worse choice can lead to a better total.
• —The naive recursion is exponential and its calls repeat with identical arguments.
• —The input has an obvious ordering — a prefix, an index range, a remaining capacity — to index the state by.

The dynamic programming template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 481 problems listed below.

def rob(nums):
    """The canonical 1-D shape: dp[i] is the answer for the prefix nums[:i]."""
    if not nums:
        return 0

    dp = [0] * (len(nums) + 1)
    dp[1] = nums[0]                                   # base case

    for i in range(2, len(nums) + 1):                 # transition
        dp[i] = max(dp[i - 1],                        # skip nums[i - 1]
                    dp[i - 2] + nums[i - 1])          # take it, so skip its neighbour

    return dp[len(nums)]

Complexity characteristics

Time

O(states × transitions)

Auxiliary space

O(states), frequently reducible

The running time is the number of distinct states multiplied by the work done at each one, which is why choosing the state is the whole problem: a one-dimensional state over a prefix gives O(n), a two-dimensional state over two strings gives O(n·m), and a bitmask state over n items gives O(2ⁿ·n). Memoised recursion and a bottom-up table share the same complexity and differ only in constant factors and stack depth. The space often collapses — when row i depends only on row i−1, an O(n·m) table becomes O(m).

All 481 dynamic programming LeetCode problems

Every problem in the library the dynamic programming pattern applies to, grouped by LeetCode's own difficulty rating. 416 of the 481 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Dynamic Programming pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.