DP Classifications:
- KnapSack Problem
- LIS
- LCS
- Matrix Chain Multiplication
- DP on Grid
- Kadane's Algorithm
- Advanced DP:
- DP Kth Lexicogrophical String
- DP on Tree
- DP + Bitmasking
- DP + Segment Tree
- DP + Convex Hull
- DP + Pre Processing
- DP + Trie
- DP + Geometry
- DP + Binary Search
- DP + Knuth Optimization
Knapsack Problem
-
Knapsack means a bag.
-
Items with Price and Weight are given.
-
We have to fill the bag to get maximum profit.
-
Example:
-Given List of Weights: 3,2,4
-Given List of profits: 8,5,9
-Weight to be filled: 7
-Best possible combination with maximum profit: 4+3=7=Weight with Profit 9+8=17. -
Types of Knapsack:
- 0/1: Can't include an item multiple times.
- Bounded: Can include an item multiple times but with a limit.
- Unbounded: Can include an item multiple times with no limit. -
Types of Knapsack:
- Fractional: Can include a part of an item.
- Integer: Can't include a part of an item. -
Some Knapsack problems variations:
- Subset sum problem
- Partition equals subset problem
- Count of Subsets with particular sum.
- Partition of Set into 2 subsets such that difference of both the subsets should be minimum.
- Target Sum.
Matrix Chain Multiplication
- Given a List of Matrices.
- Find the most efficient way to multiply the matrices together.
- Find the efficient way such that we have minimum no of multiplications.
- Various types of problems including strings,arrays etc.