optimal substructure

Optimal substructure is a property of a problem where the best solution to the overall problem can be built from the best solutions to its smaller parts. In other words, solving the big problem efficiently involves solving smaller, manageable pieces optimally first. This approach is common in algorithms like dynamic programming, where breaking down problems into optimal sub-solutions makes finding the overall best solution more straightforward and efficient. Essentially, if a problem has optimal substructure, solving its parts correctly guarantees the best overall outcome.