2022-03-05：不相交的线。 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直

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代码

2022-03-05：不相交的线。 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直的相关教程结束。