This site uses JavaScript for navigation, themes, and games like 2048. Please enable JavaScript in your browser settings, then reload the page.
49 problems. Click one to open the details.
0/49 solved
1.0/1 Knapsack — Recursive
Recursive choice: take or skip each item under capacity W.
2.0/1 Knapsack — Memoization
Cache (n, W) subproblems on top of the recursive knapsack.
3.0/1 Knapsack — Top Down DP
Fill a 2D table for capacity vs items bottom-up.
4.Subset Sum
Decide if any subset sums exactly to target S.
5.Equal Sum Partition
Partition into two equal-sum subsets iff total even and subset-sum(total/2).
6.Count Subsets with Given Sum
Count how many subsets sum to S.
7.Minimum Subset Sum Difference
Split into two subsets with minimum absolute sum difference.
8.Count Subsets with Given Difference
Count partitions with sum difference = D; reduces to subset sum.
9.Target Sum
Assign +/− to each number so the expression equals target.
10.Unbounded Knapsack
Each item may be used unlimited times; maximize value under W.
11.Rod Cutting
Cut a rod of length n to maximize price; unbounded knapsack variant.
12.Coin Change — Maximum Number of Ways
Count combinations to make amount with unlimited coins.
13.Coin Change — Minimum Coins
Fewest coins to make amount; unbounded knapsack minimization.
14.Longest Common Subsequence — Recursive
LCS length via recursion on two string indices.
15.Longest Common Subsequence — Memoization
Memoize LCS(i,j) to avoid exponential recomputation.
16.Longest Common Subsequence — Tabulation
Bottom-up 2D DP for LCS length.
17.Longest Common Substring
Longest contiguous common segment; reset DP when chars differ.
18.Print Longest Common Subsequence
Reconstruct one LCS string by tracing the DP table.
19.Shortest Common Supersequence
SCS length = m + n - LCS; merge while covering both strings.
20.Min Insertions and Deletions A to B
Convert A to B using LCS: deletions = n-LCS, insertions = m-LCS.
21.Longest Palindromic Subsequence
LPS(s) = LCS(s, reverse(s)).
22.Min Deletions to Make Palindrome
n - LPS(s) deletions make s a palindrome.
23.Print Shortest Common Supersequence
Trace DP to emit one shortest common supersequence string.
24.Longest Repeating Subsequence
LCS of s with itself where indices must differ.
25.Sequence Pattern Matching
Is pattern a subsequence of text? LCS(pattern,text)==|pattern|.
26.Min Insertions to Make Palindrome
Same as min deletions: n - LPS.
27.Matrix Chain Multiplication — Recursive
Min cost to multiply matrices; try every split k.
28.Matrix Chain Multiplication — Memoization
Memoize MCM(i,j) over partition points.
29.Palindrome Partitioning — Recursive
Min cuts so every substring is a palindrome.
30.Palindrome Partitioning — Memoization
Memoize min cuts for substring s[i..j].
31.Palindrome Partitioning — Optimized
Precompute palindrome table; optimize cut DP.
32.Boolean Parenthesization — Recursive
Count ways to parenthesize a boolean expression to true.
33.Boolean Parenthesization — Memoization
Memoize ways for (i,j,isTrue) using 3D DP or map.
34.Scramble String — Recursive
Check if one string is a scramble of another via splits.
35.Scramble String — Memoization
Memoize scramble checks on string pairs.
36.Egg Dropping — Recursive
Min worst-case trials with e eggs and f floors.
37.Egg Dropping — Memoization
Memoize eggDrop(eggs, floors) over trial floors.
38.Egg Dropping — Optimized
Binary search the floor choice inside memoized egg DP.
39.DP on Trees — Introduction
Tree DP pattern: answer from left/right child results plus root choice.
40.Diameter of Binary Tree
Longest path between any two nodes; track via height recursion.
41.Maximum Path Sum (Any Node to Any)
Max path sum where path can start and end at any nodes.
42.Max Sum of Non-Adjacent Elements
House-robber style DP on array.
43.Ninja's Training
Max points over days with no same activity twice in a row.
44.Minimum Path Sum in Grid
Only right/down moves; DP min path sum.
45.Assign Cookies
Greedy: sort and assign smallest sufficient cookie.
46.Edit Distance
Min insert/delete/replace to convert word1→word2.
47.Best Time to Buy and Sell Stock IV
At most k transactions; DP states.
48.Longest Increasing Subsequence
LIS length; O(n log n) patience or O(n²) DP.
49.Burst Balloons
Interval DP for max coins bursting balloons.