最长公共子序列---dp

思路：

看似好像可以用双指针或者map集合写，但仔细想一下还是行不通。

dp[i]表示text1在第i个位置上最长的公共子序列。

首先记住一句话，两个字符串做比较，求最长公共子序列，通常用二维dp。

class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); int [][] dp = new int[m + 1][n + 1]; for(int i = 1;i <= m;i ++){ for(int j = 1;j <= n;j ++){ char ch1 = text1.charAt(i - 1); char ch2 = text2.charAt(j - 1); if(ch1 == ch2){ 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]; } }

为什么不能直接写成 m 和 n？

假设：

text1 = "abcde"; // m = 5 text2 = "ace"; // n = 3

如果你写：

int[][] dp = new int[m][n];

数组大小就是：

dp[5][3]

它的合法下标是：

行：0 ~ 4 列：0 ~ 2

但是你的代码最后返回的是：

return dp[m][n];

也就是：

return dp[5][3];

这就越界了，因为最大只能访问：

dp[4][2]

所以会报错：

ArrayIndexOutOfBoundsException