Related Tags

algorithms
greedy

# What is the optimal substructure?

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