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.

What DP Interview Problems Actually Test

Dynamic programming interview problems test your ability to decompose a problem into overlapping subproblems and reuse computed results. The core mechanic is memoization or tabulation — storing solutions to subproblems so you don't recompute them. This turns exponential brute force into polynomial time, typically O(n²) or O(n·m).

The key property that matters in practice is optimal substructure: the optimal solution to the whole problem must contain optimal solutions to its subproblems. Without that, DP won't work. You also need overlapping subproblems — if subproblems are unique, DP gives no benefit over divide-and-conquer. Recognizing these two properties is the difference between solving a problem and guessing at a recurrence.

Use DP when you see 'count ways', 'minimum cost', 'maximum profit', or 'longest subsequence' — these almost always hide overlapping subproblems. In real systems, DP powers route optimization, resource allocation, and sequence alignment. Knowing when to apply it separates engineers who write O(2^n) code from those who ship production-grade solutions.

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];
    }
}

The Pathological Recurrence: Why Your State Definition Is the Only Thing That Matters

You've memorized the patterns. You've grinded 50 problems. Then a senior throws you a problem you've never seen, and your O(2^n) solution times out in the interview. The bottleneck isn't the algorithm — it's the state definition. Every DP problem is just a recurrence relation with a built-in dependency graph. The moment you define dp[i][j] as 'maximum profit from the first i items with capacity j', you've already won or lost. If your state is wrong, no optimization in the world saves you. The trick: trace the recurrence on paper before writing code. Find the smallest input that breaks your logic. Memoization is forgiving; tabulation punishes bad state definitions with a silent O(n^2) washout. In production, this kills more services than null pointers — an incorrect caching key that grows exponentially with input size. Define your state like your job depends on it. Because in an on-call rotation, it does.

// io.thecodeforge
// Bad: state explodes, O(2^n) on string length
public int badWildcardMatch(String s, String p) {
    return dfs(s, p, 0, 0);
}

// Good: O(m*n) with clear 2D state
public int isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m+1][n+1];
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-2];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else if (p.charAt(j-1) == '*') {
                dp[i][j] = dp[i][j-2];
                if (p.charAt(j-2) == '.' || p.charAt(j-2) == s.charAt(i-1)) {
                    dp[i][j] = dp[i][j] || dp[i-1][j];
                }
            }
        }
    }
    return dp[m][n] ? 1 : 0;
}

The Recurrence Relation Debugging Checklist: What to Do When Your DP Goes Silent

Your DP returns 0 for every input. No exceptions. No stack traces. Just wrong answers. This is the most common bug in production DP code — a recurrence that silently degenerates to the base case. The fix isn't more print statements. It's a three-point checklist. First, verify your base case returns something non-zero for the smallest valid input. Second, trace the recurrence manually for n=1 and n=2. Third, ensure every recursive call actually transforms the state — if your recurrence calls f(i, j) and both parameters stay identical, you've built an infinite loop that returns base case. In production, this manifests as a caching layer that always hits the null entry because the key never changes. The real debugging move: write the recurrence on paper, then translate it character-by-character to code. Every operator, every index shift. I've watched juniors spend three hours chasing a bug that was a single off-by-one in a state transition. The recurrence is the contract. If it's wrong, the code is a lie.

// io.thecodeforge
public int fibonacciBugged(int n) {
    int[] dp = new int[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // correct
    }
    return dp[n];
}

// The silent killer: recurrence doesn't progress
public int countWays(int n) {
    if (n <= 1) return 1;
    // BUG: dp[i] = dp[i-1] + dp[i-2]? No, it's just dp[i-1]
    return countWays(n-1) + countWays(n-2); // innocent-looking but wrong
}

// Fixed: explicit state progression
public int countWaysFixed(int n) {
    int[] dp = new int[n+1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

The Common Substring Threshold: Why LCS Variants Break in Production Without Compression

Longest Common Substring (not subsequence) looks like LCS but with a catch: you reset to 0 when characters don't match. That's easy. The production killer is when you need to find substrings above a length threshold — like 'find all common substrings longer than 3 characters between two DNA sequences'. The naive DP keeps the entire table, O(m*n) memory. With m=100k, n=100k, that's 10 billion entries. Your server crashes. The fix: sliding window DP with O(n) space. Only track the previous row, and store results in a hash set of start indices. But here's the trap: when you discard rows, you lose the ability to backtrack and reconstruct. If the interviewer asks 'print the longest substring', not just its length, you need a different strategy. Production compromise: store only the maximum length and the ending index in each row. Reconstruct by scanning the string at the end. This keeps memory O(n) and gives you the actual substring. I've seen this exact pattern at scale — a bioinformatics pipeline that ran out of memory every night at 3 AM. The root cause? A junior using 2D dp[][] for all-vs-all comparisons.

// io.thecodeforge
// O(m*n) memory — don't use this for production
public int lcsNaive(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m+1][n+1];
    int max = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }
    return max;
}

// O(n) memory — production-ready
public int lcsOptimized(String a, String b) {
    int m = a.length(), n = b.length();
    int[] prev = new int[n+1];
    int max = 0;
    for (int i = 1; i <= m; i++) {
        int[] curr = new int[n+1];
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1)) {
                curr[j] = prev[j-1] + 1;
                max = Math.max(max, curr[j]);
            }
        }
        prev = curr;
    }
    return max;
}

