Thursday, December 03, 2020

Types of Dynamic Programming

For coding interviews, the most common types of DP problems are: 1. Knapsack - 0-1 - Bounded - Unbounded 2. LCS 3. LIS 4. Matrix chain multiplication 5. DP on grid 6. Kadane's algorithm etc Advanced Dynamic Programming 1. Kth lexicographical string 2. DP on Tree 3. DP + bitmasking 4. DP + BIT/Segment tree 5. DP + convex hull Mostly, this is for competitive programming.

Monday, November 30, 2020

Edit Distance - Dynamic Programming










 

Data Structure Operations Cheat Sheet


 

Sorting Algorithms Cheat Sheet


 

Look for Similarities Between Problems

 It is always a good idea to look for similarities between problems. By studying the differences and similarities between two problems, one usually gains insight into both problems. Given a new problem, the first question should be in almost all cases, "Is this problem similar to a known problem?" Sometimes, the similarities between two problems become apparent only after complicated reductions are exhibited. The reductions between matrix and graph algorithms are especially interesting.  

Eulerian Graphs







Longest Increasing Subsequence










Binary Search in a Cyclic Sequence



 

The Knapsack Problem













Finding the Maximum Consecutive Subsequence

 









The Skyline Problem

 





The Celebrity Problem