I Solved 3 DP Problems With the Exact Same Template. Here It Is.

I've been breaking down coding patterns that used to intimidate me, writing about them as I go. This one's about dynamic programming, and specifically about the moment I realized I'd been overcomplicating it for years.

I Used to Treat Every DP Problem Like a New Puzzle

For the longest time, dynamic programming felt like guesswork. I'd see a problem, stare at it, try to figure out some clever recurrence, and either get it or not. There was no system. Every problem felt like starting from scratch.

I'd read solutions on LeetCode and think "how was I supposed to come up with that?" The recurrence relations looked like they fell out of the sky. And the explanations always started with the answer and worked backwards, which is the opposite of how my brain actually approaches things.

The turning point came when I stopped trying to learn DP "problems" and started looking at DP as a process. I wrote about this shift in my earlier post on dynamic programming as state + transition, where I argued that DP isn't about memorization. It's about defining states and transitions.

But knowing that conceptually and actually having a repeatable process are two different things. So I set out to find a DP template I could apply to LeetCode problems consistently. And I did.

The 4-Step Dynamic Programming Template

Every dynamic programming problem I've solved since then follows these four steps. Not loosely. Not "kind of." Literally the same four questions, in the same order, every time.

Step 1: Define the State

What does dp[i] represent? This is the hardest step because it requires you to decide what "progress" means for this problem. The state has to capture enough information that you can make decisions going forward without looking back at anything else.

A good state definition is one sentence. If you can't describe what dp[i] means in plain English, you don't have the right state yet.

Step 2: Find the Recurrence

How does dp[i] relate to previously computed states? This is where you express the "choice" at each step. You're answering: "If I already know the answers for all smaller versions of this problem, how do I combine them to get the answer for this version?"

The recurrence is almost always a min, max, or sum over some set of previous states.

Step 3: Set the Base Case

What are the trivially small inputs where you know the answer without computing anything? dp[0] is usually the starting point. Sometimes dp[1] too. These ground the entire computation. Get them wrong and everything cascades.

Step 4: Determine the Answer

Where in the DP table is your final answer? It's not always the last cell. Sometimes it's the max across the entire array. Sometimes it's a specific corner of a 2D table. This step is easy to forget, and forgetting it is a surprisingly common bug.

That's it. Four steps. Let me show you how the same four steps solve three very different dynamic programming problems.

Problem 1: Climbing Stairs

You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top? This is LeetCode #70 and probably the first dynamic programming problem most people encounter. Here's the template applied:

Step 1 (State): dp[i] = the number of distinct ways to reach step i.

Step 2 (Recurrence): To reach step i, I either came from step i-1 (took 1 step) or step i-2 (took 2 steps). So dp[i] = dp[i-1] + dp[i-2].

Step 3 (Base case): dp[0] = 1 (one way to stand at the ground: do nothing). dp[1] = 1 (one way to reach step 1: take one step).

Step 4 (Answer): Return dp[n].

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

Clean. Simple. You might recognize this as the Fibonacci sequence, and that's not a coincidence. Fibonacci IS a dynamic programming problem. The recurrence dp[i] = dp[i-1] + dp[i-2] is the same. What the template gave us was a structured way to arrive there instead of just recognizing it.

Time complexity: O(n). Space: O(n), though you could optimize to O(1) since you only ever look back two steps.

Problem 2: Coin Change

Given coins of different denominations and a total amount, find the minimum number of coins needed to make that amount. If it's impossible, return -1. This is LeetCode #322. A completely different problem. Same dynamic programming template.

Step 1 (State): dp[i] = the minimum number of coins needed to make amount i.

Step 2 (Recurrence): For each coin denomination c, if I use that coin, I need dp[i - c] + 1 coins total (the +1 is for the coin I just used). I want the minimum across all coin choices: dp[i] = min(dp[i - c] + 1) for all coins c where c <= i.

Step 3 (Base case): dp[0] = 0 (zero coins needed to make amount 0). Everything else starts at infinity (meaning "impossible so far").

Step 4 (Answer): Return dp[amount] if it's not infinity, otherwise -1.

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

