Optimal Substructure Property
What You'll Learn
You'll learn how to recognize when a problem's optimal solution can be built from optimal solutions to smaller subproblems—the foundation of dynamic programming.
The Core Idea
Optimal substructure means that the best solution to a big problem is made up of the best solutions to smaller pieces of that same problem.
Think of it like building a skyscraper: if you want the tallest, strongest building, you need the tallest, strongest foundation and the tallest, strongest floors stacked on top. A suboptimal foundation ruins the whole structure, no matter how good the upper floors are.
In algorithmic terms, if you're solving problem P and you can break it into subproblems P₁, P₂, ... Pₙ, then:
- The optimal solution to P contains optimal solutions to P₁, P₂, ... Pₙ
- You cannot get the best answer for P by using non-optimal answers for any subproblem
Why This Matters
Optimal substructure is one of the two key properties that make dynamic programming work (the other being overlapping subproblems, which you'll learn later). Without it, you can't combine solutions to smaller problems to solve larger ones correctly.
Example: Shortest Path
Finding the shortest path from A to C through B has optimal substructure:
- If the shortest A→C path goes through B, then the A→B portion must be the shortest A→B path
- If you used a longer A→B route, you could swap it for the shortest one and get a better A→C path—contradicting that you started with the optimal one
This is why greedy and dynamic programming approaches can work on shortest path problems.
Key Takeaway: A problem has optimal substructure if its optimal solution is composed of optimal solutions to its subproblems—allowing you to build up solutions from smaller pieces.