leetcode

commit b06d7a42ad7246c9aaa58f15dc98b082d66ec8c1
parent 5c9dcaf38e891d0421176ac927cf817e22d04a18
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 11 May 2023 20:28:44 +0200

Daily Problem

Diffstat:
A
Problems/1035.cpp
 | 
22
++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 23 insertions(+), 0 deletions(-)
diff --git a/Problems/1035.cpp b/Problems/1035.cpp
@@ -0,0 +1,22 @@
+class Solution {
+  int dp[500][500];
+
+public:
+  Solution() { memset(dp, 0xFF, sizeof(dp)); }
+
+  int maxUncrossedLines(const vector<int> &nums1, const vector<int> &nums2,
+                        int i = 0, int j = 0) {
+    if (i >= nums1.size() || j >= nums2.size()) return 0;
+    if (dp[i][j] != -1) return dp[i][j];
+
+    int res;
+    if (nums1[i] == nums2[j])
+      res = 1 + maxUncrossedLines(nums1, nums2, i + 1, j + 1);
+    else {
+      res = max(maxUncrossedLines(nums1, nums2, i + 1, j),
+                maxUncrossedLines(nums1, nums2, i, j + 1));
+    }
+
+    return dp[i][j] = res;
+  }
+};
diff --git a/README.md b/README.md
@@ -395,6 +395,7 @@ for solving problems.
 |  1020  |   Medium   | [Number of Enclaves](Problems/1020.cpp)                                                          |
 |  1022  |    Easy    | [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp)                                          |
 |  1026  |   Medium   | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp)                                |
+|  1035  |   Medium   | [Uncrossed Lines](Problems/1035.cpp)                                                             |
 |  1038  |   Medium   | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp)                                      |
 |  1042  |   Medium   | [Flower Planting With No Adjacent](Problems/1042.cpp)                                            |
 |  1046  |    Easy    | [Last Stone Weight](Problems/1046.cpp)                                                           |