1035. 不相交的线 #
- 标签:数组、动态规划
- 难度:中等
题目大意 #
有两条独立平行的水平线,按照给定的顺序写下 nums1
和 nums2
的整数。
现在,我们可以绘制一些直线,只要满足以下要求:
nums1[i] == nums2[j]
。- 绘制的直线不与其他任何直线相交。
例如:
现在要求:计算出能绘制的最大直线数目。
解题思路 #
动态规划求解。
定义状态 dp[i][j]
表示:nums1
中前 i
个数与 nums2
中前 j
个数的最大连接数,则:
状态转移方程为:
- 如果
nums1[i] == nums[j]
,则nums1[i]
与nums2[j]
可连线,此时dp[i][j] = dp[i - 1][j - 1] + 1
。 - 如果
nums1[i] != nums[j]
,则nums1[i]
与nums2[j]
不可连线,此时最大连线数取决于dp[i - 1][j]
和dp[i][j - 1]
的较大值,即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
。
最后输出 dp[size1][size2]
即可。
代码 #
|
|