力扣算法学习day36-3
1142-最长公共子序列
题目
代码实现
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// dp 速度 5ms
// 求子序列、子数组问题是经常考虑dp的，我发现最近做这些题，自己老是喜欢去找规律，而不是找
// 递推关系，这道题就是，我感觉是思考方向不对。做dp的题一定要找递推关系，依赖关系。
// 题目分析：
// 递推关系：两个的字符串都先取长度为1的子字符串，即取第一个元素开始，依次遍历，比如第一次取第一个元素
// 第二次取第一和第二个元素.... 即取0-i的子字符串。比如示例一，text1先取a，text2也取a可以知道，这两个
// 公共子字符串最大长度就为1，即为1-1,1-1(两个子字符串长度-1)，两个都取空这种情况是最大子序列长度为0的，
// 然后在它的基础上加1得到，然后在遍历的过程肯定是需要一个先遍历完才行嘛(这个不需要解释了吧)，这里我
// 就举例示例1，示例1中text2先遍历增加，即先取text1的第一个a，然后再依次取text2的取前1个、前2个、前i个
// 元素的子字符串与text1取1个比较，text2取一个已经分析了，如果text2取前两个，那么就是ac，a和c不一样，
// 所以它需要看a和a，即前面这种情况和空和ac这两种情况的最大子序列。即1.
// 注：这里主要举例一下这个递推关系，后面的可以自己想了。
// 迭代公式：dp[i][j]=?
// 1.如果text1在i的元素等于text2的元素，说明尾部元素相等，那么两个子字符串的公共子序列长度一定在dp[i-1][j-1]
// 的基础上+1(即子字符串取text1的i-1,和text2的j-1那种情况的最大子序列+1);即：dp[i][j] = dp[i-1][j-1]+1;
// 2.如果不相等，那就取 子字符串取text1的i-1,text2的j 和 子字符串取text1的i,text2的j-1两种情况取最大值即可
// 即：dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); 这里迭代公式实际上已经确定了
char[] list1 = text1.toCharArray();
char[] list2 = text2.toCharArray();
int[][] dp = new int[list1.length+1][list2.length+1];
for(int i = 1;i < list1.length+1;i++){
for(int j = 1;j < list2.length+1;j++){
if(list1[i-1] == list2[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]);
}
}
}
return dp[list1.length][list2.length];
}
// 我首先想到的方法，先将第一个数组在第二个数组中出现的坐标求出来，凡是在第二个数组没有的就
// 将其剔除，剔除方式是，造一个ArrayList来存储求出来的第一个数组存在的值在第二个数组中的位置
// 这里存入是是带顺序的，然后就将问题转化为了一个求单调递增子序列问题了，因为两个字符串有顺序
// 且需要求公共的带顺序相同的子序列，那么这种方式求出来后就找坐标单调递增可以剔除中间的其他坐标
// 求最长即可，即我说的转化为求单调递增子序列的问题。但是提交超时了。然后，我看了哈超时的案例，
// 实际上，，是错的，因为我看到案例1,2,3后，直接就想的是没有字母重复出现的情况，所以这种方法
// 不仅仅是超时，而且不对，不过，如果这道题换成字符不重复的话理论上应该是成立的。
// public int longestCommonSubsequence(String text1, String text2) {
// char[] list1 = text1.toCharArray();
// char[] list2 = text2.toCharArray();
// List<Integer> list = new ArrayList<>();
// for(int i = 0;i < list1.length;i++){
// for(int j = 0;j < list2.length;j++){
// if(list1[i] == list2[j]){
// list.add(j);
// }
// }
// }
// if(list.isEmpty()){
// return 0;
// }
// int[] dp = new int[list.size()];
// for(int i = 0;i < dp.length;i++){
// dp[i] = 1;
// }
// int result = 1;
// for(int i = 1;i < list.size();i++){
// int temp = list.get(i);
// for(int j = 0;j < i;j++){
// if(list.get(j) < temp){
// dp[i] = dp[j] + 1;
// }
// if(result < dp[i]){
// result = dp[i];
// }
// }
// }
// // p q r s
// // 9 6 7 0
// return result;
// }
}