Top DP Interview Problems — Avoid StackOverflow in Prod

Dynamic programming separates the candidates who get offers from the ones who get 'we'll be in touch.' It's not because DP is obscure — it's because it forces you to think recursively, spot structure in chaos, and optimise on the fly. Every major tech company — Google, Meta, Amazon, Microsoft — leans on DP problems to stress-test exactly those skills. If you can solve a DP problem cleanly under pressure, you've signalled that you understand trade-offs, not just syntax.

The reason DP trips people up isn't the math — it's the pattern recognition. Beginners see 20 different DP problems and treat each one as a unique puzzle. Senior engineers see the same 5 underlying patterns wearing different costumes. Once you can identify 'this is a knapsack variant' or 'this is interval DP,' you're not solving problems cold anymore — you're applying a playbook. That shift from memorisation to pattern recognition is exactly what this article builds.

By the end of this article you'll be able to recognise the 10 most common DP problem archetypes, implement each one from scratch with correct base cases and transition functions, explain your space-optimisation decisions out loud, and handle the follow-up questions interviewers use to probe whether you truly understand or just memorised. Let's build that playbook.

DP Pattern Matrix for Rapid Classification

When you see a new problem, ask yourself three questions: What is the state? What is the recurrence shape? What are the base cases? These form a pattern matrix that maps every DP problem to one of five archetypes. Use the table below to classify within seconds.

To use the matrix: Identify the structure of the input. If you see two sequences → Sequence or Edit Distance. If you see a single array with capacity limit → Knapsack. If you see substrings/ranges → Interval. If you see an n×m grid → Grid. If you see a problem asking for the longest increasing order → LIS. This classification step alone eliminates 80% of the guesswork.

// Quick classification snippet — not real code
public class PatternClassifier {
    public String classify(String problemDescription) {
        if (problemDescription.contains("substring") || problemDescription.contains("range")) {
            return "INTERVAL_DP";
        } else if (problemDescription.contains("grid") || problemDescription.contains("matrix")) {
            return "GRID_DP";
        } else if (problemDescription.contains("capacity") || problemDescription.contains("weight")) {
            return "KNAPSACK";
        } else if (problemDescription.contains("sequence") || problemDescription.contains("subsequence")) {
            return "SEQUENCE_DP";
        } else if (problemDescription.contains("increasing")) {
            return "LIS";
        } else {
            return "ANALYZE_MORE";
        }
    }
}

Visual State Transition Table Walkthrough

One of the best ways to internalize DP is to draw the state transition table manually. Let's take the classic "Coin Change 2" problem (number of combinations to make an amount using unlimited coins) and walk through the table cell by cell. We'll use a small example: coins = [1,2,5], amount = 5. The DP table is built row by row, where each row represents a coin and each column represents an amount. The value in dp[coinIndex][amount] is the number of combinations using only coins up to the current coin type.

Below is a step-by-step visualization using array states for each row. Watch how the values evolve.

public class CoinChange2TableWalkthrough {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int x = coin; x <= amount; x++) {
                dp[x] = dp[x] + dp[x - coin];  // exclude + include
            }
        }
        return dp[amount];
    }
}

Memoization vs Tabulation Comparison Matrix

Both memoization (top-down) and tabulation (bottom-up) solve the same DP problems but they differ in performance, memory, and safety. The table below compares them across key dimensions.

When to use which? For interviews: I recommend starting with tabulation if you can see the bottom-up order. It's safer and faster. Use memoization as a fallback when the state transition order is not obvious (e.g., string-based state). In production, always prefer tabulation to avoid stack overflow and achieve better cache locality. But for complex state definitions (like dictionary words), memoization with HashMap can be cleaner.

Below is a code example of Fibonacci implemented both ways.

