= Optimal substructure
{wiki}
<Optimal substructure> means that the relevant parts of an optimal solution solve their own subproblems optimally. For a <0-1 knapsack problem>, removing a chosen item leaves an optimal selection among the other allowed items at the reduced capacity. For sequential <mathematical optimization>, this becomes the <dynamic programming principle>: after fixing the next decision and resulting <dynamic programming state>, use an optimal continuation. <Optimal substructure> justifies the <recurrence relation>; overlap between subproblems explains why storing a <value function> can save work.
Back to article page
