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.
Articles by others on the same topic
There are currently no matching articles.