C++刷leetcode（1035. 不相交的线）【动态规划】

糖逗

题目描述：

1. 我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
   
2. 
   
3. 现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
   
4. 
   
5. 以这种方法绘制线条，并返回我们可以绘制的最大连线数。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 
    
13. 输入：A = [1,4,2], B = [1,2,4]
    
14. 输出：2
    
15. 解释：
    
16. 我们可以画出两条不交叉的线，如上图所示。
    
17. 我们无法画出第三条不相交的直线，因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。
    
18. 示例 2：
    
19. 
    
20. 输入：A = [2,5,1,2,5], B = [10,5,2,1,5,2]
    
21. 输出：3
    
22. 示例 3：
    
23. 
    
24. 输入：A = [1,3,7,1,7,5], B = [1,9,2,5,1]
    
25. 输出：2
    
26.  
    
27. 
    
28. 提示：
    
29. 
    
30. 1 <= A.length <= 500
    
31. 1 <= B.length <= 500
    
32. 1 <= A[i], B[i] <= 2000
    
33. 
    
34. 来源：力扣（LeetCode）
    
35. 链接：https://leetcode-cn.com/problems/uncrossed-lines
    
36. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int maxUncrossedLines(vector<int>& A, vector<int>& B) {
   
4.         vector<int> store1, store2;
   
5.         int k = 0;
   
6.         for(int i = 0; i < A.size(); i++){
   
7.             k++;
   
8.             for(int j = 0; j < B.size(); j++){
   
9.                 if(B[j] == A[i]){
   
10.                     store1.push_back(j);
    
11.                     store2.push_back(k);
    
12.                 }
    
13.             }
    
14.         }
    
15.         vector<int> dp(store1.size(), 1);
    
16.         int res = 0;
    
17.         for(int i = 0; i < store1.size(); i++){
    
18.             for(int j = 0; j < i; j++){
    
19.                 if(store1[j] < store1[i] && store2[j] != store2[i]){
    
20.                     dp[i] = max(dp[j] + 1, dp[i]);
    
21.                 }
    
22.             }
    
23.             res = max(dp[i], res);
    
24.         }
    
25.         return res;
    
26.     }
    
27. };

复制代码

糖逗

勉强通过