Top 50 Dynamic Programming Coding Problems for Interviews: A Comprehensive Guide

Table of Contents#

• 1. Fundamentals of DP
• 2. Knapsack Variations
• 3. String & Sequence DP
• 4. Array DP
• 5. Coin Change & Combinatorics
• 6. Matrix DP
• 7. Palindromic DP
• 8. Tree & Graph DP
• 9. Advanced DP Problems
• References

1. Fundamentals of DP#

These problems lay the groundwork for understanding DP by introducing core concepts like memoization, tabulation, and state transitions.

1.1 Fibonacci Number#

Problem Statement: Compute the nth Fibonacci number, where ( F(0) = 0 ), ( F(1) = 1 ), and ( F(n) = F(n-1) + F(n-2) ).
Key Insight: Overlapping subproblems (e.g., ( F(5) ) requires ( F(4) ) and ( F(3) ), which both require ( F(2) )).
Approach:

• Recursive: Exponential time (( O(2^n) )), no memoization.
• Memoization: Store results of subproblems in a cache (time ( O(n) ), space ( O(n) )).
• Tabulation: Iteratively compute values from ( F(0) ) to ( F(n) ) (time ( O(n) ), space ( O(1) ) with optimization).
  Difficulty: Easy

1.2 Climbing Stairs#

Problem Statement: You are climbing a staircase with n steps. You can climb 1 or 2 steps at a time. How many distinct ways can you reach the top?
Key Insight: The number of ways to reach step n is the sum of ways to reach step n-1 (1 step up) and step n-2 (2 steps up).
Approach:

• Recursive: ( f(n) = f(n-1) + f(n-2) ) (exponential time).
• Memoization: Cache results of f(n-1) and f(n-2) (time ( O(n) ), space ( O(n) )).
• Tabulation: Use a 1D array or variables to track prev and curr (time ( O(n) ), space ( O(1) )).
  Difficulty: Easy

1.3 House Robber (I)#

Problem Statement: You are a robber planning to rob houses along a street. Each house has a certain amount of money, but you cannot rob two adjacent houses. What is the maximum amount you can rob?
Key Insight: For each house i, the maximum loot is either:

• Loot from robbing house i + loot from houses before i-1 (i.e., dp[i-2] + nums[i]), or
• Loot from not robbing house i (i.e., dp[i-1]).
  Approach:
• Tabulation: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (time ( O(n) ), space ( O(n) ); optimize to ( O(1) ) with variables).
  Difficulty: Medium

1.4 House Robber (II)#

Problem Statement: Same as House Robber I, but the houses are arranged in a circle (the first and last houses are adjacent).
Key Insight: The problem splits into two cases:

1. Rob houses from the first to the second-last.
2. Rob houses from the second to the last.
   The answer is the maximum of these two cases.
   Approach:

• Reuse the solution for House Robber I on the two subarrays and return the maximum.
  Difficulty: Medium

1.5 Maximum Subarray (Kadane’s Algorithm)#

Problem Statement: Find the contiguous subarray (containing at least one number) with the largest sum.
Key Insight: For each position i, the maximum subarray sum ending at i is either:

• The element itself (nums[i]), or
• The element plus the maximum subarray sum ending at i-1 (dp[i-1] + nums[i]).
  Approach:
• Tabulation: Track current_max (max sum ending at i) and global_max (overall max sum). Update current_max = max(nums[i], current_max + nums[i]) (time ( O(n) ), space ( O(1) )).
  Difficulty: Medium

---

2. Knapsack Variations#

The knapsack problem is a classic DP scenario involving selecting items to maximize value without exceeding a weight capacity. Here are its most common variants:

2.1 0/1 Knapsack Problem#

Problem Statement: Given n items with weights wt[] and values val[], and a knapsack capacity W, find the maximum value achievable by selecting items such that their total weight ≤ W. Each item can be used at most once.
Key Insight: For each item i and capacity w, the maximum value is:

