思路：本题与上一题的唯一不同点在于本题的子序列是可以不连续的，而上一题的子序列必须是连续的，我们在上一题的推导过程中只对两边nums1[i-1]和nums2[j-1]的情况进行推导，因为在连续约束下如果当前判断的值不相同，自然也不存在连续相同的子序列，而本题不同没有必须连续的要求，也就是在nums1[i-1]和nums2[j-1]不相同的情况下，也依然可能存在相同的子序列，在这种情况下的dp[i][j]就要继承上一位的值，上一位的值有两种情况dp[i-1][j]和dp[i][j-1]，继承其中最大的即可
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int res = 0;
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
// 从连续变成了不连续
for (int i = 1; i < text1.length() + 1 ; i++) {
for (int j = 1; j < text2.length() + 1;j++){
if (text1.charAt(i - 1) == text2.charAt( j - 1)){
dp[i][j] = dp[i-1][j-1] + 1;
// 在值不相同的时候需要继承上一位的情况
}else {
// 至于继承哪个情况要看哪种情况最大
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
res = Math.max(res,dp[i][j]);
}
}
return res;
}
}
