题目描述
- “连连看”
- 上下两个数组，相同的数可以连线，问在不交叉的情况下最多可以连多少条线
示例
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：
1 4 2
| \
1 2 4
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2
题解
- 思路
- 暴力就是枚举两个末尾，然后穷举
- 这种暴力要优化就是 DP
func maxUncrossedLines(nums1 []int, nums2 []int) int {n, m := len(nums1), len(nums2)f := make([][]int, n + 1)for i := 0; i < n + 1; i ++ { f[i] = make([]int, m + 1) }for i := 1; i <= n; i ++ {for j := 1; j <= m; j ++ {f[i][j] = max(f[i - 1][j], f[i][j - 1])if nums1[i - 1] == nums2[j - 1] {f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)}}}return f[n][m]
}