• If the item is included: val[i] + dp[i-1][w - wt[i]] (if wt[i] ≤ w).
• If the item is excluded: dp[i-1][w].
  Approach:
• 2D Tabulation: dp[i][w] = max(dp[i-1][w], (val[i] + dp[i-1][w - wt[i]]) if wt[i] ≤ w else dp[i-1][w]) (time ( O(nW) ), space ( O(nW) )).
• Space Optimization: Use a 1D array dp[W+1] and iterate backwards to avoid overwriting values (space ( O(W) )).
  Difficulty: Medium

2.2 Unbounded Knapsack Problem#

Problem Statement: Same as 0/1 knapsack, but each item can be used unlimited times.
Key Insight: For each capacity w, iterate over items and update dp[w] to include multiple uses of the same item.
Approach:

• 1D Tabulation: dp[w] = max(dp[w], val[i] + dp[w - wt[i]]) for all i where wt[i] ≤ w. Iterate capacities forward (unlike 0/1 knapsack) to allow reuse (time ( O(nW) ), space ( O(W) )).
  Difficulty: Medium

2.3 Target Sum#

Problem Statement: Given an array of integers nums and a target S, assign a + or - sign to each number to make their sum equal to S. Return the number of ways to do this.
Key Insight: Let sum(nums) = total. We need (sum of positive numbers) - (sum of negative numbers) = S. Let P be the sum of positive numbers. Then P - (total - P) = S → P = (S + total)/2. The problem reduces to finding the number of subsets of nums that sum to P.
Approach:

• Subset sum count: Use a 1D DP array where dp[p] = number of subsets with sum p (time ( O(nP) ), space ( O(P) )).
  Difficulty: Medium

2.4 Partition Equal Subset Sum#

Problem Statement: Given a non-empty array of positive integers, determine if it can be partitioned into two subsets with equal sum.
Key Insight: Check if sum(nums) is even. If not, return false. Otherwise, find if there exists a subset with sum sum(nums)/2 (0/1 knapsack variant).
Approach:

• 1D DP array dp[target] where dp[i] = true if a subset with sum i exists (time ( O(n \times target) ), space ( O(target) )).
  Difficulty: Medium

2.5 Count of Subset Sum#

Problem Statement: Given an array nums and a target sum k, count the number of subsets that sum to k.
Key Insight: For each number num and sum s, update dp[s] += dp[s - num] (unbounded if items can be reused, 0/1 if not).
Approach:

• 1D Tabulation: Initialize dp[0] = 1 (empty subset). For each num, iterate s from k down to num and update dp[s] += dp[s - num] (0/1 case) (time ( O(nk) ), space ( O(k) )).
  Difficulty: Medium

2.6 Bounded Knapsack Problem#

Problem Statement: Each item can be used at most c[i] times (e.g., 3 copies of item 1).
Key Insight: Decompose each item with c[i] copies into binary components (e.g., 3 = 2 + 1) and solve as 0/1 knapsack, or use a 1D array with a nested loop for counts.
Approach:

• Binary decomposition: Convert c[i] into powers of 2 (e.g., 5 = 4 + 1) to split into log(c[i]) items, then apply 0/1 knapsack (time ( O(nW \log c) )).
  Difficulty: Hard

---

3. String & Sequence DP#

String DP problems involve optimizing operations on strings, such as finding common subsequences, editing distances, or palindromic substrings.

3.1 Longest Common Subsequence (LCS)#

Problem Statement: Given two strings text1 and text2, find the length of their longest common subsequence (a subsequence is a sequence derived by deleting some characters without changing order).
Key Insight: For text1[i] and text2[j]:

• If text1[i] == text2[j], LCS(i,j) = LCS(i-1,j-1) + 1.
• Else, LCS(i,j) = max(LCS(i-1,j), LCS(i,j-1)).
  Approach:
