2022-03-05：不相交的线。

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
  }
}