2022-03-05：不相交的线。
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
输入：nums1 = [1,4,2], nums2 = [1,2,4]。
输出：2。
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
力扣1035。
答案2022-03-05：
求最长公共子序列。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
if true {
A := []int{1, 4, 2}
B := []int{1, 2, 4}
ret := maxUncrossedLines1(A, B)
fmt.Println(ret)
}
if true {
A := []int{1, 4, 2}
B := []int{1, 2, 4}
ret := maxUncrossedLines2(A, B)
fmt.Println(ret)
}
}
// 针对这个题的题意，做的动态规划
func maxUncrossedLines1(A, B []int) int {
if len(A) == 0 || len(B) == 0 {
return 0
}
N := len(A)
M := len(B)
// dp[i][j]代表: A[0...i]对应B[0...j]最多能划几条线
dp := make([][]int, N)
for i := 0; i < N; i {
dp[i] = make([]int, M)
}
if A[0] == B[0] {
dp[0][0] = 1
}
for j := 1; j < M; j {
dp[0][j] = twoSelectOne(A[0] == B[j], 1, dp[0][j-1])
}
for i := 1; i < N; i {
dp[i][0] = twoSelectOne(A[i] == B[0], 1, dp[i-1][0])
}
// 某个值(key)，上次在A中出现的位置(value)
AvalueLastIndex := make(map[int]int)
AvalueLastIndex[A[0]] = 0
// 某个值(key)，上次在B中出现的位置(value)
BvalueLastIndex := make(map[int]int)
for i := 1; i < N; i {
AvalueLastIndex[A[i]] = i
BvalueLastIndex[B[0]] = 0
for j := 1; j < M; j {
BvalueLastIndex[B[j]] = j
// 可能性1，就是不让A[i]去划线
p1 := dp[i-1][j]
// 可能性2，就是不让B[j]去划线
p2 := dp[i][j-1]
// 可能性3，就是要让A[i]去划线，那么如果A[i]==5，它跟谁划线？
// 贪心的点：一定是在B[0...j]中，尽量靠右侧的5
p3 := 0
if _, ok := BvalueLastIndex[A[i]]; ok {
last := BvalueLastIndex[A[i]]
p3 = twoSelectOne(last > 0, dp[i-1][last-1], 0) 1
}
// 可能性4，就是要让B[j]去划线，那么如果B[j]==7，它跟谁划线？
// 贪心的点：一定是在A[0...i]中，尽量靠右侧的7
p4 := 0
if _, ok := AvalueLastIndex[B[j]]; ok {
last := AvalueLastIndex[B[j]]
p4 = twoSelectOne(last > 0, dp[last-1][j-1], 0) 1
}
dp[i][j] = getMax(getMax(p1, p2), getMax(p3, p4))
}
BvalueLastIndex = make(map[int]int)
}
return dp[N-1][M-1]
}
// 但是其实这个题，不就是求两个数组的最长公共子序列吗？
func maxUncrossedLines2(A, B []int) int {
if len(A) == 0 || len(B) == 0 {
return 0
}
N := len(A)
M := len(B)
dp := make([][]int, N)
for i := 0; i < N; i {
dp[i] = make([]int, M)
}
dp[0][0] = twoSelectOne(A[0] == B[0], 1, 0)
for j := 1; j < M; j {
dp[0][j] = twoSelectOne(A[0] == B[j], 1, dp[0][j-1])
}
for i := 1; i < N; i {
dp[i][0] = twoSelectOne(A[i] == B[0], 1, dp[i-1][0])
}
for i := 1; i < N; i {
for j := 1; j < M; j {
p1 := dp[i-1][j]
p2 := dp[i][j-1]
p3 := twoSelectOne(A[i] == B[j], 1 dp[i-1][j-1], 0)
dp[i][j] = getMax(p1, getMax(p2, p3))
}
}
return dp[N-1][M-1]
}
func twoSelectOne(c bool, a, b int) int {
if c {
return a
} else {
return b
}
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下：
***
[左神java代码](https://gitee.com/moonfdd/coding-for-great-offer/blob/main/src/class51/Problem_1035_UncrossedLines.java)
