Dynamic Programming
0/1 Knapsack Pattern
Equal Subset Sum Partition (Also includes Subset Sum - Very Similar)
Unbounded Knapsack
Buy and Sell Stocks (State Machines Concept)
Longest Increasing Subsequence
Minimum Deletions to make a Sequence Sorted
Classic LIS problem. Find the LIS of the sequence and the
deletions = arr.length - LIS.length
Minimum Number of Removals To Make Mountain Array (Very Similar to Bitonic Sequence)
All Possible Cuts in All Possible Intervals For Choosing Last Operation
Merging Stones (Similar to burst balloons)
Kadanes
Explanation - https://www.youtube.com/watch?v=86CQq3pKSUw
The best time to buy and sell 1 stock can also be seen as an application of Kadane's algorithm
2-String Problems
Note: Some of these problems can ask for the length/count of the longest/shortest common substring/sequence or it can also ask for the substring/subsequence produced.
1-String Problems
(Already posted as part of All Possible Cuts in All Possible Intervals For Choosing Last Operation)
Minimum Insertions To Form a Palindrome
You can always just find the Longest Palindromic subsequence and use that.
str.length - LPS.length
will also give you the same answer.Similarly, you can also use the Longest Common Subsequence technique. You need to do an LCS on
str
andstr.reverse()
and thenstr.length - LCS(str, str.reverse())
will give you the same answer.
Advanced String DP Problems
Optimal Path To Target
Includes the Minimum Cost for Tickets Problem
Unique Paths
Other Problems
This fits into the knapsack category. You either choose a house to rob or you skip the house.
Cherry Pickup (This has comments explaining the thought process)
Other Backtracking Problems
Practicing Backtracking problems also helps provide a good foundation and thought process for DP based problems. These are some classic backtracking problems.
The difference between permutations 1 and 2 is that 1 has unique numbers in the input array and 2 has duplicate numbers possible
Similar Problems But slightly different
A few neat optimizationz are done in this solution.
We check if we can even compute a palindrome from the given string. If not we immediately return.
If it's an odd length palindrome, we get the mid point character (1 character which only appears once)
We just take half of the remaining characters and compute all permutations on just half the list. When we have a complete permutation we do
permutation + mid + permutation.reverse()
. This allows us to calculate all possible permutations on just half the string instead of the entire string.For even length palindromes mid will be empty so it will essentailly be
permutation + permutation.reverse()
Last updated
Was this helpful?