Dynamic Programming Patterns

So you sat down to solve a DP problem. You stared at it. You had no idea where to even begin. That feeling is normal. It is the real pain with dynamic programming. Every problem looks brand new, like you have never seen anything like it.

Here is the good news. Most DP problems are not new at all. They fall into a handful of shapes that keep coming back. Once you learn those shapes, a new problem stops feeling scary. You look at it and think, “ah, this is just that pattern again.”

This page is your map of those shapes. We call them DP patterns, which just means common problem types that all get solved in a similar way. For each one I will give you the signal that tells you “this is the pattern” and one example problem. Keep this page open while you practice. Over time the signals start to jump out at you on their own.

🧭 Why patterns matter

Think about how you learned to ride a bike. The first time, every wobble felt like a new disaster. After a week, your body just knew what to do. You stopped thinking about each move.

DP is the same. The patterns are the muscle memory. Here is what they give you.

• You spend less time stuck. You match the problem to a known shape instead of inventing from zero.
• You know what your DP state should be. Each pattern has a usual way to describe the state.
• You catch yourself faster. If your idea does not fit any known shape, that is a hint you read the problem wrong.

🗺️ The patterns at a glance

Here is the whole map in one table. Read the signal column slowly. That is the part you want to remember.

Now let us walk through each one. Slow and friendly.

1️⃣ 1D DP

This is the gentlest pattern, so we start here. In 1D DP you keep one row of answers, one value per step. The answer at a step depends only on a few steps right before it.

The signal looks like this.

• The problem moves along a line. Stairs, days, houses in a row.
• The answer at position n leans on position n minus 1, maybe n minus 2.
• There is no second thing changing at the same time. Just the position.

The classic example is Fibonacci. Each number is the sum of the two before it. Climbing Stairs is the same idea in a different form. You can climb one or two steps. So the ways to reach step n equal the ways to reach n minus 1 plus the ways to reach n minus 2.

House Robber adds a tiny twist. You cannot rob two houses next to each other. So at each house you choose. Skip this one and keep the best so far, or take this one and add the best from two houses back. Same shape, one small choice baked in.

Here is Climbing Stairs so the shape feels real. We build up the answer step by step from the bottom.

#include <stdio.h>

// ways to reach step n, taking 1 or 2 steps at a time
int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1; // ways to reach step 1
    int prev1 = 2; // ways to reach step 2
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2; // depends on two steps back
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    printf("Ways to climb 5 stairs: %d\n", climbStairs(5));
    return 0;
}

Ways to climb 5 stairs: 8

#include <iostream>
using namespace std;

// ways to reach step n, taking 1 or 2 steps at a time
int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1; // ways to reach step 1
    int prev1 = 2; // ways to reach step 2
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2; // depends on two steps back
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    cout << "Ways to climb 5 stairs: " << climbStairs(5) << endl;
    return 0;
}

Ways to climb 5 stairs: 8

public class ClimbingStairs {
    // ways to reach step n, taking 1 or 2 steps at a time
    static int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1; // ways to reach step 1
        int prev1 = 2; // ways to reach step 2
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2; // depends on two steps back
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println("Ways to climb 5 stairs: " + climbStairs(5));
    }
}

Ways to climb 5 stairs: 8

# ways to reach step n, taking 1 or 2 steps at a time
def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2  # ways to reach step 1 and step 2
    for _ in range(3, n + 1):
        curr = prev1 + prev2  # depends on two steps back
        prev2, prev1 = prev1, curr
    return prev1

print("Ways to climb 5 stairs:", climb_stairs(5))

Ways to climb 5 stairs: 8

// ways to reach step n, taking 1 or 2 steps at a time
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1; // ways to reach step 1
  let prev1 = 2; // ways to reach step 2
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2; // depends on two steps back
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

console.log("Ways to climb 5 stairs:", climbStairs(5));

Ways to climb 5 stairs: 8

2️⃣ 2D grid DP

Now the problem grows a second dimension. In 2D grid DP you fill a table that looks like a grid of cells. The answer for a cell depends on a few neighbor cells, usually the one above and the one to the left.

