The cut-and-paste schema (type it)

Answer

# Cut-and-paste (optimal substructure proof) # 1. Assume optimal S contains a suboptimal subsolution S'. # 2. Replace S' with the optimal S'* (legal: subproblems independent). # 3. Result >= S, contradicting S optimal. # => the subsolution inside S must be optimal.

Memorize this four-line skeleton — the exam asks you to prove optimal substructure for an unseen problem, and you fill in S, S’, and the independence justification.