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 nn items with their weights and values and a knapsack of capacity CC, put in the items that maximize the value such that the sum of the weights does not exceed CC.

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

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

Notice that the maximum value obtained by adding n1n-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
Copyright ©2022 Educative, Inc. All rights reserved

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.

Keep Exploring