Introduction to Dynamic Programming (DP)
Dynamic Programming is an optimization over plain recursion. It is used when a problem has:
- Overlapping Subproblems: You solve the same smaller problems multiple times.
- Optimal Substructure: The optimal solution to the main problem can be constructed from optimal solutions of its subproblems.
1. The DP Framework: Top-Down vs. Bottom-Up
Top-Down (Memoization)
You start with the big problem and break it down. You use a "Cache" (usually a Map or Array) to store results of subproblems so you don't calculate them twice.
Pattern: Recursion + Cache.
Bottom-Up (Tabulation)
You start with the smallest subproblems (base cases) and build up to the big problem using a table (array).
Pattern: Iterative loop + DP Array.
2. Curriculum in this Module
- Theory & Intuition (Current Page)
- Lesson: The 0/1 Knapsack Pattern - The king of DP patterns.
- Problem: Longest Increasing Subsequence - Mastering the $O(n^2)$ to $O(n \log n)$ transition.
- Problem: Coin Change - Minimum steps to a target.
- Curated Practice Problems - 10 essential challenges.
3. How to Spot a DP Problem in 5 Seconds
- It asks for Maximum, Minimum, or Total number of ways.
- You can't use a Greedy approach because local choices affect global outcomes.
- The input is an array or string where you need to make a series of dependent decisions.
Final Takeaway
DP is just Recursion + Common Sense (Memory). If you can write the recursive solution, you are 90% of the way to a DP solution.