Skip to content
Menu
中文Sign in
← All questions

What does optimal substructure mean in dynamic programming?

Optimal substructure means that the optimal solution to the overall problem can be constructed by efficiently combining the optimal solutions of its subproblems. In the route example, once the shortest SF→LA and LA→SD segments are known, they combine to give the shortest SF→SD route.

Conditions

  • The problem can be divided into subproblems.
  • The optimal solution of the main problem depends on the optimal solutions of its subproblems.

Reasoning, step by step

  1. Identify the definition of optimal substructure.
  2. Understand that the optimal solution to the main problem can be constructed from the optimal solutions of its subproblems.
  3. Apply this concept to the shortest-path example: SHORTESTPATH(SF,SD)=SHORTESTPATH(SF,LA)+SHORTESTPATH(LA,SD)SHORTEST_PATH(SF, SD) = SHORTEST_PATH(SF, LA) + SHORTEST_PATH(LA, SD).

Example

The video uses a map route from San Francisco to San Diego via Los Angeles to illustrate optimal substructure.

Common misconceptions

  • Assuming that any problem with subproblems has optimal substructure.
  • Confusing optimal substructure with overlapping subproblems.

Watch the explanation

2:05 – 3:02Watch this moment ↗

Explore next

Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.