DP Patterns Framework: 0/1 Knapsack, LCS, Palindromes, DP on Grid

Mastering DP requires recognizing patterns. This section unifies four core patterns: 0/1 Knapsack, Longest Common Subsequence (LCS), Palindromic Substrings, and DP on Grids. Each pattern has a characteristic state definition and recurrence.

0/1 Knapsack: Given weights and values, maximize value without exceeding capacity. State: dp[i][w] = max value using first i items with capacity w. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi). Example: Subset Sum, Partition Equal Subset Sum.

LCS: Find longest subsequence common to two strings. State: dp[i][j] = length of LCS of prefixes of length i and j. Recurrence: if s1[i-1]==s2[j-1] then dp[i][j]=1+dp[i-1][j-1] else dp[i][j]=max(dp[i-1][j], dp[i][j-1]). Example: Edit Distance, Shortest Common Supersequence.

Palindromic Substrings: Count or find longest palindromic substring. State: dp[i][j] = true if substring i..j is palindrome. Recurrence: dp[i][j] = (s[i]==s[j] and (j-i<2 or dp[i+1][j-1])). Example: Palindromic Partitioning, Longest Palindromic Subsequence.

DP on Grid: Count paths or find min cost in a grid. State: dp[i][j] = number of ways or min cost to reach (i,j). Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (for unique paths) or dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) (for min path sum). Example: Unique Paths II, Minimum Path Sum.

These patterns share a common structure: define state, write recurrence, handle base cases, and iterate. Recognizing which pattern applies is the key to solving DP problems quickly.

# 0/1 Knapsack
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

# LCS
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# Palindromic Substrings count
def count_palindromic_substrings(s):
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    count = 0
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            if s[i]==s[j] and (j-i<2 or dp[i+1][j-1]):
                dp[i][j] = True
                count += 1
    return count

# Grid DP: Unique Paths
def unique_paths(m, n):
    dp = [[1]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

DP vs Greedy vs Backtracking: Decision Framework

Choosing the right algorithmic paradigm is critical. This framework helps decide between DP, Greedy, and Backtracking based on problem properties.

Greedy: Use when a local optimum leads to global optimum. Properties: optimal substructure (without overlapping subproblems) and greedy choice property. Example: Fractional Knapsack, Dijkstra's algorithm. If you can prove that making the best choice at each step yields the optimal solution, go greedy. It's O(n log n) or O(n).

Backtracking: Use when you need to explore all possibilities (exhaustive search) and the solution space is small. It's essentially brute force with pruning. Example: N-Queens, Sudoku solver. Time complexity is exponential, so only feasible for small inputs (n ≤ 20).

DP: Use when there are overlapping subproblems and optimal substructure. DP caches results to avoid recomputation. Example: 0/1 Knapsack, Edit Distance. Time complexity is polynomial (O(n^2) or O(n*capacity)).

Decision Flowchart: 1. Does the problem ask for a single optimal solution (max/min) or count? → DP or Greedy. 2. Can you make a decision that never needs to be undone? → Greedy. 3. Are there overlapping subproblems? → DP. 4. Is the input size small and need all solutions? → Backtracking.

Example: Coin Change (minimum coins). Greedy fails for arbitrary denominations (e.g., coins [1,3,4], amount 6: greedy gives 4+1+1=3 coins, but optimal is 3+3=2). DP works. But for canonical coin systems (e.g., US coins), greedy works.

Production Note: Greedy is fastest, DP is moderate, backtracking is slowest. Always profile test cases to ensure correctness.

# Greedy: Fractional Knapsack
def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    for w, v in items:
        if capacity >= w:
            total_value += v
            capacity -= w
        else:
            total_value += v * (capacity / w)
            break
    return total_value

# DP: 0/1 Knapsack (as above)
# Backtracking: Subset Sum (find all subsets)
def subset_sum_backtrack(nums, target):
    res = []
    def backtrack(start, path, total):
        if total == target:
            res.append(path[:])
            return
        if total > target:
            return
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i+1, path, total+nums[i])
            path.pop()
    backtrack(0, [], 0)
    return res

DP with Bitmask for Subset Problems

Bitmask DP is a powerful technique for problems involving subsets, especially when the number of elements is small (n ≤ 20). It uses an integer's bits to represent a set: bit i is 1 if element i is included.

State: dp[mask] = optimal value for the subset represented by mask. Often combined with a second dimension (e.g., last element) for path problems.

# TSP using bitmask DP
def tsp(dist):
    n = len(dist)
    dp = [[float('inf')]*n for _ in range(1<<n)]
    dp[1][0] = 0  # start at city 0
    for mask in range(1<<n):
        for u in range(n):
            if not (mask & (1<<u)):
                continue
            for v in range(n):
                if mask & (1<<v):
                    continue
                new_mask = mask | (1<<v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
    full_mask = (1<<n)-1
    return min(dp[full_mask][i] + dist[i][0] for i in range(1, n))

# Subset Sum using bitmask (check existence)
def subset_sum_bitmask(nums, target):
    n = len(nums)
    for mask in range(1<<n):
        total = 0
        for i in range(n):
            if mask & (1<<i):
                total += nums[i]
        if total == target:
            return True
    return False