Contents

# Problem

We write the integers of `A` and `B` (in the order they are given) on two separate horizontal lines.

Now, we may draw connecting lines: a straight line connecting two numbers `A[i]` and `B[j]` such that:

`A[i] == B[j]`; The line we draw does not intersect any other connecting (non-horizontal) line. Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.

Return the maximum number of connecting lines we can draw in this way.

## example 1

 ``````1 2 3 4 `````` ``````Input: A = [1,4,2], B = [1,2,4] Output: 2 Explanation: We can draw 2 uncrossed lines as in the diagram. We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2. ``````

## example 2

 ``````1 2 `````` ``````Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2] Output: 3 ``````

## example 3

 ``````1 2 `````` ``````Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1] Output: 2 ``````

## Constraints

• 1 <= `len(A)` <= 500
• 1 <= `len(B)` <= 500
• 1 <= `A[i], B[i]` <= 2000

# Solution

## Dynamic programming

Lets describe our dp function.

`i` – iterator over `A`

`j` – iterator over `B`

• If `i<0` or `j<0` – return 0
• Compare `A[i]` and `B[j]` :
• if equal – run dp with `i-1`, `j-1`; return with + 1
• if not equeal – return max of dp(`i-1`, `j`) and dp(`i`, `j-1`)
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 `````` ``````func maxUncrossedLines(A []int, B []int) int { m := make(map[int]map[int]int, len(A)) for idx:=0;idxb { return a } return b } ``````