Dynamic Programming
Go to Problems- Dynamic Programming (commonly referred to as DP) is an algorithmic technique for solving a problem by recursively breaking it down into simpler subproblems and using the fact that the optimal solution to the overall problem depends upon the optimal solution to it’s individual subproblems.
- The technique was developed by Richard Bellman in the 1950s.
- DP algorithm solves each subproblem just once and then remembers its answer, thereby avoiding re-computation of the answer for similar subproblem every time.
- It is the most powerful design technique for solving optimization related problems.
-
It also gives us a life lesson - Make life less complex. There is no such thing as big problem in life. Even if it appears big, it can be solved by breaking into smaller problems and then solving each optimally. Learn More.
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 |