• 2D Tabulation: dp[i][j] stores LCS length for text1[0..i-1] and text2[0..j-1] (time ( O(mn) ), space ( O(mn) ); optimize to ( O(min(m,n)) )).
  Difficulty: Medium

3.2 Edit Distance (Levenshtein Distance)#

Problem Statement: Given two strings word1 and word2, find the minimum number of operations (insert, delete, replace) required to convert word1 to word2.
Key Insight: For word1[i] and word2[j]:

• If word1[i] == word2[j], dp[i][j] = dp[i-1][j-1].
• Else, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete, insert, replace).
  Approach:
• 2D Tabulation: dp[i][j] = min edits for word1[0..i-1] → word2[0..j-1] (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Medium

3.3 Longest Repeating Subsequence#

Problem Statement: Find the length of the longest subsequence in a string that repeats (non-overlapping indices).
Key Insight: Treat the string as two separate strings and compute LCS where indices i != j (to avoid overlapping).
Approach:

• 2D DP: dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1 if s[i-1] == s[j-1] and i != j else 0) (time ( O(n^2) )).
  Difficulty: Medium

3.4 Distinct Subsequences#

Problem Statement: Given a string s and a target t, count the number of distinct subsequences of s that equal t.
Key Insight: For each character in s, update dp[j] (number of ways to form t[0..j-1]) as dp[j] += dp[j-1] if s[i] == t[j-1].
Approach:

• 1D Tabulation: dp[0] = 1 (empty subsequence). For each char in s, iterate j from len(t) down to 1 (to avoid overcounting) (time ( O(mn) ), space ( O(n) )).
  Difficulty: Hard

3.5 Shortest Common Supersequence (SCS)#

Problem Statement: Find the length of the shortest string that contains both text1 and text2 as subsequences.
Key Insight: SCS length = len(text1) + len(text2) - LCS length(text1, text2) (LCS is counted twice, so subtract once).
Approach:

• Compute LCS length first, then apply the formula (time ( O(mn) )).
  Difficulty: Medium

3.6 Minimum Insertions to Form a Palindrome#

Problem Statement: Given a string s, find the minimum number of characters to insert to make it a palindrome.
Key Insight: The minimum insertions = len(s) - length of longest palindromic subsequence (LPS) (LPS is the longest subsequence that is a palindrome; the remaining characters need to be mirrored).
Approach:

• Compute LPS of s (using LCS on s and its reverse) (time ( O(n^2) )).
  Difficulty: Medium

3.7 Longest Common Substring#

Problem Statement: Find the length of the longest contiguous substring common to two strings.
Key Insight: Track contiguous matches. For s1[i] == s2[j], dp[i][j] = dp[i-1][j-1] + 1; else, dp[i][j] = 0.
Approach:

