Leetcode Problem 1035. Uncrossed Lines

1035. Uncrossed Lines

Leetcode Solutions

Dynamic Programming with Space Optimization

  1. Initialize two arrays dp and dpPrev of size n2 + 1 with all elements set to 0.
  2. Iterate over the elements of nums1 using an outer loop with index i.
  3. For each i, iterate over the elements of nums2 using an inner loop with index j.
  4. If nums1[i - 1] == nums2[j - 1], set dp[j] to 1 + dpPrev[j - 1].
  5. If nums1[i - 1] != nums2[j - 1], set dp[j] to the maximum of dp[j - 1] and dpPrev[j].
  6. After completing the inner loop, copy the contents of dp to dpPrev.
  7. The final answer is dp[n2], which represents the maximum number of uncrossed lines.
UML Thumbnail

Iterative Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...