optimal substructure
Optimal substructure is a property of a problem that indicates it can be broken down into smaller, simpler subproblems. When these subproblems are solved optimally, their solutions can be combined to form an optimal solution to the original problem. This concept is essential in algorithms like dynamic programming and greedy algorithms.
For example, in the shortest path problem, finding the shortest path from point A to point B can be achieved by first determining the shortest paths from A to intermediate points. If these intermediate paths are optimal, the overall path from A to B will also be optimal, demonstrating the principle of optimal substructure.