Java solutions for the DP round — 0/1 and unbounded knapsack, LIS, LCS, edit distance, coin change (minimum coins and number of ways), partition equal subset sum, house robber I and II, matrix chain multiplication, burst balloons, unique paths (with and without obstacles), minimum path sum, jump game I and II, climbing stairs, decode ways, word break, maximal square, rod cutting, palindrome partitioning II, egg dropping, target sum, distinct subsequences, and stock trading with k transactions.
Published September 25, 2026
For every DP problem, say these four things out loud:
dp[i] (or dp[i][j]) means;Then mention space optimisation (rolling arrays). Start from recursion plus memoisation if that's clearer, then convert it to a table.
Learn it in depth → DP Introduction
Short answer:
dp[w] = max(dp[w], dp[w - wt] + val), iterating the capacity downwards, so each item counts once. O(n·W) time, O(W) space.int knapsack01(int[] wt, int[] val, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < wt.length; i++)
for (int w = W; w >= wt[i]; w--) dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
int unboundedKnapsack(int[] wt, int[] val, int W) { // rod cutting: wt = lengths 1..n, val = prices
int[] dp = new int[W + 1];
for (int i = 0; i < wt.length; i++)
for (int w = wt[i]; w <= W; w++) dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
Learn it in depth → Knapsack Patterns
Short answer:
dp[i] = 1 + max(dp[j]) for j < i with a[j] < a[i].tails[k] = the smallest tail of an increasing subsequence of length k+1; binary-search the position of each element, and replace or append. The length of tails is the answer. (Practice)int lengthOfLIS(int[] a) {
int[] tails = new int[a.length]; int size = 0;
for (int x : a) {
int i = Arrays.binarySearch(tails, 0, size, x);
if (i < 0) i = -(i + 1);
tails[i] = x;
if (i == size) size++;
}
return size;
}
Short answer:
dp[i][j] = dp[i-1][j-1] + 1 if the characters match, else max(dp[i-1][j], dp[i][j-1]).dp[i][j] = dp[i-1][j-1]; otherwise 1 + min(insert dp[i][j-1], delete dp[i-1][j], replace dp[i-1][j-1]). The base cases are dp[i][0] = i and dp[0][j] = j.Both are O(m·n), and can be reduced to O(min(m, n)) space with rolling rows.
int lcs(String a, String b) {
int[][] dp = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++) for (int j = 1; j <= b.length(); j++)
dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1) ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[a.length()][b.length()];
}
int minDistance(String a, String b) {
int m = a.length(), n = b.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++)
dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1) ? dp[i - 1][j - 1]
: 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
return dp[m][n];
}
Learn it in depth → LCS & String DP
Short answer:
dp[a] = min(dp[a - c] + 1), with dp[0] = 0, and "infinity" for unreachable amounts. O(amount × coins). (Coin Change)dp[a] += dp[a - c], with dp[0] = 1. (Swapping the loops counts permutations instead.)int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
int change(int amount, int[] coins) {
int[] dp = new int[amount + 1]; dp[0] = 1;
for (int c : coins) for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
return dp[amount];
}
Short answer:
total/2: a boolean dp over the sums, iterating downwards. O(n·sum).P = (total + target) / 2. Count the subsets that sum to P (0/1 counting knapsack). Check the parity, and that |target| ≤ total.boolean canPartition(int[] a) {
int total = Arrays.stream(a).sum(); if (total % 2 == 1) return false;
boolean[] dp = new boolean[total / 2 + 1]; dp[0] = true;
for (int x : a) for (int s = total / 2; s >= x; s--) dp[s] |= dp[s - x];
return dp[total / 2];
}
int findTargetSumWays(int[] a, int target) {
int total = Arrays.stream(a).sum();
if (Math.abs(target) > total || (total + target) % 2 == 1) return 0;
int p = (total + target) / 2; int[] dp = new int[p + 1]; dp[0] = 1;
for (int x : a) for (int s = p; s >= x; s--) dp[s] += dp[s - x];
return dp[p];
}
Short answer:
dp[i] = max(dp[i-1], dp[i-2] + a[i]), with two variables: O(n), O(1). (House Robber)[0 .. n-2] and robbing [1 .. n-1].int robLinear(int[] a, int lo, int hi) {
int prev = 0, cur = 0;
for (int i = lo; i <= hi; i++) { int next = Math.max(cur, prev + a[i]); prev = cur; cur = next; }
return cur;
}
int robCircle(int[] a) {
if (a.length == 1) return a[0];
return Math.max(robLinear(a, 0, a.length - 2), robLinear(a, 1, a.length - 1));
}
Short answer: These are interval DP problems: dp[i][j] is the best result for the interval i..j, trying every split point k, and filling by increasing interval length. O(n³).
dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j].(i, j): dp[i][j] = max over k of dp[i][k] + dp[k][j] + v[i]·v[k]·v[j].int maxCoins(int[] nums) {
int n = nums.length + 2; int[] v = new int[n]; v[0] = v[n - 1] = 1;
System.arraycopy(nums, 0, v, 1, nums.length);
int[][] dp = new int[n][n];
for (int len = 2; len < n; len++)
for (int i = 0; i + len < n; i++) {
int j = i + len;
for (int k = i + 1; k < j; k++) dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]);
}
return dp[0][n - 1];
}
int matrixChain(int[] p) { // matrices A1..An, Ai is p[i-1] x p[i]
int n = p.length - 1; int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]);
}
return dp[1][n];
}
Learn it in depth → Interval DP
Short answer: These are grid DP problems, with a single rolling row:
dp[j] += dp[j-1] (paths from above plus from the left). The closed form is C(m+n-2, m-1).dp[j] = 0 on an obstacle.dp[j] = grid[i][j] + min(dp[j], dp[j-1]).All are O(m·n) time, O(n) space.
int uniquePathsWithObstacles(int[][] g) {
int n = g[0].length; int[] dp = new int[n]; dp[0] = 1;
for (int[] row : g)
for (int j = 0; j < n; j++) {
if (row[j] == 1) dp[j] = 0;
else if (j > 0) dp[j] += dp[j - 1];
}
return dp[n - 1];
}
int minPathSum(int[][] g) {
int n = g[0].length; int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;
for (int[] row : g)
for (int j = 0; j < n; j++) dp[j] = row[j] + (j == 0 ? dp[0] : Math.min(dp[j], dp[j - 1]));
return dp[n - 1];
}
Short answer:
i > furthest. O(n). (Jump Game)i reaches the end of the current range, jump (count++), and extend the range. O(n).boolean canJump(int[] a) {
int far = 0;
for (int i = 0; i < a.length; i++) { if (i > far) return false; far = Math.max(far, i + a[i]); }
return true;
}
int jump(int[] a) {
int jumps = 0, curEnd = 0, far = 0;
for (int i = 0; i < a.length - 1; i++) {
far = Math.max(far, i + a[i]);
if (i == curEnd) { jumps++; curEnd = far; }
}
return jumps;
}
Short answer:
ways(n) = ways(n-1) + ways(n-2). O(n) time, O(1) space. (O(log n) with matrix exponentiation.) (Climbing Stairs)dp[i] = (s[i-1] != '0' ? dp[i-1] : 0) + (10 ≤ two-digit ≤ 26 ? dp[i-2] : 0). Zeros are the trap: "0", "06" and "30" can't be decoded as single digits.int climbStairs(int n) { int a = 1, b = 1; for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; } return b; }
int numDecodings(String s) {
int prev2 = 1, prev1 = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= s.length(); i++) {
int cur = s.charAt(i - 1) != '0' ? prev1 : 0;
int two = Integer.parseInt(s.substring(i - 2, i));
if (two >= 10 && two <= 26) cur += prev2;
prev2 = prev1; prev1 = cur;
}
return prev1;
}
Short answer: dp[i] = "the prefix s[0..i) can be segmented". dp[i] = OR over j of (dp[j] && dict.contains(s[j..i))). Limit j to i - maxWordLen, which gives O(n·L). A trie avoids creating substrings. (Word Break)
boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int maxLen = words.stream().mapToInt(String::length).max().orElse(0);
boolean[] dp = new boolean[s.length() + 1]; dp[0] = true;
for (int i = 1; i <= s.length(); i++)
for (int j = Math.max(0, i - maxLen); j < i && !dp[i]; j++) dp[i] = dp[j] && dict.contains(s.substring(j, i));
return dp[s.length()];
}
Short answer: dp[i][j] = the side of the largest all-1s square with its bottom-right corner at (i, j). It's 1 + min(top, left, top-left) when the cell is '1'. The answer is the (maximum side)². O(m·n), with O(n) space in a rolling version.
int maximalSquare(char[][] m) {
int rows = m.length, cols = m[0].length, best = 0; int[][] dp = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++)
if (m[i - 1][j - 1] == '1') {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
best = Math.max(best, dp[i][j]);
}
return best * best;
}
Short answer:
pal[j][i].cuts[i] = the minimum cuts for s[0..i]: 0 if the whole prefix is a palindrome; otherwise min(cuts[j-1] + 1) over the j where s[j..i] is a palindrome.O(n²) time and space. (Expanding around centres removes the pal table.)
int minCut(String s) {
int n = s.length(); boolean[][] pal = new boolean[n][n]; int[] cuts = new int[n];
for (int i = 0; i < n; i++) {
cuts[i] = i; // worst case: cut between every character
for (int j = 0; j <= i; j++)
if (s.charAt(j) == s.charAt(i) && (i - j < 2 || pal[j + 1][i - 1])) {
pal[j][i] = true;
cuts[i] = j == 0 ? 0 : Math.min(cuts[i], cuts[j - 1] + 1);
}
}
return cuts[n - 1];
}
Short answer:
dp[e][f] = the minimum number of trials, is O(e·f²) (O(e·f log f) with a binary search on the split floor).dp[m][e] = the maximum number of floors you can check with m moves and e eggs: dp[m][e] = dp[m-1][e-1] + dp[m-1][e] + 1 (the egg breaks, so check below; it survives, so check above; plus the current floor). Find the smallest m with dp[m][e] ≥ floors. O(e · m), with m ≤ floors.int superEggDrop(int eggs, int floors) {
int[] dp = new int[eggs + 1]; int moves = 0;
while (dp[eggs] < floors) {
moves++;
for (int e = eggs; e >= 1; e--) dp[e] = dp[e - 1] + dp[e] + 1;
}
return moves;
}
Short answer: Count the ways t appears as a subsequence of s. dp[i][j] is the count for s[0..i) and t[0..j): it's dp[i-1][j] (skip s[i-1]), plus dp[i-1][j-1] if s[i-1] == t[j-1]. The base case is dp[i][0] = 1. It's O(m·n), or one row, iterating j downwards. Use long (the counts get large).
int numDistinct(String s, String t) {
long[] dp = new long[t.length() + 1]; dp[0] = 1;
for (int i = 1; i <= s.length(); i++)
for (int j = t.length(); j >= 1; j--)
if (s.charAt(i - 1) == t.charAt(j - 1)) dp[j] += dp[j - 1];
return (int) dp[t.length()];
}
Short answer: This is a state-machine DP. buy[j] = the best balance after the j-th buy; sell[j] = the best balance after the j-th sell. For each price: buy[j] = max(buy[j], sell[j-1] - p) and sell[j] = max(sell[j], buy[j] + p). O(n·k). If k ≥ n/2, it's effectively unlimited: sum every positive difference. (Stock I)
int maxProfit(int k, int[] prices) {
if (k >= prices.length / 2) {
int profit = 0;
for (int i = 1; i < prices.length; i++) profit += Math.max(0, prices[i] - prices[i - 1]);
return profit;
}
int[] buy = new int[k + 1], sell = new int[k + 1]; Arrays.fill(buy, Integer.MIN_VALUE);
for (int p : prices)
for (int j = 1; j <= k; j++) {
buy[j] = Math.max(buy[j], sell[j - 1] - p);
sell[j] = Math.max(sell[j], buy[j] + p);
}
return sell[k];
}
Learn it in depth → State-Machine DP
Q: Memoisation (top-down) or tabulation (bottom-up)? A: Top-down is easier to derive and computes only the reachable states, but it uses recursion (with stack limits) and hashing overhead. Bottom-up is iterative, faster in practice, and makes space optimisation (rolling arrays) easy.
Q: How do you know a problem is DP? A: It asks for an optimum or a count over choices, the same sub-problems repeat (overlapping sub-problems), and the best answer is built from the best sub-answers (optimal substructure).
Q: Why does the loop direction matter in 1-D knapsack? A: Iterating the capacity downwards reads values from the previous item's row (each item is used at most once); iterating upwards reads values already updated for the same item (unlimited reuse).
Q: How do you reconstruct the actual solution, not just its value? A: Keep the full table (or a parent/choice table), then walk back from the answer cell following the transitions that produced each value.