What are overlapping subproblems?

What is a subproblem?

A subproblem is a smaller problem that is a part of a larger problem. Subproblems are often used in problem-solving techniques, such as divide-and-conquer and dynamic programming, where a complex problem is broken down into smaller, more manageable subproblems that can be solved independently and then can be combined to solve the larger problem.

This approach is not only efficient but can also be used to find optimal solutions.

What are overlapping subproblems?

Subproblems are like smaller components of a puzzle. Solving each of these components can help to solve the entire puzzle. Once all the puzzle pieces are in the right place, the whole puzzle is solved.

Sometimes, the smaller components of the puzzle might be exactly the same. In the case of the same puzzle, we need to solve that puzzle only once, and we can reuse the solution of the same puzzle. Such subproblems are called overlapping subproblems.

Therefore, subproblems are different parts of a task that we have to do one time each while overlapping subproblems are the same parts of a task that we have to do multiple times.

Below is an example of overlapping subproblems solving the Fibonacci series. The nodes in the same color solve the same subproblem, meaning there are overlapping subproblems.

How can we use overlapping subproblems to our advantage?

Overlapping subproblems can be used to our advantage by using dynamic programming. Dynamic programming is a method for solving problems by breaking them down into smaller subproblems, then solving each subproblem only once, and storing the solution to each subproblem. This allows for faster problem-solving by avoiding the computation of the same subproblems multiple times.

This is particularly useful when dealing with overlapping subproblems because it allows for the efficient use of previously computed solutions to solve new subproblems. Let’s take a look at a simple example highlighting the massive difference dynamic programming makes in the time complexity of our solution.

Example: Recursive approach without storing the results of overlapping subproblems

The following code solves the problem successfully but the overall time complexity will be $O(2^n)$ . As the input size increases, the solution’s efficiency will deteriorate because of the exponential time complexity.

You can uncomment the last comment in each code tab below and check how this recursive solution causes a time-out when the input is a large number.

def get_fibonacci(n):
    # Base case for n = 0 and n = 1
    if n < 2:
        return n
    # Otherwise, calculate the Fibonacci number using the recurrence relation
    return get_fibonacci(n - 1) + get_fibonacci(n - 2)
# Driver code
def main():
    inputs = [0, 5, 7, 10, 14]
    # You can uncomment the line below and check how this recursive solution causes a time-out 
    # inputs.append(60)
    for i in range(len(inputs)):
        print(str(i + 1) + ". " + str(inputs[i]) + "th Fibonacci number is:", get_fibonacci(inputs[i]))
        print("-" * 72, "\n", sep="")
if __name__ == "__main__":
    main()

Fibonacci Numbers using recursion

def get_fibonacci_memo(n, lookup_table):
    # Base case
    if n < 2:
        return n
    # Check if already present
    if lookup_table[n] != -1:
        return lookup_table[n]
    # Adding entry to table if not present
    lookup_table[n] = get_fibonacci_memo(n - 1, lookup_table) + \
                      get_fibonacci_memo(n - 2, lookup_table)
    return lookup_table[n]
def get_fibonacci(n):
    # Initializing the lookup table of size num + 1
    lookup_table = [-1] * (n + 1)
    return get_fibonacci_memo(n, lookup_table)
# Driver code
def main():
    inputs = [0, 5, 7, 10, 14]
    # Let's uncomment this and check the effect of dynamic programming using memoization
    # inputs.append(60)
    for i in range(len(inputs)):
        print(str(i + 1) + ". " + str(inputs[i]) + "th Fibonacci number is:", get_fibonacci(inputs[i]))
        print("-" * 72, "\n", sep="")
if __name__ == "__main__":
    main()

Fibonacci Numbers using dynamic programming

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

What are overlapping subproblems?

What is a subproblem?