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.
如果 num