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