List of dynamic programming (DP) topics in competitive programming, organized from basic to advanced:

Introduction to Dynamic Programming
- Top-Down (Memoization)
- Bottom-Up (Tabulation)
Basic DP Problems
- Fibonacci Numbers
- Factorial Calculation
- Minimum/Maximum Path Sum

1D DP Problems
- Coin Change Problem
- Longest Increasing Subsequence (LIS)
- Longest Decreasing Subsequence
- Longest Common Subsequence (LCS)
- Edit Distance
- Rod Cutting Problem
- Integer Partition
- Subset Sum Problem
2D DP Problems
- 0/1 Knapsack Problem
- Unbounded Knapsack Problem
- Matrix Chain Multiplication
- Grid Unique Paths
- Minimum Path Sum in Grid
String DP Problems
- Palindromic Substrings
- Palindrome Partitioning
- Longest Palindromic Subsequence
Interval DP
- Matrix Chain Multiplication
- Stone Game
- Optimal BST
DP with Bitmasking
- Traveling Salesman Problem (TSP)
- Assignments Problem
Digit DP
- Count Numbers with Specific Properties

DP on Trees
- Tree Diameter
- Tree DP
- Subtree Sizes
- Heavy-Light Decomposition
DP with Two Pointers
- Maximum Subarray Sum
- Sliding Window Problems
Range DP
- Building Bridges
- Maximum Sum Increasing Subsequence
DP with Divide and Conquer Optimization
- Knuth’s Optimization
- Convex Hull Trick
DP with Monotonic Queue/Deque
- Monotonic Queue Optimization
Bitwise Manipulation in DP
- Subset Generation
Inclusion-Exclusion Principle
- Subset Counting
SOS DP (Sum Over Subsets DP)
- Fast Subset Convolution
DP on Graphs
- Shortest Paths (Floyd-Warshall)
- Independent Set on Trees
- Path Counting
DP with Matrix Exponentiation
- Fibonacci Sequence
- Linear Recurrences
Game Theory and DP
- Grundy Numbers
- Nim Game
DP with Persistent Data Structures
- Persistent Segment Trees

Provide feedback

Saved searches