前言在 LeetCode 动态规划刷题中最长公共子序列LCS是最经典的基础模型之一。而「1035. 不相交的线」本质就是最长公共子序列的换皮题掌握一道即可通杀两道。一、1143. 最长公共子序列题目描述给定两个字符串text1和text2返回两字符串最长公共子序列的长度无公共子序列返回 0。子序列不改变相对顺序删除部分字符可不删得到的新串公共子序列两个字符串共有的子序列动态规划思路状态定义dp[i][j]表示text1前i个字符、text2前j个字符的最长公共子序列长度。状态转移若text1[i-1] text2[j-1]当前字符匹配结果 前 i-1、j-1 的结果 1dp[i][j] dp[i-1][j-1] 1若不相等取「text1 少一个字符」或「text2 少一个字符」的最大值dp[i][j] max(dp[i-1][j], dp[i][j-1])初始化dp[0][j] 0、dp[i][0] 0空串与任何串的公共子序列长度为 0。Java 代码class Solution { public int longestCommonSubsequence(String text1, String text2) { int m text1.length(), n text2.length(); // dp[i][j]text1前i个text2前j个的最长公共子序列长度 int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { char c1 text1.charAt(i - 1); for (int j 1; j n; j) { char c2 text2.charAt(j - 1); if (c1 c2) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } }测试用例 结果输入text1 abcde,text2 ace输出3输入text1 abc,text2 abc输出3输入text1 abc,text2 def输出0二、1035. 不相交的线题目描述在两条水平线上按顺序写nums1、nums2连线满足nums1[i] nums2[j]连线不相交端点也不能相交求最大连线数量。核心与 LCS 完全等价连线不相交 → 数字的相对顺序必须保持不变→ 本质就是求两个数组的最长公共子序列长度动态规划思路与 1143 完全一致仅把字符串换成数组即可。Java 代码class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { int num1 nums1[i - 1]; for (int j 1; j n; j) { int num2 nums2[j - 1]; if (num1 num2) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } }测试用例 结果输入nums1 [1,4,2],nums2 [1,2,4]输出2输入nums1 [2,5,1,2,5],nums2 [10,5,2,1,5,2]输出3输入nums1 [1,3,7,1,7,5],nums2 [1,9,2,5,1]输出2