# Intuition\nWhen you see a dynamic programming problem solution, you usually feel confusely on how the solution been. Because Dynamic Programming is an iterative evolution progress. You can\'t just look at the problem and suddenly bump a best solution, ok maybe somebody can. But to me it is a progress need to think step by step.\n\nHere I will show you what kind of methods I have been thought, and how to do the problem.\n\n# Approach\nRecursion && Dynamic Programming.\n\n### Method 1 : Non-memoization recursion, TLE.\n> This method use a non-memoization recursion. Too many duplicate steps been run repeatedly.\n\n### Method 2 : 2D Dynamic Programming with Top Down.\n> This problem has 2 conditions. One is `nums1[i] == nums2[j]` and another is `nums1[i] != nums2[j]`.\n> We need to deal these 2 conditions seperately. You can find the proof of why these 2 conditions can help in the other solution comments.\n> 1. `result[i][j] = max(result[i-1][j], result[i][j-1])`\n> 2. `result[i][j] = result[i-1][j-1] + 1`\n\n> This time I use HashMap to record each result, such method can skip those duplicate calculations.\n\n### Method 3 : 2D Dynamic Programming with Bottom Up.\n> We use recursion to solve this problem in method 2. Maybe it is a little bit too complex?\n> Usually, I use for loop more than recursion.\n> Need to reverse our thinking when use bottom up.\n\n### Method 4 : 1D Dynamic Programming.\n> Why we need to save all of the results?\n> Actually, just use previous and current row when calculate uncrossed lines of each point (i, j) in variable `result` at method 2 and 3.\n> So we only need to save 1D result.\n\n# Complexity\n- Time complexity:\nMethod 1 : $$O(2^n)$$\nMethod 2 : $$O(i*j)$$\nMethod 3 : $$O(i*j)$$\nMethod 4 : $$O(i*j)$$\n\n- Space complexity:\nMethod 1 : $$O(i*j)$$\nMethod 2 : $$O(i*j)$$\nMethod 3 : $$O(i*j)$$\nMethod 4 : $$O(i)$$\n\n\n# Code\n### Method 1 (TLE)\n```rust [method 1]\nuse std::cmp;\nimpl Solution {\n pub fn max_uncrossed_lines(nums1: Vec, nums2: Vec) -> i32 {\n let len_1 = nums1.len();\n let len_2 = nums2.len();\n let mut result = vec![vec![0; len_2+1]; len_1+1];\n Self::divide_conquer(len_1, len_2, &nums1, &nums2, &mut result)\n }\n\n fn divide_conquer(i: usize, j: usize, nums1: &Vec, nums2: &Vec, result: &mut Vec>) -> i32 {\n if i == 0 || j == 0 || i > nums1.len() || j > nums2.len() {\n return 0\n }\n if result[i][j] > 0 {\n return result[i][j]\n }\n\n match nums1[i-1] == nums2[j-1] {\n true => result[i][j] = Self::divide_conquer(i-1, j-1, nums1, nums2, result) + 1,\n false => result[i][j] = cmp::max(Self::divide_conquer(i-1, j, nums1, nums2, result), Self::divide_conquer(i, j-1, nums1, nums2, result)),\n }\n\n result[i][j]\n }\n}\n```\n### Method 2 (2D DP with Top Down)\n```rust [method 2]\nuse std::cmp;\nuse std::collections::HashMap;\nimpl Solution {\n pub fn max_uncrossed_lines(nums1: Vec, nums2: Vec) -> i32 {\n let len_1 = nums1.len();\n let len_2 = nums2.len();\n let mut result = HashMap::new();\n for index1 in 1..len_1+1 {\n for index2 in 1..len_2+1 {\n result.insert((index1, index2), -1);\n }\n }\n Self::dynamic_programming(len_1, len_2, &nums1, &nums2, &mut result)\n }\n\n // i, j mean to amount i and amount j, not index i and index j\n fn dynamic_programming(i: usize, j: usize, nums1: &Vec, nums2: &Vec, result: &mut HashMap<(usize, usize), i32>) -> i32 {\n if i == 0 || j == 0 || i > nums1.len() || j > nums2.len() {\n return 0\n }\n\n let &value = result.get(&(i, j)).unwrap();\n if value >= 0 {\n return value\n }\n\n let mut temp = 0;\n match nums1[i-1] == nums2[j-1] {\n true => temp = Self::dynamic_programming(i-1, j-1, nums1, nums2, result) + 1,\n false => temp = cmp::max(Self::dynamic_programming(i-1, j, nums1, nums2, result), Self::dynamic_programming(i, j-1, nums1, nums2, result)),\n };\n\n result.insert((i, j), temp);\n *result.get(&(i, j)).unwrap()\n }\n}\n```\n### Method 3 (2D DP with Bottom Up)\n```rust [method 3]\nuse std::cmp;\nuse std::collections::HashMap;\nimpl Solution {\n pub fn max_uncrossed_lines(nums1: Vec, nums2: Vec) -> i32 {\n let len_1 = nums1.len();\n let len_2 = nums2.len();\n Self::dynamic_programming(len_1, len_2, &nums1, &nums2)\n }\n\n fn dynamic_programming(i: usize, j: usize, nums1: &Vec, nums2: &Vec) -> i32 {\n if i < 0 || j < 0 || i > nums1.len() || j > nums2.len() {\n return 0\n }\n\n let mut result = HashMap::new();\n for index_i in 1..i+1 {\n for index_j in 1..j+1 {\n let mut temp = 0;\n match nums1[index_i-1] == nums2[index_j-1] {\n true => temp = *result.get(&(index_i-1, index_j-1)).unwrap_or(&0) + 1,\n false => temp = cmp::max(*result.get(&(index_i-1, index_j)).unwrap_or(&0), *result.get(&(index_i, index_j-1)).unwrap_or(&0)),\n };\n result.insert((index_i, index_j), temp);\n }\n }\n\n result[&(i, j)]\n }\n}\n```\n### Method 4 (1D DP)\n```rust [method 4]\nuse std::cmp;\nimpl Solution {\n pub fn max_uncrossed_lines(nums1: Vec, nums2: Vec) -> i32 {\n let len_1 = nums1.len();\n let len_2 = nums2.len();\n Self::dynamic_programming(len_1, len_2, &nums1, &nums2)\n }\n\n fn dynamic_programming(i: usize, j: usize, nums1: &Vec, nums2: &Vec) -> i32 {\n if i < 0 || j < 0 || i > nums1.len() || j > nums2.len() {\n return 0\n }\n\n let mut row_previous = vec![0; j+1];\n for index_i in 1..i+1 {\n let mut row_current = vec![0; j+1];\n for index_j in 1..j+1 {\n match nums1[index_i-1] == nums2[index_j-1] {\n true => row_current[index_j] = row_previous[index_j-1] + 1,\n false => row_current[index_j] = cmp::max(row_current[index_j-1], row_previous[index_j]),\n };\n }\n row_previous = row_current;\n }\n\n row_previous[j]\n }\n}\n```\n

Uncrossed Lines

Problem Description

Problem Description

Answer Panel