难度：中等 今天做了一个最长公共子数组，评论里面很多人提到这道题，就顺便一起做了。子数组是连续的，如果某个位置没匹配上就直接等于0，以这个位置为起点重新匹配。这个子序列可以不连续，如果匹配上那就直接等于dp[i][j]+1 如果没匹配上，就取前面过程中的最大值 题目描述 解题思路 还是动态规划，dp[i][j]代表以A[i-1]与B[j-1]结尾的子序列的长度。 如果某个位置匹配上了，那么加一。 如果没匹配上，一个位置没匹配上并不影响总的值，在dp[i][j+1], dp[i+1][j]中取一个较大的作为当前位置的值。
/* * 1143. 最长公共子序列 * 子序列不要求连续 * 2020/7/1 */ public int longestCommonSubsequence(String text1, String text2) { char[] s1 = text1.toCharArray(); char[] s2 = text2.toCharArray(); int m = s1.length,n = s2.length; int[][] dp = new int[m+1][n+1]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if(s1[i] == s2[j]) { dp[i+1][j+1] = dp[i][j]+1; }else { dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]); } } } return dp[m][n]; }