Do you think IIT Guwahati certified course can help you in your career?
Introduction
Suppose you are preparing for a coding interview at a big company or want to increase your code optimization skills by solving problems based on real-life situations. In that case, you must focus on dynamic programming.
In this, we will discuss a famous dynamic programming problem that can help you understand the concept of dynamic programming so you can apply this concept efficiently whenever you want to.
Dynamic Programming
Suppose you are solving a problem where you can see a pattern of sub-problems repeating throughout the main statement. Think of more than one way to deal with these sub-problems. You might use a recursive approach to deal with these sub-problems, which is a good approach, but what if your following result is dependent on your previous result?
In this scenario, recursion is not optimal because you have to store and compute the data at every point you have already calculated. This is where the concept of dynamic programming comes into play.
So, we use Dynamic Programming, an optimization of simple recursion, to solve such problems. The basic idea is to store the results of sub-problems to avoid recalculation and reduce the time complexity of the issues.
The problem we will discuss is known as ‘building bridges’. building bridges is based on the problem LIS(Longest Increasing Subsequence), so if you have a good understanding of the LIS, you can easily understand the building bridges problem.
Problem Statement
Let's discuss the problem statement of building bridges with an example first.
Assume you are a constructor who got a contract to build bridges across a river. You have to build multiple bridges because you want to shorten the path of one village to another. You have calculated multiple coordinates from North to South across the river where building the bridges is possible.
Your task is to build the maximum number of bridges across the river that do not overlap with any of the bridges on the river. Let's see a pictorial representation of the problem.
The number of bridges we have built in the image is 3.
The coordinates of bridges are (1,1) (2,2) (3,3) accordingly.
As you can see, these bridges are not overlapping with each other.
The ‘building bridges’ problem states that there are 2 * N cities along the bank of a river, with N cities lying to the North of the river and N on the Southern bank of the river. The coordinates of cities on the Northern and Southern banks are given as the input.
Your task is to connect the cities of the Northern bank with that of the Southern bank with the help of bridges, but the bridges must be distinct. It would help if you connected the maximum bridges that do not overlap during construction.
Example
Input
Total number of bridges to build: 4
North and South Coordinates of river banks will be (5,6) (3,4) (1,3) (2,5).
These coordinates can be in any order on each side of the river. The user input is the pair of coordinates that can connect, like in the picture below.
Output
The maximum number of bridges we can connect is 3.
In the given sequence of north and south coordinates, we cannot connect 2 and 5 because they will overlap with other bridges, decreasing the number of bridges we can connect.
Now that you have understood the problem statement, let's discuss how to tackle the building bridges problem.
Approach
The solution to this problem is simple if you know the LIS concept. LIS plays an important factor in solving the building bridges problem. Try to understand the LIS to understand the explanation for building bridges.
We know the coordinates will be given to us in the north and south directions. We also know that these coordinates will be present in any order across the river on each side. You must understand that if you do not want the bridges to overlap, the coordinates must be in increasing order on each side of the river.
This means we need to sort each side of the river in increasing order to avoid overlapping. But, we cannot individually sort the coordinates because they will be given to use in the form pair.
We can sort one side of the river concerning another and then apply the LIS on the non-sorted side. For example, if you have sorted the north coordinates, you can calculate the LIS on the south coordinates.
As we have mentioned avoiding overlapping the order must be increased. We have sorted the one coordinate, and then if we look for the LIS in the non-sorted coordinates, we will only find the pairs of coordinates which cannot be overlapped.
The number of elements present in the LIS will be the maximum number of bridges we can from across the river,
Algorithm
Store the coordinates of the cities in a pair.
Sort the pairs according to the south coordinates in increasing order.
The north and south coordinates should increase or decrease to avoid overlapping.
Since we sorted the coordinates of the cities on the Southern bank, we need to find the coordinates of cities on the Northern bank that are increasing or decreasing to find the maximum number of non-overlapping bridges.
Now, we will find the Longest Increasing Subsequence of the coordinates of the North to find the maximum number of bridges.
In this problem, a value greater than or equal to the previous value can also be considered part of the increasing subsequence.
The maximum in LIS will be returned.
DRY Run
Input:
Sorting the coordinates with respect to north coordinates.
Calculating LIS on the South Coordinates.
The LIS until value 3 will be 1, so our max will be 1, and we will update the LIS array as LIS[1] = 1.
Next, we will calculate the LIS until value 5, which will be 2. Compare the current LIS and max value. Here current LIS is greater than the max because the current LIS is 2 and the max is 1. Update the max = 2 and LIS array LIS[2] = 2.
Now LIS until value 4 will be 2. The max and current LIS are the same, so we will not update it. LIS array will be LIS[3] = 2.
Now LIS until value 6 will be 3. The current LIS is greater than the max. Update the max = 3 and the LIS array as LIS[4] = 3.
The maximum number of bridges we can build will be 3.
Implementation
#include<bits/stdc++.h>
using namespace std;
int maxBridges(vector<pair<int, int>> &values, int n) {
// Initializing a memo vector to store the current max
vector<int>memo(n);
memo[0] = 1;
// Sorting the values vector pair
sort(values.begin(), values.end());
int omax = 0;
// Calculating the max bridges with LIS
for (int i = 1; i < n; i++) {
int max = 0;
for (int j = 0; j < i; j++) {
if (values[i].second >= values[j].second){
if(memo[j] > max) {
max = memo[j];
}
}
memo[i] = max + 1;
if (memo[i] > omax) {
omax = memo[i];
}
}
}
// Returning the max
return omax;
}
int main() {
vector<pair<int, int>> values;
values.push_back({5, 6});
values.push_back({3, 4});
values.push_back({1, 3});
values.push_back({2, 5});
cout << "The maximum number of bridges is " << maxBridges(values, values.size());
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity for this approach will be O(N*N) because we have to apply the nested for loop to calculate the LIS on the second coordinate.
An extra array of size N is taken to store the value of LIS at every index; thus, the space complexity is given by O(N).
Optimized Approach
We can achieve a better time complexity in the building bridges problem. Instead of using the nested for loop to calculate the LIS, we can use the lower_bound() function. With the help of lower_bound, we can traverse the non-sorted coordinates and calculate the LIS in O(logN) time complexity.
Algorithm
Store the coordinates of the cities in a pair.
Sort the pairs according to the North coordinates in increasing order.
Since the Northside is increasing, we will find the Longest Increasing Subsequence for the Southern coordinates.
The length of this longest increasing subsequence will be the answer to our problem.
In this method, we create a DP array and initialize it with an enormous value, say INT_MAX.
We traverse the Southern Coordinates one by one, find the index of the next greater element present in the DP array, and update it with the value of this Southern coordinate. The length of the LIS, which ends at that index, will be increased by 1.
Note that the smallest element will have the highest chance of contributing to the LIS.
Subsequently, we will keep track of the maximum LIS, and this maximum will be our answer.
DRY Run
We will create a Dp vector of size ‘n’, and all the values will be INT_MAX in the vector.
Let us store the LIS at every index in the variable ANS.
i = 0
value = 3
Next greater element in the DP array = INT_MAX
Index of next greater element = 0
DP[4] becomes:
ANS = max(0, 0+1)
= max(0,1)
= 1
i = 1
value = 5
Next greater element in the DP array = INT_MAX
Index of next greater element = 1
DP[4] becomes:
ANS = max(1, 1+1)
= max(1,2)
= 2
i = 2
value = 4
Next greater element in the DP array = 5
Index of next greater element = 1
DP[4] becomes:
ANS = max(2, 1+1)
= max(2,2)
= 2
i = 3
value = 6
Next greater element in the DP array = INT_MAX
Index of next greater element = 2
DP[4] becomes:
ANS = max(2, 2+1)
= max(2,3)
= 3
Thus, the length of the LIS is 3. Hence the maximum number of bridges will be 3.
Implementation
#include<bits/stdc++.h>
using namespace std;
// Finding the maximum number of bridges.
int maxBridges(vector<pair<int, int>> & values, int n) {
// Creating a DP vector to store the number of non-overlapping bridges.
vector<int> dpvector(n,INT_MAX);
int maxbridges = 0;
// Sorting the values
sort(values.begin(), values.end());
// Calculating the maximum number of bridges
for (auto tr:values) {
int index = lower_bound(dpvector.begin(), dpvector.end(), tr.second) - dpvector.begin();
dpvector[index] = tr.second;
maxbridges = max(maxbridges, index + 1);
}
return maxbridges;
}
int main() {
vector<pair<int, int>> values;
values.push_back({5, 6});
values.push_back({3, 4});
values.push_back({1, 3});
values.push_back({2, 5});
cout << "The maximum number of bridges is "<<maxBridges(values, values.size());
return 0;
}
You can also try this code with Online C++ Compiler
In this approach, we traverse a single loop from index 0 to N-1, and in every iteration, we use a lower bound, which costs O(log N) time. Thus, the time complexity is given by O(N * log N).
Space Complexity
Since it uses an extra DP array for storing the number of non-overlapping bridges, the space complexity is given by O(N).
Dynamic programming is one of the programming techniques we use to break down the main into sub-problems and calculate the result based on the output of subproblems.
What is LIS?
LIS stands for longest increasing subsequence, a problem based on dynamic programming.
Do we need to know LIS to solve the building bridges problem?
Yes, the building bridges problem is a variation of the LIS problem. LIS stands for Longest Increasing subsequence, which we use to calculate an increasing subsequence longest in an input.
What inbuilt method can we use to sort the vector?
The sort() function can sort the vector or array.
What is the lower_bound() function?
The function returns the pointer to the first number in a vector greater than the number given to the lower_bound().
Conclusion
In this blog, we discussed problems based on LIS, known as building bridges. We have used the dynamic programming approach to solve the problem and implemented the solution. We have also discussed the optimal approach to tackle the problem.
To learn more programming problems check out the following links.
84+ registered