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