Course contentsShow
← Computer Science
Lesson 880 of 2,87221. Greedy AlgorithmsFree lesson

Optimal Substructure in Greedy Problems

Recognize how optimal solutions contain optimal solutions to subproblems in greedy contexts.

Optimal Substructure in Greedy Problems

You'll learn how greedy algorithms rely on building globally optimal solutions from locally optimal choices at each step.

What Is Optimal Substructure?

Optimal substructure means that an optimal solution to a problem contains optimal solutions to its subproblems. In greedy contexts, this property lets you confidently make a local choice without worrying about future consequences—because if your current choice is optimal and you solve the remaining subproblem optimally, the overall solution will be optimal.

Think of it like building a staircase: if each step you place is at the perfect height, and the remaining steps above it are also perfectly placed, your entire staircase will be optimal. You don't need to reconsider earlier steps.

How It Works in Greedy Algorithms

Unlike divide-and-conquer or dynamic programming (where you might explore multiple subproblems), greedy algorithms make one choice at each stage. Optimal substructure guarantees that:

  1. Your greedy choice reduces the problem to a smaller subproblem
  2. Solving that subproblem optimally combines with your choice to form the optimal solution
  3. No backtracking needed—the choice is irrevocable

For example, in the coin change problem with specific denominations, choosing the largest coin that fits always leaves you with a smaller, similar problem. If that remaining problem is solved optimally, your entire solution is optimal.

Why Both Properties Matter

Remember: greedy needs both the Greedy Choice Property (making a locally optimal choice) and Optimal Substructure (subproblems solve independently). Without optimal substructure, a greedy choice might paint you into a corner with no way to recover.

Key Takeaway: Optimal substructure in greedy problems ensures that once you make the best local choice, solving what remains optimally guarantees a globally optimal solution—no second-guessing required.