The signal looks like this.

• The problem literally talks about a grid, a board, or a matrix.
• You can only move in fixed directions, very often right and down.
• To reach a cell you must have come from a neighbor cell.

Unique Paths is the friendly starter. A robot sits top-left and wants to reach bottom-right, moving only right or down. The number of ways to reach a cell is the ways to reach the cell above plus the ways to reach the cell on the left. That is it.

Min Path Sum is the same grid with a cost on each cell. Now you want the cheapest path, not the count of paths. So instead of adding the two neighbors, you take the smaller of the two and add the current cell cost. Same grid shape, different combine step.

Here is the picture of how one cell pulls from its neighbors.

3️⃣ Knapsack-style DP

This pattern is about choices. For each item you ask one question. Do I take it or skip it? In knapsack-style DP you are picking a subset of items to hit some target, like a total weight, a total value, or an exact sum.

The signal looks like this.

• You have a list of items and a target number.
• For each item the choice is take it or skip it.
• You ask things like “can I reach exactly this sum” or “what is the fewest items to reach it”.

Subset Sum is the clean example. Given numbers, can you pick some of them that add up exactly to a target? At each number you branch. Try the target without this number, or subtract this number and try the smaller target. If either branch works, the answer is yes.

Coin Change is the same family. You want to make an amount using coins, and each coin can be used many times. The question shifts to “fewest coins”, but the take-or-skip thinking is the same. Walk through every amount from small to large and build up the best answer.

4️⃣ Subsequence DP

A subsequence means you keep the order but you are allowed to drop some elements. You do not have to keep them next to each other. In subsequence DP you compare two sequences, or you look inside one sequence for a hidden order.

The signal looks like this.

• The problem says “subsequence”, not “subarray”. Order stays, gaps are allowed.
• You are comparing two strings or arrays, or finding the longest ordered run in one.
• The answer at each spot depends on smaller prefixes of the input.

Longest Common Subsequence, often shortened to LCS, compares two strings. You walk both strings and at each pair of letters you ask: do they match? If yes, this pair extends the common run. If not, you drop a letter from one side or the other and keep the better result. It naturally becomes a small grid, so it is closely related to 2D grid DP.

Longest Increasing Subsequence, often shortened to LIS, works on one array. You want the longest run of numbers that keep going up, with gaps allowed. For each number you look back at every earlier smaller number and extend the best run ending there.

5️⃣ Interval DP

Last one, and we will keep it short since it shows up less often for beginners. In interval DP you solve a problem over a range, like positions i to j, by splitting that range at some middle point and combining the two halves.

The signal looks like this.

• You work over a range i to j, not just a single position.
• You try every possible split point inside the range.
• The best answer for the whole range comes from joining the best answers of the parts.

Matrix Chain Multiplication is the textbook example. You decide the order to multiply a chain of matrices so you do the least work, and you do that by trying each split. Burst Balloons is another. You pick which balloon to pop last in a range, then solve the left and right sub-ranges.

Interval DP is heavier than the others because you loop over ranges and split points. Just recognize the signal for now. When you meet a “split the range and combine” problem later, you will know which drawer to open.

🧩 What You’ve Learned

• ✅ DP problems mostly fall into a few repeating shapes, so a new problem rarely needs a brand new idea.
• ✅ 1D DP moves along a line and leans on the last few steps, like Climbing Stairs and House Robber.
• ✅ 2D grid DP fills a table where each cell depends on the cell above and the cell to the left, like Unique Paths and Min Path Sum.
• ✅ Knapsack-style DP is take-it-or-skip-it over a target sum, like Subset Sum and Coin Change.
• ✅ Subsequence DP keeps order while allowing gaps, like LCS across two strings and LIS inside one array.
• ✅ Interval DP splits a range at a middle point and combines the parts, like Matrix Chain and Burst Balloons.
• ✅ The fastest way to get good is to read the signal first, name the pattern, then write the state.

🚀 What’s Next?

• Introduction to Dynamic Programming
• Coin Change