• 2D DP: Track max_len as we iterate through characters (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Medium

3.8 Scramble String#

Problem Statement: Given two strings s1 and s2, determine if s2 is a scrambled version of s1 (split s1 into two non-empty parts, swap them, and recursively scramble each part).
Key Insight: Use memoization with 3 states: (i, j, k) (start index of s1, start index of s2, length of substring). Check all possible splits and permutations.
Approach:

• Memoization: dp[i][j][k] = true if s1[i..i+k-1] can be scrambled to s2[j..j+k-1] (time ( O(n^4) ), space ( O(n^3) )).
  Difficulty: Hard

---

4. Array DP#

Array DP problems focus on optimizing sequences of numbers, such as finding increasing subsequences, maximum product subarrays, or optimal stock trading strategies.

4.1 Longest Increasing Subsequence (LIS)#

Problem Statement: Given an integer array nums, return the length of the longest strictly increasing subsequence.
Key Insight: For each i, LIS[i] = 1 + max(LIS[j] for j < i and nums[j] < nums[i]).
Approach:

• Tabulation: dp[i] = length of LIS ending at i (time ( O(n^2) )).
• Optimized: Use binary search to maintain a list of the smallest possible tail values for increasing subsequences (time ( O(n \log n) )).
  Difficulty: Medium

4.2 Maximum Product Subarray#

Problem Statement: Find the contiguous subarray within an array of integers that has the largest product.
Key Insight: Track max_prod and min_prod (since a negative min_prod can become positive with a negative number). Update:

• temp_max = max(nums[i], max_prod * nums[i], min_prod * nums[i])
• min_prod = min(nums[i], max_prod * nums[i], min_prod * nums[i])
• max_prod = temp_max
  Approach:
• Iterate through the array, updating max_prod and min_prod (time ( O(n) ), space ( O(1) )).
  Difficulty: Medium

4.3 Jump Game I#

Problem Statement: Given an array nums where nums[i] is the maximum jump length from position i, determine if you can reach the last index.
Key Insight: Track the farthest index reachable. For each i, if i > farthest, return false. Update farthest = max(farthest, i + nums[i]).
Approach:

• Greedy/DP hybrid: Iterate and update farthest (time ( O(n) ), space ( O(1) )).
  Difficulty: Medium

4.4 Jump Game II#

Problem Statement: Same as Jump Game I, but find the minimum number of jumps to reach the last index.
Key Insight: Track current_end (end of current jump range), farthest, and jumps. Increment jumps when i reaches current_end.
Approach:

• Greedy: Iterate, update farthest, and reset current_end when needed (time ( O(n) ), space ( O(1) )).
  Difficulty: Hard

4.5 Best Time to Buy and Sell Stock (I)#

Problem Statement: You can buy and sell once. Find the maximum profit.
Key Insight: Track min_price and max_profit. For each price, max_profit = max(max_profit, price - min_price).
Approach:

• Iterate, update min_price and max_profit (time ( O(n) ), space ( O(1) )).
  Difficulty: Easy

4.6 Best Time to Buy and Sell Stock (III)#

Problem Statement: You can buy and sell at most twice. Find the maximum profit.
Key Insight: Track four states: buy1, sell1, buy2, sell2 (first buy, first sell, second buy, second sell).

• buy1 = min(buy1, price)
• sell1 = max(sell1, price - buy1)
• buy2 = min(buy2, price - sell1) (use profit from first sell to buy again)
• sell2 = max(sell2, price - buy2)
  Approach:
• Iterate and update the four states (time ( O(n) ), space ( O(1) )).
  Difficulty: Hard

4.7 Best Time to Buy and Sell Stock (IV)#

Problem Statement: You can buy and sell at most k times. Find the maximum profit.
Key Insight: For k transactions, track buy[i] (min price to buy for the i-th transaction) and sell[i] (max profit from i-th sell).

• buy[i] = min(buy[i], price - sell[i-1])
• sell[i] = max(sell[i], price - buy[i])
  Approach:
• Use a DP array for buy and sell (time ( O(nk) ), space ( O(k) )).
  Difficulty: Hard

4.8 Maximum Sum Increasing Subsequence (MSIS)#

Problem Statement: Find the maximum sum of an increasing subsequence.
Key Insight: Similar to LIS, but dp[i] = max(dp[j] + nums[i] for j < i and nums[j] < nums[i]) (initialize dp[i] = nums[i]).
Approach:

• Tabulation (time ( O(n^2) )).
  Difficulty: Medium

4.9 Length of Longest Subarray with Positive Product#

Problem Statement: Given an array of integers, find the length of the longest subarray with a positive product.
Key Insight: Track positive_len (length of subarray ending at i with positive product) and negative_len (same for negative). Update based on the sign of nums[i].
Approach:

• Iterate and update positive_len and negative_len (time ( O(n) ), space ( O(1) )).
  Difficulty: Medium

---

5. Coin Change & Combinatorics#

These problems involve counting ways to form sums or making change with coins, a common DP application for combinatorial optimization.

5.1 Coin Change I (Minimum Coins)#

Problem Statement: Given coins of denominations coins and an amount amount, find the minimum number of coins to make amount (unbounded coins).
Key Insight: dp[i] = min coins to make amount i. For each i, dp[i] = min(dp[i - coin] + 1) for all coin ≤ i.
Approach:

• Tabulation: Initialize dp[0] = 0, others as infinity. Iterate amounts and coins (time ( O(amount \times n) ), space ( O(amount) )).
  Difficulty: Medium

5.2 Coin Change II (Number of Ways)#

Problem Statement: Given coins and amount, find the number of ways to make amount (unbounded coins, order does not matter).
Key Insight: dp[i] = number of ways to make i. For each coin, iterate amounts from coin to amount and dp[i] += dp[i - coin].
Approach:

• Tabulation: dp[0] = 1. Iterate coins first, then amounts (to avoid counting permutations as distinct) (time ( O(n \times amount) ), space ( O(amount) )).
  Difficulty: Medium

5.3 Combination Sum IV#

Problem Statement: Given nums and target, find the number of combinations that sum to target (order matters, e.g., [1,2] and [2,1] are distinct).
Key Insight: Similar to Coin Change II, but iterate amounts first, then coins (to count permutations).
Approach:

• Tabulation: dp[0] = 1. For each i from 1 to target, dp[i] += dp[i - num] for all num ≤ i (time ( O(target \times n) ), space ( O(target) )).
  Difficulty: Medium

5.4 Staircase with Variable Steps#

Problem Statement: You can climb k steps (given as an array steps). Find the number of ways to reach the top (step n).
Key Insight: dp[i] = sum(dp[i - step] for step in steps if i - step ≥ 0).
Approach:

• Tabulation: dp[0] = 1. For each i from 1 to n, sum dp[i - step] (time ( O(n \times k) ), space ( O(n) )).
  Difficulty: Medium

---

6. Matrix DP#

Matrix DP problems involve grids or 2D arrays, where solutions depend on neighboring cells (e.g., paths, sums, or constraints).

6.1 Unique Paths I#

Problem Statement: A robot starts at (0,0) in an m x n grid and moves only right or down. How many unique paths to (m-1, n-1)?
Key Insight: dp[i][j] = dp[i-1][j] + dp[i][j-1] (paths from top + paths from left).
Approach:

• Tabulation: dp[0][j] = 1 (first row), dp[i][0] = 1 (first column). Fill the rest (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Easy

6.2 Unique Paths II#

Problem Statement: Same as I, but with obstacles (marked as 1). A robot cannot move into obstacles.
Key Insight: If grid[i][j] == 1, dp[i][j] = 0. Else, dp[i][j] = dp[i-1][j] + dp[i][j-1] (if i-1 or j-1 are valid).
Approach:

• Handle edge cases (start/end is obstacle). Use a 1D array and update in place (time ( O(mn) ), space ( O(n) )).
  Difficulty: Medium

6.3 Minimum Path Sum#

Problem Statement: Find the minimum path sum from (0,0) to (m-1, n-1) in a grid with non-negative numbers (move right/down).
Key Insight: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Approach:

• Tabulation: Initialize first row and column with cumulative sums. Fill the rest (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Medium

6.4 Dungeon Game#

Problem Statement: A knight starts at (0,0) in a dungeon grid (cells can have positive/negative values, representing health gain/loss). He needs to reach the princess at (m-1, n-1) with health > 0. Find the minimum initial health.
Key Insight: Work backwards from the princess. dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]) (knight needs enough health to survive current cell and reach the end).
Approach:

• 2D DP array, filled from bottom-right to top-left (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Hard

6.5 Cherry Pickup#

Problem Statement: A robot starts at (0,0) and moves to (n-1, n-1) in an n x n grid, collecting cherries (can move right/down). Then it returns to (0,0) (can move left/up). Find the maximum cherries collected.
Key Insight: Model the round trip as two robots moving from (0,0) to (n-1, n-1) simultaneously. Track dp[k][i][j] (k steps taken, robot1 at (i, k-i), robot2 at (j, k-j)).
Approach:

• 3D DP with state (k, i, j), where k is the sum of coordinates (time ( O(n^3) ), space ( O(n^3) ); optimize to ( O(n^2) )).
  Difficulty: Hard

6.6 Largest Square Submatrix of 1’s#

Problem Statement: Given a binary matrix, find the area of the largest square containing only 1’s.
Key Insight: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if matrix[i][j] == 1 (size of square with bottom-right corner at (i,j)).
Approach:

• 2D DP array, track max_size (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Medium

6.7 Maximum Size Rectangle of 1’s#

Problem Statement: Given a binary matrix, find the area of the largest rectangle containing only 1’s.
Key Insight: Treat each row as the base of a histogram, where heights[j] is the number of consecutive 1’s ending at (i,j). Use the "largest rectangle in histogram" algorithm on each row.
Approach:

• Compute heights array for each row, then apply histogram logic (time ( O(mn) ), space ( O(n) )).
  Difficulty: Hard

---

7. Palindromic DP#

Palindromic DP problems focus on finding/using palindromic substrings or subsequences, which have symmetric properties ideal for DP.

7.1 Longest Palindromic Substring (DP Approach)#

Problem Statement: Find the longest contiguous palindromic substring in a string.
Key Insight: A substring s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is a palindrome.
Approach:

• 2D DP: dp[i][j] = true if s[i..j] is a palindrome. Fill for all lengths l=1 to n (time ( O(n^2) ), space ( O(n^2) )).
  Difficulty: Medium

7.2 Count Palindromic Substrings#

Problem Statement: Count all palindromic substrings in a string.
Key Insight: Use the DP table from "Longest Palindromic Substring" and count all dp[i][j] = true.
Approach:

• 2D DP: Iterate over all substrings and count palindromes (time ( O(n^2) ), space ( O(n^2) )).
  Difficulty: Medium

7.3 Palindromic Partitioning (Minimum Cuts)#

Problem Statement: Given a string, split it into the minimum number of palindromic substrings.
Key Insight: dp[i] = min cuts for s[0..i]. For j < i, if s[j+1..i] is a palindrome, dp[i] = min(dp[i], dp[j] + 1).
Approach:

• Precompute a palindrome table is_pal[i][j]. Then compute dp array (time ( O(n^2) ), space ( O(n^2) )).
  Difficulty: Hard

7.4 Longest Palindromic Subsequence (LPS)#

Problem Statement: Find the length of the longest palindromic subsequence (non-contiguous).
Key Insight: LPS of s = LCS of s and its reverse.
Approach:

• Compute LCS(s, reversed(s)) (time ( O(n^2) ), space ( O(n^2) )).
  Difficulty: Medium

7.5 Minimum Deletions to Make String Palindrome#

Problem Statement: Find the minimum number of deletions to make a string a palindrome.
Key Insight: Minimum deletions = len(s) - LPS length (LPS is the longest subsequence that is a palindrome; delete the rest).
Approach:

• Compute LPS length, then subtract from len(s) (time ( O(n^2) )).
  Difficulty: Medium

---

8. Tree & Graph DP#

Tree and graph DP problems involve optimizing paths or values on hierarchical structures like trees or graphs.

8.1 House Robber III (Tree Version)#

Problem Statement: Houses are arranged in a binary tree. Robbing two adjacent nodes (parent-child) is not allowed. Find the maximum loot.
Key Insight: For each node, return two values: [rob, not_rob] (max loot if node is robbed/not robbed).

• rob = node.val + left.not_rob + right.not_rob
• not_rob = max(left.rob, left.not_rob) + max(right.rob, right.not_rob)
  Approach:
• Post-order traversal with memoization (time ( O(n) ), space ( O(n) )).
  Difficulty: Medium

8.2 Maximum Path Sum in Binary Tree#

Problem Statement: Find the maximum path sum in a binary tree (path can start/end at any node, but must be contiguous).
Key Insight: For each node, compute the maximum path sum passing through it: node.val + max(left_gain, 0) + max(right_gain, 0). Update the global maximum.
Approach:

• Post-order traversal, track max_sum and return the max gain from the subtree (time ( O(n) ), space ( O(h) ), h is tree height).
  Difficulty: Hard

8.3 Diameter of Binary Tree#

Problem Statement: The diameter is the length of the longest path between any two nodes (path may or may not pass through the root).
Key Insight: For each node, diameter = left_depth + right_depth. Track the maximum diameter across all nodes.
Approach:

• Post-order traversal, compute depth of left/right subtrees, and update diameter (time ( O(n) ), space ( O(h) )).
  Difficulty: Easy

8.4 Number of Ways to Paint a Tree#

Problem Statement: Given a tree with n nodes and k colors, find the number of ways to color the tree such that no two adjacent nodes have the same color.
Key Insight: Root the tree. The root has k choices. Each child has k-1 choices (not root’s color). Each subsequent child has k-2 choices (not parent’s or sibling’s color).
Approach:

• Post-order traversal, multiply choices for each node (time ( O(n) )).
  Difficulty: Medium

---

9. Advanced DP Problems#

These problems require advanced DP techniques, such as interval DP, state compression, or handling complex state transitions.

9.1 Burst Balloons#

Problem Statement: Given n balloons with values, burst them in an order where bursting the i-th balloon gives nums[left] * nums[i] * nums[right] (left/right are adjacent unburst balloons). Find the maximum coins.
Key Insight: Use interval DP: dp[i][j] = max coins for bursting balloons between i and j. For k (last balloon to burst in i..j), dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1]).
Approach:

• Add dummy balloons at start/end (value 1). Fill dp for intervals of length l from 1 to n (time ( O(n^3) ), space ( O(n^2) )).
  Difficulty: Hard

9.2 Egg Drop Problem#

Problem Statement: Given e eggs and f floors, find the minimum number of attempts to determine the critical floor (the lowest floor from which an egg breaks).
Key Insight: dp[e][f] = min attempts for e eggs and f floors. For a floor k, if the egg breaks, solve dp[e-1][k-1]; else, solve dp[e][f-k].

• dp[e][f] = 1 + min(max(dp[e-1][k-1], dp[e][f-k])) for k=1..f.
  Approach:
• 2D DP with base cases: dp[1][f] = f, dp[e][1] = 1 (time ( O(e f^2) ), space ( O(e f) ); optimize with binary search to ( O(e f \log f) )).
  Difficulty: Hard

9.3 Regular Expression Matching#

Problem Statement: Given a string s and pattern p (supports . (matches any char) and * (matches 0+ of the preceding element)), determine if s matches p.
Key Insight: dp[i][j] = true if s[0..i-1] matches p[0..j-1].

• If p[j-1] == '*', check:
  • dp[i][j-2] (use * to match 0 preceding elements), or
  • dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.') (use * to match 1+).
• Else, dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.').
  Approach:
• 2D DP array (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Hard

9.4 Wildcard Matching#

Problem Statement: Similar to regex matching, but * matches any sequence (including empty).
Key Insight: dp[i][j] = true if s[0..i-1] matches p[0..j-1].

• If p[j-1] == '*', dp[i][j] = dp[i][j-1] (match empty) or dp[i-1][j] (match 1+ chars).
  Approach:
• 2D DP (time ( O(mn) ), space ( O(mn) ); optimize to ( O(n) )).
  Difficulty: Hard

---

References#

• LeetCode DP Problems: https://leetcode.com/tag/dynamic-programming/
• GeeksforGeeks DP Tutorial: https://www.geeksforgeeks.org/dynamic-programming/
• "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS).
• "Dynamic Programming for Interviews" by Sam Gavis-Hughson.

Mastering these 50 problems will give you a strong foundation in DP and prepare you to tackle even the most challenging interview questions. Happy coding! 🚀