All Patterns
🧩
hardPattern #07
Dynamic Programming
Break the problem into overlapping subproblems and cache results.
What is this pattern?
DP identifies optimal substructure: the solution to a problem depends on solutions to smaller instances. You define a recurrence relation and fill a table (bottom-up) or memoize recursive calls (top-down), trading exponential time for polynomial.
When to use it
- Counting ways, maximizing/minimizing a value, or checking feasibility
- Problem can be broken into overlapping subproblems
- Keywords: "minimum cost", "maximum profit", "number of ways", "can you reach"
- Greedy doesn't work — local optimal ≠ global optimal
Key Insight
Define dp[i] clearly before writing any code. Ask: "what does dp[i] represent?" Then write the recurrence and base cases. The transition almost always looks at dp[i-1] or dp[i-w] or dp[i][j-1].
Pro Content
The Java template and practice problems for this pattern are part of the Pro plan. Upgrade to unlock all patterns, 500+ problems, and Aria code reviews.
From ₹3,999 for a year · one-time, no auto-renewal