Dynamic Programming Patterns: One Template for Most Problems

For a long time I treated every dynamic programming problem as a brand-new puzzle. Then I noticed something: most dynamic programming patterns reduce to the same four-step template. Once you see the pattern, the problems that used to feel impossible start to look like variations of a few familiar shapes.

This post walks through the core dynamic programming patterns using one repeatable template, then applies it to three classic problems so you can see the pattern in action. If you want the underlying theory of state and transitions first, read our deeper guide on how dynamic programming actually works. Here the focus is recognizing and reusing dynamic programming patterns.

Why Dynamic Programming Patterns Matter

Dynamic programming feels hard because people memorize solutions instead of learning the pattern. A pattern is reusable; a memorized solution is not. When you learn the dynamic programming patterns behind a problem, you can derive the solution under pressure instead of recalling it. That is the difference between freezing in an interview and reasoning your way to an answer.

Almost every DP problem is built from the same skeleton: a state that captures a subproblem, a recurrence that builds bigger answers from smaller ones, a base case, and a final answer. Learn that skeleton once and most dynamic programming patterns become recognizable.

The Universal Dynamic Programming Template

Step 1: Define the State

The state is the smallest description of a subproblem whose answer you can reuse. For sequence problems it is often dp[i], the answer considering the first i elements. Naming the state precisely is the single most important step in every dynamic programming pattern.

Step 2: Find the Recurrence

The recurrence expresses dp[i] in terms of smaller states like dp[i-1]. This transition is the heart of the dynamic programming pattern: it says how the optimal solution for a bigger problem is assembled from optimal answers to smaller ones.

Step 3: Set the Base Case

The base case is the smallest state whose answer you know outright, such as dp[0]. Without it the recurrence has nothing to build on.

Step 4: Determine the Answer

Finally, decide which state holds the answer. Sometimes it is dp[n], sometimes the maximum across all states. Naming it explicitly keeps the dynamic programming pattern honest.

Pattern in Action: Climbing Stairs

Climbing Stairs is the cleanest example of a linear dynamic programming pattern. State: dp[i] is the number of ways to reach step i. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Base case: dp[0] = dp[1] = 1. Answer: dp[n].

def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Same four steps, nothing memorized. This linear sequence shape is one of the most common dynamic programming patterns you will meet, and the brute force version that recomputes every call is exponential until the template caches it.

Pattern in Action: Coin Change

Coin Change shows the unbounded knapsack dynamic programming pattern. State: dp[x] is the fewest coins to make amount x. Recurrence: dp[x] = min(dp[x], dp[x-c] + 1) for each coin c. Base case: dp[0] = 0. Answer: dp[amount].

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for x in range(c, amount + 1):
            dp[x] = min(dp[x], dp[x-c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Different problem, identical template. Recognizing this knapsack pattern saves you from reinventing it every time and turns a brute force search into a clean optimal solution.

Pattern in Action: Longest Increasing Subsequence

Longest Increasing Subsequence is the subsequence dynamic programming pattern. State: dp[i] is the length of the longest increasing subsequence ending at index i. Recurrence: dp[i] = max(dp[i], dp[j] + 1) for every j before i with nums[j] less than nums[i]. Base case: every dp[i] starts at 1. Answer: the maximum value across dp.

def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Three different problems, one dynamic programming template. That is the whole point of learning dynamic programming patterns instead of solutions.

Recognizing Dynamic Programming Patterns

How do you know a problem is DP in the first place? Two signals. First, the problem asks for an optimal value, a count of ways, or a yes-or-no over many choices. Second, the choices overlap, so the same subproblem is solved repeatedly. When both hold, the brute force solution is exponential and a dynamic programming pattern delivers the optimal solution efficiently.

Most interview DP falls into a handful of pattern families: linear sequence like Climbing Stairs, knapsack and subset sums like Coin Change, subsequence problems like Longest Increasing Subsequence, and grid or interval problems. Map a new question to one of these dynamic programming patterns and the template does the rest.

Common Dynamic Programming Pattern Families

It helps to keep a short mental catalog of dynamic programming pattern families so a new question snaps to a known shape. In every case the brute force approach re-explores the same choices and runs in exponential time; the dynamic programming pattern caches subproblem answers and recovers the optimal solution in polynomial time.

The knapsack family decides what subset of items to take under a constraint, like Coin Change or Partition Equal Subset Sum. The grid family walks a matrix accumulating an optimal solution, like Unique Paths or Minimum Path Sum, where dp[i][j] depends on the cells above and to the left. The interval family builds answers over ranges, like Matrix Chain Multiplication or Burst Balloons. The two-sequence family compares two strings, like Edit Distance, Longest Common Subsequence, and Shortest Common Supersequence, where dp[i][j] compares prefixes of each input and the brute force alternative explores every alignment.

You do not need hundreds of problems to internalize these families. Most dp patterns leetcode lists group questions by exactly these shapes, so once you solve two or three per family the brute force instinct fades and reaching for the optimal solution becomes automatic. The shortest common supersequence problem, for instance, is just longest common subsequence with one extra step, which is obvious once you see the shared dynamic programming pattern.

Memoization vs Tabulation

Every dynamic programming pattern can be written top-down with memoization or bottom-up with tabulation. Memoization caches recursive results and is often easier to write from the recurrence directly.

from functools import lru_cache

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

Tabulation, the array version shown above, avoids recursion overhead and makes space optimization obvious. Pick whichever expresses the dynamic programming pattern most clearly; they compute the same optimal solution.

Dynamic Programming Patterns for Coding Interviews

In an interview, do not jump to code. State the dynamic programming pattern out loud: define the state, write the recurrence, give the base case, name the answer. Mention that the brute force version is exponential and that the pattern recovers the optimal solution, because that framing shows the interviewer you understand the pattern, not just a memorized snippet. Then practice these dynamic programming patterns on Climbing Stairs, Coin Change, Longest Increasing Subsequence, House Robber, and Edit Distance. For the foundations behind state and transition, see our guide on how dynamic programming works, and explore more breakdowns on the Levelop blog.