Building Bridges

Explore how to find the maximum number of non-overlapping bridges between two cities using dynamic programming. Understand the naive recursive solution and then optimize it with top-down and bottom-up approaches based on the longest common substring pattern. Gain skills in solving recursive problems efficiently by applying memoization and tabulation methods to reduce time complexity and improve performance.

We'll cover the following...

Statement
Examples
Try it yourself
Solution

Statement

Two cities are to be connected via $n$ number of bridges over a river. The north bank of the river belongs to city $A$ , while the south bank to city $B$ . Considering this scenario, suppose we have two arrays, north and south, consisting of positive integers.

Note: north represents the coordinates of bridges on the northern bank of the river, whereas south represents the coordinates of bridges on the southern bank.

What is the maximum number of bridges if the ${i^{th}}$ point of city $A$ is connected to the ${i^{th}}$ point of city $B$ , keeping in view that no two bridges overlap each other? While building bridges, you can only connect the $A[i^{th}]$ bridge on the north bank with the $B[i^{th}]$ point on the south bank.

For example, we have two arrays:

$north = [6, 4, 2, 1]$
$south = [2, 3, 6, 5]$

One possibility is that we can connect $1$ with ...

1.Getting Started

2.0/1 Knapsack

3.Unbounded Knapsack

4.Recursive Numbers

5.Longest Common Substring

6.Palindromic Subsequence

7.Conclusion

Building Bridges

Statement