juniorDynamic Programming
What is Optimal Substructure?
Updated Apr 28, 2026
Short answer
An optimal solution to the problem contains optimal solutions to its subproblems.
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. An optimal solution to the problem contains optimal solutions to its subproblems.
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?