optimal substructure
The property that an optimal solution to a problem is built from optimal solutions to its subproblems.
In more detail
A shortest path from A to C through B contains a shortest path from A to B. Both greedy algorithms and dynamic programming need it; DP adds overlapping subproblems and greedy adds the greedy-choice property.
Related terms
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- overlapping subproblems — The property that a recursive solution solves the same subproblems again and again.
- greedy-choice property — The property of a problem that a globally best solution can always be reached by making the locally best choice at each step.
Taught in
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers