-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathUncrossed Line
More file actions
30 lines (30 loc) · 1.02 KB
/
Uncrossed Line
File metadata and controls
30 lines (30 loc) · 1.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int total_line(vector<int>&nums1,vector<int>&nums2,int i,int j,vector<vector<int>>&dp){
if(i>=nums1.size() or j>=nums2.size()){
return 0;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
if(nums1[i]==nums2[j]){
return dp[i][j]=1+total_line(nums1,nums2,i+1,j+1,dp);
}
return dp[i][j]=max(total_line(nums1,nums2,i+1,j,dp),total_line(nums1,nums2,i,j+1,dp));
}
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,-1));
for(int i=0;i<=nums1.size();i++){
for(int j=0;j<=nums2.size();j++){
if(i==0 or j==0){
dp[i][j]=0;
}else if(nums1[i-1]==nums2[j-1]){
dp[i][j]=1+dp[i-1][j-1];
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[nums1.size()][nums2.size()];
}
};