ConceptTheory & Algos
Optimal substructure
A property of a problem where an optimal solution to the problem contains optimal solutions to subproblems.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
4Each in their own terms, from the easiest level.
David Silver
A property where an optimal solution can be decomposed into subproblems, and the principle of optimality applies.Erik Demaine
An optimal solution to a problem incorporates optimal solutions to subproblems.Srini Devadas
A property stating that subpaths of a shortest path are themselves shortest paths.
Lectures that assume it
2Connections
13The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Dynamic programming
- Shortest path
- Minimum spanning tree
- Subproblem
- Greedy-choice property
- Overlapping subproblems