持续创造，加速成长！这是我参加「掘金日新方案 10 月更文应战」的第8天，点击查看活动概况

最近一直在力扣刷题，也逐步对各类题型有了自己的理解，所谓见招拆招，将自己的粗浅经历共享一下，协助更多在编程路上的朋友们。

今日遇到了一个特别有意思的题，很值得共享出来，标题如下：

不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，能够制作一些连接两个数字 nums1[i]和 nums2[j]的直线，这些直线需要一起满足满足：

nums1[i] == nums2[j] 且制作的直线不与任何其他连线（非水平线）相交。 请注意，连线即使在端点也不能相交：每个数字只能归于一条连线。

以这种办法制作线条，并回来能够制作的最大连线数。

示例如下

开始探索

第一眼看到这个标题是懵的，底子想不出来怎么做，感觉上会接近DFS，但是还要保存前置状况，而且感觉上DFS就会超时。

实在是无从写起，愣了良久还是看了题解，恍然大悟，这题竟然是动态规划？？？

正确思路

这是一道二维的动态规划标题，因为是求连线数，所以dp[i][j]界说为从最初算起，nums1的 i 方位和nums2的 j 方位上的可连线数。

初始值很简单，假如是空数组的话，无法与任何数组有连线，所以i为0或者j为0时，连线数均为0

• 假如nums[i] == nums[j]，则dp[i][j] = dp[i – 1][j – 1] + 1

• 假如nums[i] != nums[j], 则dp[i][j] 为上一个状况中连线最多的，即Math.max(dp[i – 1][j], dp[i][j – 1];

终究结果为dp[nums1.length][nums2.length]

这道题也是在求两个数组的最长公共子序列，只不过是换了一种描述，说成线的话，很简单让人想不到，每次遇到动态规划都会被教育…