Building Bridges
Explore how to connect cities with the maximum number of non-overlapping bridges using dynamic programming. Understand naive recursive and optimized top-down and bottom-up DP solutions that improve time and space efficiency for this sequence optimization problem.
Statement
Two cities are to be connected via north and south, consisting of positive integers.
Note:
northrepresents the coordinates of bridges on the northern bank of the river, whereassouthrepresents the coordinates of bridges on the southern bank.
What is the maximum number of bridges if the
For example, we have two arrays:
One possibility is that we can connect