There is a river which flows horizontally through a country. There are N cities on the north side of the river and N cities on the south side of the river. The X coordinates of the N cities on the north side of the river are n₁, n₂, , n_N, and the X coordinates of the N cities on the south side of the river are s₁, s₂, , s_N. Assume that we can only build bridges between cities with the same number; that is, we can only build bridges between cities with coordinates n_i and s_i, where 1 <= i <= N. In this problem, we ask you to determine the maximum number of bridges we can build without any bridges crossing each other. Note that n₁ through n_N and s₁ through s_N are both not sorted.

(1) Describe your definition of a subproblem. Use that definition, prove that this problem exhibits optimal substructure. (2) Describe a dynamic-programming algorithm to solve the problem. (3) What is the time complexity of your algorithm?

** Note: There is already a solution to this question on here but the person who answered copied word for word the solution given in the source material. I am hoping that someone can explain it differently, at least in their own words, so that I can better understand. Thank you.