Algorithm Dynamic Programming Optimal Substructure And Overlapping Subproblems Complete Guide

Complete Examples, Step-by-Step for Beginners: Algorithm Dynamic Programming - Optimal Substructure and Overlapping Subproblems

1. Understanding Optimal Substructure

Optimal Substructure means that the optimal solution to a problem can be constructed efficiently from optimal solutions to its subproblems. This means that the solution to the entire problem depends on the solution to its subproblems in an optimal way.

2. Understanding Overlapping Subproblems

Overlapping Subproblems occur when the problem can be broken down into subproblems that are computed multiple times. Instead of recomputing the result of these subproblems every time, the results are stored and reused. This way, problems with many overlapping subproblems like Fibonacci can be solved efficiently.

Example 1: Fibonacci Sequence

Let's solve the Fibonacci sequence problem using dynamic programming to understand these concepts better.

Problem Statement: Find the n-th Fibonacci number.

Mathematical Formulation:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

Recursive Solution:

def fibonacci_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# Test the recursive function
print(fibonacci_recursive(5))  # Output: 5

Issue: The recursive solution has exponential time complexity O(2^n) because it recomputes the same subproblem multiple times.

Dynamic Programming Solution Using Memoization:

Memoization is a top-down approach where we store the results of subproblems in a data structure (usually an array or a dictionary) and use these results to solve larger subproblems.

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
        return memo[n]

# Test the memoization function
print(fibonacci_memoization(5))  # Output: 5

Explanation:

• Here, memo dictionary stores the Fibonacci numbers that have already been computed.
• When the function is called with a number n, it first checks if F(n) is already in the memo dictionary. If it is, the function returns memo[n] immediately without making a recursive call.
• This significantly reduces the time complexity to O(n).

Dynamic Programming Solution Using Tabulation:

Tabulation is a bottom-up approach where we fill up a table in a specific order and use previously computed values to compute new values.

def fibonacci_tabulation(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    table = [0] * (n+1)
    table[1] = 1
    for i in range(2, n+1):
        table[i] = table[i-1] + table[i-2]
    return table[n]

# Test the tabulation function
print(fibonacci_tabulation(5))  # Output: 5

Explanation:

• We initialize a list table where table[i] will store the i-th Fibonacci number.
• We fill the list in a bottom-up manner, starting from table[0] and table[1].
• For each i from 2 to n, we compute table[i] using the relation table[i] = table[i-1] + table[i-2].
• This approach also has a time complexity of O(n) and a space complexity of O(n).

Space Optimization

We can optimize the space complexity to O(1) by only storing the last two Fibonacci numbers instead of an entire list.

def fibonacci_optimized(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a + b
    return b

# Test the optimized function
print(fibonacci_optimized(5))  # Output: 5

Explanation:

• We only need to store the last two Fibonacci numbers to compute the next one.
• We use two variables a and b to represent F(n-1) and F(n-2), respectively.
• This reduces the space complexity to O(1) while maintaining a time complexity of O(n).

Example 2: Longest Common Subsequence (LCS)

Problem Statement: Given two sequences X and Y, find the length of the longest subsequence present in both of them. A subsequence is a sequence derived from another sequence where some elements may be deleted without changing the order of the remaining elements.

Dynamic Programming Solution Using Tabulation:

def longest_common_subsequence(X, Y):
    m = len(X)
    n = len(Y)
    # Create a 2D array to store lengths of longest common subsequence.
    L = [[0] * (n + 1) for _ in range(m + 1)]

    # Build the L table in bottom up fashion
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])

    # L[m][n] contains the length of LCS for X[0..m-1],  Y[0..n-1]
    return L[m][n]

# Test the LCS function
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS is", longest_common_subsequence(X, Y))  # Output: 4 (The LCS is "GTAB")

Explanation:

• We create a 2D list L where L[i][j] represents the length of the longest common subsequence of X[0..i-1] and Y[0..j-1].
• We fill this table in a bottom-up manner.
  • If the current characters of X and Y are the same, then L[i][j] = L[i-1][j-1] + 1.
  • If they are different, then L[i][j] = max(L[i-1][j], L[i][j-1]).
• The length of the longest common subsequence is found in L[m][n].

Conclusion

In this tutorial, we learned how to apply dynamic programming to solve problems with optimal substructure and overlapping subproblems. We explored the Fibonacci sequence problem using both memoization and tabulation, and then moved on to the Longest Common Subsequence problem. By understanding these examples, you should be able to identify problems that can be solved using dynamic programming.

Remember the key steps:

1. Identify if the problem has optimal substructure and overlapping subproblems.
2. Decide whether to use a top-down (memoization) or bottom-up (tabulation) approach.
3. Implement the solution efficiently, optimizing for time and space as needed.