Scribd
Upload
7 views1 page

DP Problems Collection

The document is a collection of dynamic programming (DP) problems categorized into beginner, intermediate, and advanced levels. It includes classic problems such as Fibonacci Numbers, Coin Change, and the Travelling Salesman Problem, along with resources for practice. Each category contains a list of specific problems that help in understanding and applying DP techniques.

Uploaded by

aditya10prakashiit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views1 page

DP Problems Collection

The document is a collection of dynamic programming (DP) problems categorized into beginner, intermediate, and advanced levels. It includes classic problems such as Fibonacci Numbers, Coin Change, and the Travelling Salesman Problem, along with resources for practice. Each category contains a list of specific problems that help in understanding and applying DP techniques.

Uploaded by

aditya10prakashiit
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Dynamic Programming (DP) Problem Collection

### Beginner DP Problems


1. Fibonacci Numbers - Basic recurrence relation.
2. Coin Change (Ways & Min Coins) - Classic DP problem on counting & minimization.
3. Knapsack Problem (0/1 & Unbounded) - Fundamental DP optimization.
4. Longest Increasing Subsequence (LIS) - Key sequence DP problem.
5. Edit Distance - String-based DP problem.
6. Subset Sum Problem - Solving subset sum using DP.
7. Partition Equal Subset Sum - Partitioning array into two subsets.

### Intermediate DP Problems


8. Longest Common Subsequence (LCS) - Classic string DP.
9. Matrix Chain Multiplication - DP on matrix grouping.
10. Rod Cutting Problem - Similar to knapsack DP.
11. Palindrome Partitioning - Finding minimum cuts for palindrome substrings.
12. Catalan Numbers - Counting parenthesization using DP.
13. Digit DP (Counting Numbers with Constraints) - An introduction to digit DP.
14. Weighted Job Scheduling - DP with sorting.

### Advanced DP Problems


15. Bitmask DP (Travelling Salesman Problem - TSP) - NP-hard problem using DP.
16. SOS DP (Sum over Subsets) - Useful in combinatorial DP.
17. Tree DP (Diameter of a Tree, Counting Subtrees) - DP applied on trees.
18. DP on Graphs (Shortest Paths with DP, Floyd-Warshall) - Pathfinding using DP.
19. Dynamic Connectivity DP (Offline Queries on Graphs) - Handling graph updates.
20. Knuth's Optimization (Speeding up DP on Ranges) - Used in matrix chain multiplication.

### Resources to Practice


- Codeforces DP Problemset
- AtCoder DP Contest
- CSES DP Problemset
- USACO Guide (DP Section)
- LeetCode Hard DP Problems

You might also like