https://h1ros.github.io/posts/coding/1035-uncrossed-lines/
but now the problem description includes the following: "Note that a connecting line cannot intersect even at the endpoints: each number can only belong to one connecting line."
https://leetcode.com/problems/uncrossed-lines/discuss/282842/JavaC%2B%2BPython-DP-The-Longest-Common-Subsequence
public int maxUncrossedLines(int[] A, int[] B) {
int m = A.length, n = B.length, dp[][] = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (A[i - 1] == B[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
return dp[m][n];
}
https://leetcode.com/problems/uncrossed-lines/discuss/282998/memorization-search-and-brute-force-way-using-JAVA
public int maxUncrossedLines(int[] A, int[] B) {
int n = A.length;
int m = B.length;
Integer[][] dp = new Integer[n][m];
return findMaxLines(dp, A, B, 0, 0);
}
public int findMaxLines(Integer[][] dp, int[] A, int[] B, int i, int j){
if(j>=B.length || i>=A.length){
return 0;
}
if(dp[i][j]!=null){
return dp[i][j];
}
int max = Integer.MIN_VALUE;
if(A[i]==B[j]){
max = findMaxLines(dp, A, B, i+1, j+1)+1;
}
max = Math.max(max, findMaxLines(dp, A, B, i+1, j));
max = Math.max(max, findMaxLines(dp, A, B, i, j+1));
dp[i][j] = (max==Integer.MIN_VALUE)?0:max;
return dp[i][j];
}
虽然题目看起来有点复杂，其实就是求最长公共子串的长度。连线互不交叉其实就是公共子串换了一种说法而已。
本题可以采用动态规划的方法。记dp[i][j]为A[i]与B[j]连线后可以组成的最多连线的数量，当然这里A[i]与B[j]连线是虚拟的连线，因此存在A[i] != B[j]的情况。首先来看A[i] == B[j]，这说明A[i]与B[i]可以连线，显然有dp[i][j] = dp[i-1][j-1]+1；如果是A[i] != B[j]，那么分为三种情况dp[i][j] = max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])，这是因为A[i]不与B[j]连线，但是A[i]可能可以与B[j]之前所有点的连线，同理B[j]也是一样的。
本题可以采用动态规划的方法。记dp[i][j]为A[i]与B[j]连线后可以组成的最多连线的数量，当然这里A[i]与B[j]连线是虚拟的连线，因此存在A[i] != B[j]的情况。首先来看A[i] == B[j]，这说明A[i]与B[i]可以连线，显然有dp[i][j] = dp[i-1][j-1]+1；如果是A[i] != B[j]，那么分为三种情况dp[i][j] = max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])，这是因为A[i]不与B[j]连线，但是A[i]可能可以与B[j]之前所有点的连线，同理B[j]也是一样的。
Similar problems
Longest Increasing Subsequence - https://leetcode.com/problems/longest-increasing-subsequence/
Longest Common Subsequence - https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
