1.题目描述

2.思路

每个格子 dp[i][j] 都表示：

从字符串开头开始，分别取前 i 个字符和前 j 个字符之间的最优子结构（最长公共子序列的长度）

最终的 dp[m][n] 表示的就是：

“从头到尾整个 text1 和 text2 的最长公共子序列长度”。
答：不需要，因为我们构造 dp[i][j] 的时候，就是按“从左上到右下”的顺序，逐步比较两个字符串的公共子序列长度。

3.代码实现

class Solution {public int longestCommonSubsequence(String text1, String text2) {//获取 text1 和 text2 的长度，分别保存在变量 m 和 n 中int m=text1.length();int n=text2.length();//定义一个二维数组 dp，其中 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。初始化大小为 (m+1) x (n+1)，额外的一行一列用来处理边界情况（空串时的 LCS）。int[][] dp=new int[m+1][n+1];for(int i=1;i<=m;i++){//外层循环遍历 text1 的每个字符，i 表示当前处理的字符在 text1 中的索引加一（因为 dp 数组是从 1 开始的）。//获取 text1 的第 i-1 个字符，保存在变量 c1 中char c1=text1.charAt(i-1);for(int j=1;j<=n;j++){//内层循环遍历 text2 的每个字符，j 表示当前处理的字符在 text2 中的索引加一。//获取 text2 的第 j-1 个字符，保存在变量 c2 中。char c2=text2.charAt(j-1);//如果 text1 和 text2 当前字符相同if(c1==c2){//则当前的 LCS 长度在原有的基础上 +1（即在 text1[0..i-2] 和 text2[0..j-2] 的 LCS 长度基础上加 1）。dp[i][j]=dp[i-1][j-1]+1;}else{//如果字符不同，那么当前的 LCS 就是从两个子问题中取较大的一个：//不选 text1[i-1]，即 dp[i-1][j]//不选 text2[j-1]，即 dp[i][j-1]dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];}
}