Dynamic Programming
Go to ProblemsDynamic Programming Interview Questions
Following are the top Dynamic Programming Interview Questions:
- 0-1 Knapsack Problem
- Travelling Salesman Problem (TSP)
- Word Break Problem (With Solution)
- Coin Change Problem
- Edit Distance Problem
- Friends Pairing Problem
- Subset Sum Problem
- Minimum Number of Jumps
- Longest Increasing Subsequence
- Painters Partition Problem
- Longest Common Subsequence
- Climbing Stairs Problem
- Maximum Subarray Sum: Kadane’s Algorithm
- Longest Common Substring
- Longest Palindromic Substring
Dynamic Programming Problems
2d string dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Longest Common Subsequence | 200 |
|
42:05 | |
| Longest Palindromic Subsequence | 200 |
|
41:12 | |
| Edit Distance | 300 |
|
47:01 | |
| Repeating Sub-Sequence | 300 |
|
64:12 | |
| Distinct Subsequences | 325 |
|
65:51 | |
| Scramble String | 500 |
|
72:54 | |
| Regular Expression Match | 500 |
|
79:41 | |
| Regular Expression II | 500 |
|
70:41 | |
| Interleaving Strings | 500 |
|
62:15 |
Simple array dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Length of Longest Subsequence | 200 |
|
65:01 | |
| Smallest sequence with given Primes | 200 |
|
67:33 | |
| Largest area of rectangle with permutations | 200 |
|
76:53 | |
| Tiling With Dominoes | 200 |
|
63:46 | |
| Paint House! | 200 |
|
41:35 | |
| Ways to Decode | 225 |
|
70:08 | |
| Stairs | 225 |
|
15:14 | |
| Longest Increasing Subsequence | 300 |
|
30:39 | |
| Intersecting Chords in a Circle | 300 |
|
70:18 |
Greedy or dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Tushar's Birthday Bombs | 200 |
|
80:40 | |
| Jump Game Array | 225 |
|
41:16 | |
| Min Jumps Array | 300 |
|
71:56 |
Dp tricky
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Longest Arithmetic Progression | 200 |
|
75:50 | |
| N digit numbers with digit sum S | 200 |
|
73:15 | |
| Shortest common superstring | 200 |
|
58:53 | |
| Ways to color a 3xN Board | 200 |
|
65:27 | |
| Kth Manhattan Distance Neighbourhood | 200 |
|
64:27 | |
| Best Time to Buy and Sell Stock atmost B times | 200 |
|
63:41 | |
| Coins in a Line | 300 |
|
63:59 | |
| Evaluate Expression To True | 350 |
|
72:21 | |
| Egg Drop Problem! | 450 |
|
56:17 | |
| Best Time to Buy and Sell Stocks III | 700 |
|
64:45 | |
| Longest valid Parentheses | 700 |
|
62:33 |
Tree dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Max edge queries! | 200 |
|
57:34 | |
| Max Sum Path in Binary Tree | 400 |
|
55:23 |
Matrix dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Kingdom War | 200 |
|
60:45 | |
| Maximum Path in Triangle | 200 |
|
33:37 | |
| Maximum Size Square Sub-matrix | 200 |
|
44:49 | |
| Increasing Path in Matrix | 200 |
|
47:20 | |
| Minimum Difference Subsets! | 200 |
|
51:59 | |
| Subset Sum Problem! | 200 |
|
45:46 | |
| Unique Paths in a Grid | 300 |
|
34:08 | |
| Dungeon Princess | 300 |
|
71:52 | |
| Min Sum Path in Matrix | 300 |
|
30:33 | |
| Min Sum Path in Triangle | 300 |
|
43:26 | |
| Max Rectangle in Binary Matrix | 350 |
|
79:19 | |
| Rod Cutting | 350 |
|
76:15 | |
| Queen Attack | 350 |
|
61:42 | |
| Dice Throw | 400 |
|
49:36 |
Suffix / prefix dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Sub Matrices with sum Zero | 200 |
|
75:37 | |
| Coin Sum Infinite | 225 |
|
65:14 | |
| Max Product Subarray | 300 |
|
65:25 | |
| Best Time to Buy and Sell Stocks I | 300 |
|
28:13 | |
| Arrange II | 350 |
|
73:39 |
Derived dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Chain of Pairs | 200 |
|
44:12 | |
| Max Sum Without Adjacent Elements | 225 |
|
58:16 | |
| Merge elements | 300 |
|
64:11 |
Knapsack
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Flip Array | 200 |
|
81:31 | |
| Tushar's Birthday Party | 200 |
|
72:55 | |
| 0-1 Knapsack | 200 |
|
49:10 | |
| Equal Average Partition | 350 |
|
75:08 |
Dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Potions | 200 |
|
52:44 |
Adhoc
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Best Time to Buy and Sell Stocks II | 225 |
|
40:18 |
Dp optimized backtrack
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Word Break II | 350 |
|
68:51 |
Multiply dp
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Unique Binary Search Trees II | 400 |
|
36:29 | |
| Count Permutations of BST | 400 |
|
60:03 |
Breaking words
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Palindrome Partitioning II | 400 |
|
62:59 | |
| Word Break | 400 |
|
68:16 |
