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