public class FibonacciComparison {
    // Memoization
    static int[] memo;
    public static int fibMemo(int n) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibMemo(n-1) + fibMemo(n-2);
        return memo[n];
    }

    // Tabulation
    public static int fibTab(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }

    public static void main(String[] args) {
        int n = 100;
        memo = new int[n+1];
        System.out.println("Memo: " + fibMemo(n));  // could stack overflow for n=10000
        System.out.println("Tab: " + fibTab(n));    // safe
    }
}

Space Optimization: From O(N²) to O(N)

One of the most common follow-up questions in interviews is: "Can you optimize the space from O(N²) to O(N)?" This is not a trick — it's a test of your understanding of the dependency pattern in the recurrence. If the current state depends only on the previous row (or a fixed number of previous states), you can reduce space by storing only those rows.

General technique: Replace the 2D DP table with a 1D array and update it in-place. The iteration order (forward vs backward) determines whether it's unbounded or 0/1. For LCS (two sequences), you need two rows because you need both dp[i-1][j] and dp[i][j-1] and dp[i-1][j-1]. Use a temporary variable to preserve the old diagonal value.

Example: 0/1 Knapsack — original 2D table O(NC). Observe that dp[i][w] only uses dp[i-1][] (row above). So we can use a 1D array and iterate capacity backwards to avoid overwriting needed values. This is the most famous space optimization.

Example: Longest Common Subsequence — 2D O(mn). Since transition uses dp[i-1][j-1], dp[i-1][j], and dp[i][j-1], we need to keep two rows (previous and current) and a variable to remember the old diagonal. This reduces space to O(2min(m,n)) = O(min(m,n)).

Example: Grid DP (Unique Paths) — only need one row because dp[j] = dp[j] (above) + dp[j-1] (left). Update left to right.

When space optimization is NOT possible: Interval DP requires all intervals of different lengths; the dependency is not just on previous row. Burst Balloons and Matrix Chain Multiplication typically remain O(N²) space. However, you can sometimes reduce by dividing into halves but that's advanced.

Below is a side-by-side implementation showing the progression from O(N²) to O(N) for LCS.

public class LcsSpaceOptimized {
    // O(m*n) time, O(min(m,n)) space
    public int lcsOptimized(String text1, String text2) {
        if (text1.length() < text2.length()) {
            String tmp = text1; text1 = text2; text2 = tmp;
        }
        int m = text1.length(), n = text2.length();
        int[] prev = new int[n+1];  // previous row
        int[] cur = new int[n+1];   // current row

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    cur[j] = 1 + prev[j-1];
                } else {
                    cur[j] = Math.max(prev[j], cur[j-1]);
                }
            }
            // swap rows
            int[] temp = prev;
            prev = cur;
            cur = temp;
            // clear cur for next iteration (optional, as values will be overwritten)
            Arrays.fill(cur, 0);
        }
        return prev[n];
    }
}

Core Pattern: The 0/1 Knapsack Framework

The most pervasive pattern in DP is the 'Selection' problem, exemplified by the 0/1 Knapsack. In this scenario, you face a series of items and must decide: 'Do I include this item or skip it?' This binary choice builds a decision tree that we optimize using a 2D array (or a space-optimized 1D array). Understanding this state transition is the key to solving variations like 'Partition Equal Subset Sum' and 'Target Sum.'

package io.thecodeforge.dp;

public class KnapsackSolver {
    /**
     * Standard 0/1 Knapsack Implementation
     * Time Complexity: O(N * W), Space Complexity: O(W)
     */
    public int solveKnapsack(int[] values, int[] weights, int capacity) {
        int n = values.length;
        // Space optimized 1D DP array
        int[] dp = new int[capacity + 1];

        for (int i = 0; i < n; i++) {
            // Iterate backwards to ensure we don't use the same item twice
            for (int w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
            }
        }
        return dp[capacity];
    }
}

Sequence Pattern: Longest Common Subsequence (LCS)

