Optimal Substructure in Greedy Algorithms
What You'll Learn
You'll understand how optimal substructure allows greedy algorithms to build globally optimal solutions by making locally optimal choices at each step.
The Core Idea
Optimal substructure means that an optimal solution to a problem contains optimal solutions to its subproblems. In greedy algorithms, this property is essential: once you make a greedy choice, you're left with a smaller problem that you can solve the same way.
Think of it like climbing stairs optimally: if the best way to reach the 10th step involves being at the 9th step, then your path to the 9th step must also be optimal. You can't have the best overall route if part of it is suboptimal.
How It Enables Greedy Algorithms
Greedy algorithms work incrementally. At each step, they:
- Make the locally best choice (the greedy choice)
- Reduce the problem to a smaller subproblem
- Recursively solve that subproblem the same way
Optimal substructure guarantees that these local choices combine into a global optimum. After making your greedy choice, the remaining problem has the same structure, and solving it optimally completes your overall optimal solution.
Example: Activity Selection
When selecting activities by earliest finish time, once you pick an activity, the remaining problem is to select optimally from non-overlapping activities. The optimal solution to the full problem includes the optimal solution to this smaller problem.
The Difference
Unlike dynamic programming (which also requires optimal substructure), greedy algorithms make one choice at each step and never reconsider. They don't explore all subproblem solutions—they trust that the greedy choice, combined with an optimal solution to what remains, yields the best overall result.
Key Takeaway: Optimal substructure in greedy algorithms means making the best local choice leaves you with a smaller problem whose optimal solution, combined with your choice, forms the global optimum.