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