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.