1️⃣题目描述
在两条独立的水平线上按给定的顺序写下 nums1
和 nums2
中的整数。
现在,可以绘制一些连接两个数字 nums1[i]
和 nums2[j]
的直线,这些直线需要同时满足以下两点:
nums1[i] == nums2[j]
- 且绘制的直线不与任何其他连线(非水平线)相交。
示例 1:
示例2:
示例3:
注意:
1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000
2️⃣题目解析
关于本题的思路,可以说基本上和leetcode1143. 最长公共子序列完全一样,简直就是一个题。可以参照我们上篇博客:leetcode1143. 最长公共子序列(点击直接跳转至该博客)
状态转移方程(这里我多开了一块空间,所以大家注意以下下标映射关系
):
if(nums1[i-1] == nums2[j-1])
则dp[i][j] = dp[i - 1][j - 1] + 1
- 否则,
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
返回值:
dp[m][n]
3️⃣解题代码
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(),n = nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i = 1;i <= m;i++)
{
for(int j =1;j <= n;j++)
{
if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
};