Dynamic Programming Patterns for Coding Interviews

What Is Dynamic Programming and When Should You Use It?

Dynamic programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems and storing their results to avoid redundant computation. If you’ve ever felt stuck on a LeetCode problem that seems to require brute-forcing every possibility, chances are dynamic programming is the key.

You should reach for DP when a problem exhibits two properties: optimal substructure (the optimal solution can be constructed from optimal solutions of its subproblems) and overlapping subproblems (the same subproblems are solved multiple times). Classic signals include phrases like “minimum cost,” “maximum profit,” “number of ways,” or “longest/shortest” in the problem statement.

In coding interviews in 2026, DP remains one of the most heavily tested topics at companies like Google, Amazon, and Meta. Mastering a handful of recurring patterns will help you recognize and solve the vast majority of DP problems you’ll encounter.

Top-Down (Memoization) vs. Bottom-Up (Tabulation)

There are two fundamental approaches to implementing a DP solution, and understanding both is essential for coding interviews.

Top-Down with Memoization starts from the original problem and recursively breaks it down. You store (memoize) the result of each subproblem in a cache — typically a HashMap or an array — so that when the same subproblem is encountered again, you return the cached result instead of recomputing it.

Bottom-Up with Tabulation works in the opposite direction. You start by solving the smallest subproblems first and iteratively build up to the final answer, filling a DP table along the way. This approach eliminates recursion overhead and is generally more space-efficient.

Which should you use in an interview? Top-down is often easier to write because it mirrors the recursive structure of the problem. Bottom-up is preferred when you need to optimize space or avoid stack overflow on large inputs. Being comfortable with both gives you flexibility to pick the right tool for each problem.

5 Essential Dynamic Programming Patterns

Let’s walk through the five most common DP patterns, each with a Java code example you can practice and adapt.

Pattern 1: Fibonacci-Type (Linear DP)

This is the simplest DP pattern. Each state depends on a fixed number of previous states. Problems include climbing stairs, house robber, and decode ways.

Example — Climbing Stairs (LeetCode 70): You can climb 1 or 2 steps at a time. How many distinct ways can you reach the top?

public int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

Notice how we optimize space from O(n) to O(1) by only keeping track of the two previous values — a technique interviewers love to see.

Pattern 2: 0/1 Knapsack

In this pattern, you make a binary choice for each item: include it or skip it. Variants include subset sum, partition equal subset, and target sum.

Example — 0/1 Knapsack: Given items with weights and values, maximize total value without exceeding capacity W.

public int knapsack(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[] dp = new int[W + 1];

    for (int i = 0; i < n; i++) {
        // Traverse backwards to avoid using same item twice
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

The key insight is iterating the weight dimension backwards when using a 1D array. This ensures each item is only considered once per subproblem — a classic optimization from the 2D table approach.

Pattern 3: Longest Common Subsequence (LCS) / String DP

This pattern compares two sequences and builds a 2D table where dp[i][j] represents the answer for prefixes of length i and j. Problems include LCS, edit distance, and longest palindromic subsequence.

Example — Longest Common Subsequence (LeetCode 1143):

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

When characters match, we extend the previous diagonal result. When they don’t, we take the best of skipping either character. This two-dimensional decision framework appears in dozens of interview problems.

Pattern 4: Grid Traversal

Grid DP problems involve navigating a 2D matrix, usually from the top-left to the bottom-right corner. Each cell’s value depends on its neighbors. Classic problems include unique paths, minimum path sum, and dungeon game.

Example — Minimum Path Sum (LeetCode 64):

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            else if (i == 0) grid[i][j] += grid[i][j - 1];
            else if (j == 0) grid[i][j] += grid[i - 1][j];
            else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    return grid[m - 1][n - 1];
}

Here we modify the grid in-place to achieve O(1) extra space. In an interview, always mention the trade-off: in-place modification is space-efficient but mutates the input.

Pattern 5: Interval DP

Interval DP solves problems where the answer for a range [i, j] depends on splitting it at some point k. You’ll see this in problems like burst balloons, matrix chain multiplication, and minimum cost to merge stones.

The general recurrence looks like: dp[i][j] = optimal over all k in [i, j) of (dp[i][k] + dp[k+1][j] + cost). These problems typically require O(n³) time and are considered hard-level — but recognizing the pattern is half the battle.

Common Mistakes and Pro Tips

Mistake 1: Jumping to DP too quickly. Before coding, verify the problem actually has overlapping subproblems. Some problems that look like DP are better solved with greedy algorithms or binary search.

Mistake 2: Wrong base cases. Off-by-one errors in DP are extremely common. Always think carefully about what dp[0], dp[1], or dp[i][0] should be before writing the transition.

Mistake 3: Not optimizing space. Many 2D DP solutions can be reduced to 1D. Interviewers often ask “can you optimize the space?” as a follow-up — be ready.

Tip 1: Start with recursion. Write a plain recursive solution first, then add memoization. This makes the logic clearer and is easier to debug.

Tip 2: Draw the DP table. For 2D problems, sketch out a small example on paper. Visualizing how cells fill in helps you catch errors early.

Tip 3: State your subproblem clearly. Before writing code, say out loud: “dp[i] represents…” This single sentence drives the entire solution and is exactly what interviewers want to hear.

Tip 4: Practice pattern recognition. Don’t memorize solutions — instead, learn to map a new problem to one of the five patterns above. Once you identify the pattern, the recurrence relation almost writes itself.

Start Practicing Today

Dynamic programming doesn’t have to be intimidating. By mastering these five patterns — Fibonacci-type, knapsack, longest subsequence, grid traversal, and interval DP — you’ll be equipped to handle the vast majority of DP problems in your next coding interview.

Start with 2-3 problems per pattern on LeetCode, and focus on understanding the recurrence before optimizing. If you found this guide helpful, check out our other coding interview walkthroughs for more pattern-based strategies.

Good luck with your interview prep — you’ve got this!