Notice what changed between Climbing Stairs and Coin Change. The four steps are identical in structure. The only real difference is in Step 2: what "choices" are available at each state. For Climbing Stairs, the choices were "1 step or 2 steps." For Coin Change, the choices are "which coin to use." The dynamic programming template absorbed that difference without breaking.

Time complexity: O(amount * len(coins)). Space: O(amount).

Problem 3: Longest Increasing Subsequence

Given an array of integers, find the length of the longest strictly increasing subsequence. This is LeetCode #300. It's a significant step up from the first two because the recurrence looks back at ALL previous indices, not just one or two. But the dynamic programming template still works.

Step 1 (State): dp[i] = the length of the longest increasing subsequence that ENDS at index i.

That "ends at" part is crucial. I got this wrong the first time. I tried defining dp[i] as "the LIS in the first i elements" and couldn't write a recurrence. Changing the state definition to "ending at i" made the recurrence fall out naturally.

Step 2 (Recurrence): For each previous index j < i, if nums[j] < nums[i], then I could extend the subsequence ending at j by appending nums[i]. So dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i].

Step 3 (Base case): dp[i] = 1 for every index (every single element is a valid subsequence of length 1).

Step 4 (Answer): Return max(dp). Not dp[n-1]. The longest increasing subsequence could end at ANY index, not necessarily the last one. This is the step that catches people off guard.

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

Time complexity: O(n^2). Space: O(n). There's an O(n log n) solution using patience sorting, but that's a different technique entirely. The dynamic programming approach here is what interviewers typically expect you to walk through first.

The Dynamic Programming Template Side by Side

Here's all three problems laid out next to each other. The structure never changes. What changes is the meaning you assign to the state and the choices you make in the recurrence. That's it.

How to Solve Dynamic Programming Problems With This Template

Recognizing When a Problem Is DP

Look for these signals in the problem statement: the problem asks for an optimal value (minimum, maximum, longest, shortest) or a count (number of ways, how many). The problem has overlapping subproblems, meaning the same smaller problem gets solved multiple times if you use brute force. And the problem has optimal substructure, meaning the optimal solution to the whole problem contains optimal solutions to its parts.

Common keywords: "minimum cost," "maximum profit," "number of ways," "is it possible to," "longest/shortest."

When You Need to Expand the Template

Some problems need a 2D state. Knapsack has dp[i][w] where i is the item index and w is the remaining capacity. Edit distance has dp[i][j] for positions in two strings. Grid problems have dp[row][col].

The template still works. You're just defining state, recurrence, base case, and answer in two dimensions instead of one. The mental process is identical.

Memoization vs. Tabulation

Everything I showed above uses tabulation (bottom-up, filling the table iteratively). You can also do the same thing top-down with memoization:

from functools import lru_cache

def climb_stairs_memo(n: int) -> int:
    @lru_cache(maxsize=None)
    def dp(i):
        if i <= 1:
            return 1
        return dp(i - 1) + dp(i - 2)
    return dp(n)

Same template, different execution order. In interviews, I usually start with the memoized version because it maps more naturally to how I think about the problem (top-down, starting from what I want to compute). Then I mention the tabulation version as an optimization that avoids the overhead of recursive function calls.

Practice Problems

If the template clicked for you, try these. I've ordered them by how much the recurrence changes from the basic patterns above:

1. House Robber (LeetCode #198). Very similar to Climbing Stairs. The recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
2. Minimum Path Sum (LeetCode #64). Grid version of the template. 2D state, but the recurrence is straightforward.
3. Word Break (LeetCode #139). State is a boolean. Recurrence checks all possible word splits.
4. Partition Equal Subset Sum (LeetCode #416). Knapsack variant. Forces you to think about 2D states.
5. Edit Distance (LeetCode #72). Two strings, 2D table, three choices per cell. The full expansion of the template.

For each one, try filling out the four steps on paper before writing any code. State, recurrence, base case, answer. If you can fill those in, the code writes itself. This is the same DP template that works on LeetCode, HackerRank, and in live coding interviews.

The problems in this post came from a pattern-based approach to interview prep that I've been working through on Levelop. The idea of practicing by pattern rather than by random problem selection is what made DP finally click for me.