Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithms
greedy

# What is the optimal substructure? Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

A problem has an optimal substructure if its optimal solution can be constructed from the optimal solutions of its subproblems.

## Example

For instance, consider the 0/1 knapsack problem: Given a set of $n$ items with their weights and values and a knapsack of capacity $C$, put in the items that maximize the value such that the sum of the weights does not exceed $C$.

The maximum value can be obtained by taking the max of the following two values:

1. The maximum value obtained by adding $n-1$ items (excluding the $n^{th}$ item).
2. Value of the $n^{th}$ item plus maximum value obtained by adding $n-1$ items. (This can only be done if adding the $n^{th}$ item does not exceed the capacity of the bag).

Notice that the maximum value obtained by adding $n-1$ items is the optimal solution to a subproblem. The optimal solution of the problem can be constructed using the optimal solutions of the sub-problems. Hence, the 0/1 Knapsack problem has an ​optimal substructure.

## Uses

• Dynamic programming can be used to solve a problem with optimal substructure and overlapping subproblems.

• Greedy algorithms may be used to solve a problem with optimal substructure.

RELATED TAGS

algorithms
greedy 