When dealing with two strings or arrays, the 'Sequence' pattern is your go-to. The goal is to find the relationship between two prefixes. The transition function relies on a simple logic: if characters match, extend the previous subsequence; if they don't, take the best result from either ignoring the current character of the first string or the second.

package io.thecodeforge.dp;

public class LcsService {
    /**
     * io.thecodeforge: Standard LCS implementation
     * Handles the core of problems like 'Edit Distance' and 'Longest Palindromic Subsequence'
     */
    public int findLCS(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] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

Unbounded Knapsack: Coin Change & Rod Cutting

In the Unbounded Knapsack, you have unlimited copies of each item. The recurrence changes: when you include an item, you stay on the same item row instead of moving to the previous one. This means the inner loop iterates forward. Classic problems: Coin Change (minimum coins), Coin Change 2 (number of combinations), and Rod Cutting.

package io.thecodeforge.dp;

public class CoinChangeSolver {
    /**
     * Minimum number of coins to make amount.
     * Unbounded knapsack – iterate forward.
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            for (int x = coin; x <= amount; x++) {
                dp[x] = Math.min(dp[x], 1 + dp[x - coin]);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Interval DP: Matrix Chain Multiplication & Palindromic Substrings

Interval DP solves problems by considering all subarrays or substrings. The state is typically defined by the start and end indices of a range. The transition tries every possible split point within that range and combines the results. Classic problems: Matrix Chain Multiplication, Palindromic Substrings, Burst Balloons, and Optimal BST.

package io.thecodeforge.dp;

public class MatrixChainMultiplication {
    /**
     * Compute minimum multiplication cost for matrices A1A2...An
     */
    public int minCost(int[] dimensions) {
        int n = dimensions.length - 1; // number of matrices
        int[][] dp = new int[n][n];

        // length L from 2 to n
        for (int L = 2; L <= n; L++) {
            for (int i = 0; i <= n - L; i++) {
                int j = i + L - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k+1][j] + dimensions[i]*dimensions[k+1]*dimensions[j+1];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        return dp[0][n-1];
    }
}

Grid DP: Unique Paths & Minimum Path Sum

Grid DP problems involve moving through a matrix from top-left to bottom-right, often with obstacles or costs. The state is (row, col) and transitions come from the left or above. This is one of the easiest DP patterns to recognize – the recurrence is straightforward – but variations like 'Dungeon Game' and 'Cherry Pickup' push it to the next level.

package io.thecodeforge.dp;

public class UniquePaths {
    /**
     * Robot from top-left to bottom-right, only down or right.
     */
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1]; // dp[j] from above + left
            }
        }
        return dp[n-1];
    }
}

Longest Increasing Subsequence (LIS) – The O(n log n) Variant

LIS is a classic that tests your ability to go beyond O(n^2). The DP solution is O(n^2), but the optimal solution uses patience sorting (binary search) to achieve O(n log n). The state is the smallest possible tail of an increasing subsequence of each length. This pattern reappears in problems like 'Russian Doll Envelopes' and 'Maximum Length of Pair Chain'.

package io.thecodeforge.dp;

public class LIS {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int x : nums) {
            int i = Arrays.binarySearch(tails, 0, size, x);
            if (i < 0) i = -(i + 1);
            tails[i] = x;
            if (i == size) size++;
        }
        return size;
    }
}

Edit Distance (Levenshtein Distance) – String Alignment DP

Edit Distance measures how many single-character edits (insert, delete, replace) are needed to transform one string into another. The recurrence is the same as LCS but with an extra operation (replace). It's a classic DP problem that tests your ability to handle three transitions correctly. Variations include one-edit-distance, and weighted edit operations.

package io.thecodeforge.dp;

public class EditDistance {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1]; // match
                } else {
                    dp[i][j] = 1 + Math.min(
                        dp[i-1][j],    // delete
                        Math.min(dp[i][j-1],    // insert
                                 dp[i-1][j-1])); // replace
                }
            }
        }
        return dp[m][n];
    }
}