Optimal substructure
Overview
A problem has optimal substructure if an optimal solution to it contains optimal solutions to its subproblems.
It tells you that cached sub-answers can be safely combined to form the final correct answer.
Where used: Dynamic Programming, Greedy Algorithms, Shortest path algorithms
Why learn this
- It is the second diagnostic test to confirm if a problem is a DP problem.
- Together with overlapping subproblems, this proves that breaking a problem down and caching its pieces will yield the mathematically correct optimal answer.
Common mistakes
- Conflating overlapping subproblems and optimal substructure: They are different properties. Overlapping subproblems means caching helps performance. Optimal substructure means the problem can be solved by combining optimal sub-answers. Both are required for DP.
- Assuming all path problems have it: Shortest simple path has optimal substructure (a sub-path of a shortest path is also shortest). Longest simple path does NOT have optimal substructure, because the sub-paths cannot be independently combined without creating cycles.
Recall questions
- What does it mean for a problem to have optimal substructure?
- What two properties must a problem have to be solvable by Dynamic Programming?
Understanding checks
If a problem has overlapping subproblems but lacks optimal substructure, can you use DP?
No. You can cache the subproblems (overlapping), but combining those cached answers won't give you the correct optimal answer for the larger problem (lacks optimal substructure).
DP requires both properties: caching to save time, and optimal substructure for correctness.
A classmate says: 'Merge sort uses optimal substructure because it combines two sorted halves to sort the full array. That makes it DP.' Why are they wrong?
They are correct that merge sort has optimal substructure. However, it lacks overlapping subproblems (every recursive call sorts a unique portion of the array). Therefore, DP caching doesn't help.
Optimal substructure is required for DP, but it is also present in Divide and Conquer algorithms. The lack of overlapping subproblems is why merge sort isn't DP.
Practice tasks
Shortest Path composition
Modify this recursive shortest-path function to return not just the distance, but the path itself, demonstrating that the optimal path is built from optimal sub-paths.
Challenge
Longest Simple Path
Explain why the longest simple path problem does not have optimal substructure.
Continue learning
Previous: Overlapping subproblems
Next: State & transition