Leetcode - Uncrossed Lines
https://leetcode.com/problems/uncrossed-lines/
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:
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.
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 | func maxUncrossedLines(A []int, B []int) int { m := len(A) n := len(B) dp := make([][]int, m+1) for i := 0; i < len(dp); i++ { dp[i] = make([]int, n+1) } for i := m-1; i >= 0; i-- { for j := n-1; j >= 0; j-- { if A[i] == B[j] { dp[i][j] = dp[i+1][j+1] + 1 } else { dp[i][j] = max(dp[i][j+1], dp[i+1][j]) } } } return dp[0][0]}func max(a, b int) int { if a > b { return a } return b} |
评论 (0)
