Leetcode 1035. 不相交的线

Java AC

• 相当于求两个数组的最长公共子序列，因为k对连线，就是这两数组的公共子序列。

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        for (int i = 1; i <= nums1.length; i++) {
            int n1 = nums1[i-1];
            for (int j = 1; j <= nums2.length; j++) {
                int n2 = nums2[j-1];
                if (n1==n2){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}