This directory contains solutions to the 19 dynamic programming problems from the CSES Problem Set. These problems teach fundamental DP concepts and techniques.
After solving these problems, you should be comfortable with:
- Basic DP concepts and memoization
- State transitions and recurrence relations
- 1D and 2D DP problems
- Knapsack variations (bounded, unbounded, with groups)
- Digit DP techniques
- Game theory with DP
- String DP problems
- Advanced optimization techniques
- Clearly define what information you need to remember
- Keep states as simple as possible
- Avoid redundant information
- Express current state in terms of smaller subproblems
- Ensure all base cases are covered
- Verify the relation is correct
- Memoization: Top-down approach, recursive with memory
- Tabulation: Bottom-up approach, iterative
- Choose based on problem constraints
- Often only need previous states
- Use rolling arrays for 1D DP
- Consider if we can solve in-place
- Dice Combinations: Introduction to DP with simple recurrence
- Minimizing Coins: Classic coin change problem
- Coin Combinations I: Unbounded knapsack variant
- Coin Combinations II: Bounded knapsack with ordering
- Removing Digits: Digit DP introduction
- Grid Paths: 2D DP with constraints
- Book Shop: Standard knapsack problem
- Money Sums: Subset sum problem
- Removal Game: Game theory + DP
- Two Sets II: Subset sum with constraints
- Beautiful Permutation: Permutation counting with DP
- Go Go Turtle: Complex state transitions
- Decreasing String: String manipulation with DP
- School Excursion: Knapsack with group constraints
- Counting Numbers: Basic digit DP
- Counting Numbers II-V: Progressively harder digit DP problems
- Advanced optimization techniques
- Complex state management
- Start Simple: Begin with basic recurrence, optimize later
- Test Cases: Always test with edge cases and small examples
- State Compression: Use bit manipulation when possible
- Memory Management: Be careful with large DP tables
- Modulo Operations: Handle large numbers properly
- Solve in Order: Start with basic problems, progress to advanced
- Understand Patterns: Look for similarities between problems
- Implement Multiple Solutions: Try both memoization and tabulation
- Optimize: Practice space and time optimizations
- Review: Revisit problems to reinforce concepts
Master Dynamic Programming to become a competitive programming champion! 🚀