DP.md

Non-Linear DS

---

Outline

1. Basic concept

2. Top-down Dynamic Programming

3. Bottom-up Dynamic Programming

4. Top-down vs Bottom-up

5. Printing the optimal solution

6. Memory optimization

7. Classical Examples

   1. Max 1D Range Sum
   2. Max 2D Range Sum
   3. Longest Increasing Subsequence (LIS)
   4. 0-1 Knapsack (Subset Sum)
   5. Coin Change (CC)
   6. Traveling Salesman Problem (TSP)

8. Non Classical Examples

---

Material Resources

Resource	Points Covered
CP section: 3.5	All outline points
TC DP from Novice to Advanced	1,2,3
HE Intro to DP	1,2,3,4
G4G DP	All outline points

---

Problem Sets

Problem Set #1

Problem	Tags	Notes	Solution

Problem Set #2

Problem	Tags	Notes	Solution