Overlapping Subproblem

March 1, 2022

Overlapping Subproblem

Overlapping Subproblem is one of the main features of the Dynamic Programming Problem. This is an article to briefly discuss this feature of Dynamic Programming, the cause of it and the optimization of it.

Overlapping Subproblem | PrepInsta

What is Overlapping Subproblem?

The phrase consists of two parts. Subproblem clearly means when there are sub parts of a comparably bigger problem, and overlapping indicates if the similar kind of data is parsed, used or came across more than once.

Example

Suppose we have to find the fibonacci Series. So, if we say F(n) is the nth Fibonacci number, we can say F(n) = F(n-1) + F(n-2). So suppose we have to find the 5th FIbonacci number. So, F(5) = F(4) + F(3). So if we create a function F(n) that will recursively call F(n-1) and return n+F(n-1) until n=0.

So, when we need F(5), we have to call F(4) and F(3). Again when F(4) is needed, we need F(3) and F(2). So here we can see, F(3) is actually needed two times only in this instance. Let us see how many times we need to find the F(3).

The code to implement this:

#include <bits/stdc++.h>
using namespace std;
map<int,int> m;

int Fibonacci(int n)
{
    cout<<"Fibonacci ("<<n<<") is called "<<m[n]++<<" times."<<endl;
    if(n==0|n==1) return n;
    int a=Fibonacci(n-1)+Fibonacci(n-2);
    return a;
}

int main()
{
    cout<<"This is Now the 5th Fibonacci Number in  Recursive way: \n";
    cout<<Fibonacci(5);
}

Output:

This is Now the 5th Fibonacci Number in Recursive way: 
Fibonacci (5) is called 0 times.
Fibonacci (4) is called 0 times.
Fibonacci (3) is called 0 times.
Fibonacci (2) is called 0 times.
Fibonacci (1) is called 0 times.
Fibonacci (0) is called 0 times.
Fibonacci (1) is called 1 times.
Fibonacci (2) is called 1 times.
Fibonacci (1) is called 2 times.
Fibonacci (0) is called 1 times.
Fibonacci (3) is called 1 times.
Fibonacci (2) is called 2 times.
Fibonacci (1) is called 3 times.
Fibonacci (0) is called 2 times.
Fibonacci (1) is called 4 times.
5

So, here some of the numbers are needed more than 1 time. This is called the Overlapping Subproblems. This increase in the time complexity and also in the stack space. If we want to reduce the time complexity, we can use memoization and store the already got values in a lookup table for future use. Check this Page: Memoization vs Tabulation for more details.