Course contentsShow
← Computer Science
Lesson 914 of 2,87222. Dynamic ProgrammingFree lesson

Optimal Substructure Property

Learn how optimal solutions to problems can be constructed from optimal solutions to their subproblems.

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.