Optimal Substructure and Overlapping Subproblems

  • What is an optimal substructure?
  • Is overlapping subproblems related to optimal substructure?

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. Following are the two main properties of a problem that suggests that the given problem can be solved using Dynamic programming:

  1. Overlapping Subproblems
  2. Optimal Substructure

Overlapping Subproblems

Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again. For example, Binary Search doesn’t have common subproblems. If we take an example of following recursive program for Fibonacci Numbers, there are many subproblems which are solved again and again.

1
2
3
4
5
6
7

/* simple recursive program for Fibonacci numbers */
int fib(int n) 
{ 
   if (n <= 1) 
      return n; 
   return fib(n-1) + fib(n-2); 
}

Recursion tree for execution of fib(5)

	 				     fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

We can see that the function fib(3) is being called 2 times. If we would have stored the value of fib(3), then instead of computing it again, we could have reused the old stored value.

Optimal Substructure

A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems. For example, the Shortest Path problem has following optimal substructure property:

If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v. The standard All Pair Shortest Path algorithms like Floyd-Warshall and Bellman-Ford are typical examples of Dynamic Programming.

On the other hand, the Longest Path problem doesn’t have the Optimal Substructure property. Here by Longest Path we mean longest simple path (path without cycle) between two nodes. Consider the following unweighted graph given in the CLRS book. There are two longest paths from q to t: q→r→t and q→s→t. Unlike shortest paths, these longest paths do not have the optimal substructure property. For example, the longest path q→r→t is not a combination of longest path from q to r and longest path from r to t, because the longest path from q to r is q→s→t→r and the longest path from r to t is r→q→s→t.

Conclusion

Optimal substructure is not related to overlapping subproblems. We can use them to suggest that the given problem can be solved using Dynamic Programming

Claude Explanation

Optimal Substructure

Description

Optimal substructure is the property that an optimal solution to a problem contains optimal solutions to its subproblems.

This means breaking down the problem into subproblems which can be solved optimally. The solutions to the subproblems can be used to construct an optimal solution for the overall problem.

For example, shortest paths in a graph have optimal substructure - the shortest path between two vertices contains shortest paths between intermediate vertices.

Optimal substructure is key for dynamic programming. It allows solutions to be reused leading to improved efficiency.

Solution

Here is code to find the maximum sum subarray using optimal substructure:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int maxSubarraySum(int[] arr) {
  
  int max = arr[0];
  int currMax = arr[0];

  for (int i = 1; i < arr.length; i++) {
    currMax = Math.max(arr[i], currMax + arr[i]);
    max = Math.max(max, currMax);
  }

  return max;
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int maxSubarraySum(vector<int> arr) {

  int max = arr[0];
  int currMax = arr[0];

  for (int i = 1; i < arr.size(); i++) {
    currMax = max(arr[i], currMax + arr[i]);
    max = max(max, currMax);
  }

  return max;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def max_subarray_sum(arr):
  
  max_sum = arr[0]
  curr_max = arr[0]

  for num in arr[1:]:
    curr_max = max(num, curr_max + num)
    max_sum = max(max_sum, curr_max)

  return max_sum

This uses optimal sums of subarrays to calculate overall optimal sum. Optimal substructure allows efficient solutions.

Description: Optimal Substructure

Optimal substructure refers to the property of a problem that an optimal solution can be constructed from optimal solutions of its subproblems. This is a core property that makes a problem amenable to dynamic programming solutions. For example, in the shortest path problem in graph theory, if there’s an optimal path from point A to C via B, then the paths from A to B and B to C must also be optimal.

Solution:

We will implement code to solve the Longest Increasing Subsequence (LIS) problem, which exhibits the optimal substructure property. Given an array, the task is to find the length of the longest subsequence with elements in increasing order.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class OptimalSubstructure {
    public static int longestIncreasingSubsequence(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        System.out.println(longestIncreasingSubsequence(nums));  // Output: 6
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> nums = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << longestIncreasingSubsequence(nums) << endl;  // Output: 6
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def longestIncreasingSubsequence(nums):
    n = len(nums)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

nums = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(longestIncreasingSubsequence(nums))  # Output: 6

Key Takeaways:

  • Optimal substructure is a key property for dynamic programming solutions.
  • We used dynamic programming to solve the Longest Increasing Subsequence problem, which has an optimal substructure.
  • The core algorithm remains consistent across Java, C++, and Python, with syntax being the primary difference.