juniorDynamic Programming
What are the two key attributes of a DP problem?
Updated Apr 28, 2026
Short answer
Overlapping Subproblems and Optimal Substructure.
Deep explanation
Dynamic Programming (DP) is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. Overlapping Subproblems and Optimal Substructure.
Real-world example
Cashiers giving change using the minimum number of coins.
Common mistakes
- Creating a memoization table but forgetting to check it before recursing.
Follow-up questions
- What is the space complexity of this Fibonacci approach?