Optimal Substructure and Overlapping Subproblems

It's very necessary to understand the properties of the problem to get the correct and efficient solution. A variety of problems follows some common properties. Understanding these properties help us to find the solutions to these easily.

So In this blog, we will understand the optimal substructure and overlapping subproblems property. We will also discuss how the problems having these two properties can be solved using Dynamic programming. It is very important to understand these properties if you want to solve some problem using DP. So, let's get started.

Optimal Substructure

If the optimal solution to a problem P, of size n, can be calculated by looking at the optimal solutions to subproblems [p1,p2,…](not all the sub-problems) with size less than n, then this problem P is considered to have an optimal substructure.

Let's understand this by taking some examples. Check whether the below problem follows optimal substructure property or not?

Shortest Path Problem

Problem Statement - Consider an undirected graph with vertices a, b, c, d, e and edges (a, b), (a, e), (b, c), (b, e),(c, d) and (d, a) with some respective weights. Find the shortest path between a and c.

This problem can be broken down into finding the shortest path between a & b and then shortest path between b & c and this can give a valid solution i.e. shortest path between a and c.

We need to break this for all vertices between a & c to check the shortest and also direct edge a-c if exits. So the following problem can be broken down into sub-problems and it can be used to find the optimal solution to the bigger problem(also the subproblems are optimal). So this problem has an optimal substructure.

Longest Path Problem

Problem Statement - For the same undirected graph, we need to find the longest path between a and d.

Let us suppose the longest path is a->e->b->c->d, but if we think like the same manner and calculate the longest paths by dividing the whole path into two subproblems i.e. between a & c i.e. (a->e->b->c) and c & d i.e. (c->b->e->a->d), it won’t give us a valid(because we need to use non-repeating vertices) longest path between a & d. So this problem does not follow optimal substructure property because the substructures are not leading to some solution.

Overlapping Subproblems

In some problems, there are many small sub-problems which are computed many times during finding the solutions to the big problem. So, why to compute the same thing again and again?

This property can be used further to optimize the solution using various techniques.

Let us look down and check whether the following problems have overlapping subproblems or not?

Finding the nth fibonacci

This problem follows the property of having overlapping sub-problems. ( Think!)

Hint: Draw the recursion tree for fib(5) and see the overlapping sub-problems.

If you draw the recursion tree for fib(5), then you will find:

fib(5) is called 1 times
fib(4) is called 1 times
fib(3) is called 2 times
fib(2) is called 3 times
fib(1) is called 5 times
fib(0) is called 3 times

i.e. so many repetitive calculations.

Binary Search

In binary search which is solved using the divide-and-conquer approach does not have any common subproblems. Each time the sub-problems come at a unique array to find the element. So, This problem does not follow the property of overlapping sub-problems.

P roperties of a problem that suggests a given problem can be solved using DP

If any problem is having the following two properties, then it can be solved using DP:

Overlapping Subproblems
Optimal Substructure

Overlapping Subproblems

Dynamic Programming is used where solutions of the same subproblems are needed again and again. In dynamic programming pre-computed results of sub-problems are stored in a lookup table to avoid computing same sub-problem again and again. So Dynamic Programming is not useful when there are no overlapping(common) subproblems because there is no need to store results if they are not needed again and again.

From the above diagram, it can be shown that Fib(3) is calculated 2 times, Fib(2) is calculated 3 times and so on.

Optimal Substructure

A problem has an optimal substructure property if an optimal solution of the given problem can be obtained by using the optimal solution of its subproblems. Dynamic Programming takes advantage of this property to find a solution.

In the above example of Fibonacci Number, for the optimal solution of Nth Fibonacci number, we need the optimal solution of (N-1)th Fibonacci number and (N-2)th Fibonacci number.

To get an idea to how to implement the problem having these properties you can refer to this blog Idea of Dynamic Programming