Explain Overlapping Subproblems Property Using program in Python

To understand the overlapping subproblems, we will take the example of the Fibonacci series.

Fibonacci series is the sequential representation in which the next number is the sum of the previous numbers.

eg:  { 0 1 1 2 3 5 8 13 21.......}

Suppose we want to calculate the fib(5).

we will use the recursive function ie,  Fib(n),fib(n)=fib(n-1)+fib(n-2)

Let’s take the recursive graph of “fib(5)”

Overlapping subproblems

This problem is defined as the problem in computing the same result multiple times ie, finding the solution of any subproblem involves solving the same subproblem many times.

For eg. in this computation of “fib(5)”, we need to find the value of “fib(2)” three times.

So we have a solution for this problem ie, MEMOIZATION.

Memoization: A memoized program for the Fibonacci series is slightly changed or we can say a little bit modified. In this program we will make a lookup array in which all values are nil ie, initially, it is nil. lookup function will only compute its analysis when the lookup is nil for value, otherwise, it will use the stored value in it. So when the overlapping comes, this lookup will give the solution to this overlapping subproblem.

Let’s understand this from Python code:

Python code implementation:

# Function to calculate the Fibonacci series
def Fib(n, lookup):
    # Base case
    if n == 0 or n == 1:
        lookup[n] = n

    # If the value is not calculated previously, then calculate it
    if lookup[n] is None:
        lookup[n] = Fib(n - 1, lookup) + Fib(n - 2, lookup)

    # The value will be returned
    return lookup[n]

# Drive code for testing the function
def main():
    n = 9
    # Declaration of the lookup array
    # Handles up to 101
    lookup = [None] * 101
    print("Fibonacci number is:", Fib(n, lookup))

if __name__ == "__main__":
    main()

Output:

Fibonacci number is 34

Below is given what we did in the above code:

• Here theFib function calculates the nth Fibonacci number.
• It uses memoization to store and reuse previously calculated values.
• The base cases for n=0 and n=1 are defined in our code.
• Recursively calculates Fibonacci numbers, checking the memoization table in order to avoid redundant calculations.
• The main function initializes the lookup table and computes the 9th Fibonacci number (you can change n as needed).
• At the end, our Python code prints the result when run as the main program.