What is the Optimal Substructure?
Optimal Substructure is a powerful principle that says the optimal solution of a bigger problem can be created from the optimal solutions of its smaller subproblems. It allows us to break a difficult problem into small manageable parts, and combine the results of these small problems to get the best solution to the overall problem.
Longest Increasing Subsequence (LIS)
To illustrate the importance of Optimal Substructure, let's look at the problem of finding the Longest Increasing Subsequence.
What is the Longest Increasing Subsequence (LIS)?
Longest Increasing Subsequence (LIS) represents the length of the longest subsequence in an array where the elements are arranged in increasing order. A subsequence is not necessarily contiguous but maintains the order of appearance in the original array.
Traditional approach
Without taking advantage of the optimal substructure, one can use the brute-force approach – checking all possible outcomes. However, as the array increases, this method becomes increasingly ineffective.
Dynamic Programming with Optimal Substructure
Now, let's apply the Optimal Substructure concept to solve the LIS problem efficiently:
def lis(arr):
n = len(arr)
lis_lengths = [1] * n
for i in range(1, n):
for j in range(0, i):
if arr[i] > arr[j] and lis_lengths[i] < lis_lengths[j] + 1:
lis_lengths[i] = lis_lengths[j] + 1
return max(lis_lengths)
In this approach:
- We maintain a list (
lis_lengths) to store the length of the LIS ending at each element in the array. - We iterate through the array, comparing each element with the previous ones.
- If the current element is greater than the previous one and extending the LIS ending at the current element is beneficial, we update the LIS length.
Why does Optimal Substructure matter?
The optimal subproblem is the guiding principle that allows us to efficiently solve smaller subproblems, resulting in the best overall solution. It is similar to creating a blueprint for constructing the optimal solution to a complex problem.
Where to find the Optimal Substructure?
Optimal substructure often takes center stage in problems where choosing the best option at each step contributes to the optimal solution. Whether this involves finding the longest, shortest, or most efficient arrangement, the optimal substructure guides decision-making at each step.
Let's sum it up
Optimal Substructure in Dynamic Programming is the hidden power that transforms seemingly insurmountable problems into manageable tasks. By efficiently solving smaller sub-problems, we pave the way to building the optimal solution. In LIS terms, this empowers us to find the Longest Increasing Subsequence in an array.
