Dynamic Programming Interview Problems — Complete Guide
In this tutorial, you'll learn about Dynamic Programming Interview Problems. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Dynamic Programming solves optimization problems by breaking them into overlapping subproblems and storing results to avoid redundant computation. It is the most feared yet most testable topic in coding interviews.
Learning Path
flowchart LR A["Tree & Graph Problems"] --> B["DP Problems
You are here"] B --> C["Sorting & Searching"] C --> D["System Design Prep"] style B fill:#f90,color:#fff,stroke-width:2px
0/1 Knapsack
The classic DP problem where you must choose items with given weights and values to maximize value within a capacity.
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(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(
values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]
)
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5))
print(knapsack([1, 2, 3], [6, 10, 12], 5))
7
22
public class Knapsack {
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
System.out.println(knapsack(weights, values, 5));
}
}
7
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = max(
values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
cout << knapsack(weights, values, 5) << endl;
return 0;
}
7
Longest Common Subsequence
LCS finds the longest subsequence common to two strings, appearing in DNA sequence alignment and diff tools.
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[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]
print(lcs("abcde", "ace"))
print(lcs("abc", "abc"))
print(lcs("abc", "def"))
3
3
0
public class LCS {
public static int lcs(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];
}
public static void main(String[] args) {
System.out.println(lcs("abcde", "ace"));
}
}
3
Coin Change (Unbounded Knapsack)
Find the minimum number of coins needed to make a given amount, where each coin can be used unlimited times.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 2, 5], 11))
print(coin_change([2], 3))
3
-1
Common Mistakes
- Missing base case — Every DP solution needs correct initialization.
dp[0][0]ordp[0]must represent the empty-subproblem answer. - Wrong iteration order — 0/1 knapsack iterates capacity descending in 1D optimization. Unbounded knapsack iterates ascending. Mixing them produces wrong results.
- Confusing subsequence with substring — Subsequences can skip characters (DP required). Substrings are contiguous (Sliding Window suffices).
- Overflow with large values — Use
float('inf')in Python,Integer.MAX_VALUE / 2in Java, or a large sentinel value to avoid overflow in min comparisons. - Assuming greedy works — Coin change and knapsack are classic DP problems where greedy gives suboptimal results. Verify optimal substructure before using DP.
- Ignoring space optimization — Many 2D DP problems can be reduced to 1D. Mention this trade-off in interviews for bonus points.
- Not tracing the solution — DP tables tell you the optimal value but not the choice. Store decisions in a separate table if reconstruction is needed.
Practice Questions
1. Find the longest increasing subsequence (LIS).
Use DP with O(n^2) or binary search with O(n log n). The DP approach stores the length of LIS ending at each index.
2. Solve the edit distance (Levenshtein distance) problem.
Minimum number of insert, delete, and replace operations to convert one string to another. Use DP with three-way transitions.
3. Challenge: Burst Balloons (Leetcode 312)
Given an array of balloon values, bursting a balloon coins value = nums[left] * nums[i] * nums[right]. Find maximum coins. Use divide-and-conquer DP.
FAQ
Related Tutorials
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-23.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro