快点击这里征服第一道！！！
快点击这里征服第二道！！！
题目描述：
求两个 int 数组 nums1 和 nums2 的最长公共子序列的长度，什么是子序列呢？子序列就是从右开始到左顺序的，可以不连续的序列，例如【1，3，5，9，10】和【1，4，9，10】的最长公共子序列就是【1，9，10】，所以长度是3；例如【1，5，11，22，88】和【5，4，2，11，8】的最长公共子序列就是【5，11】长度是2，切记子序列不是子串，子串是连续的，而子序列可以不是连续的。
做题思路：
1.实际上动态规划是一个不断优化的过程，接下来我将用四种方式解决这道题目，而且效率是不断提升的，代码是不断优化的，但是整体思路是没有很大改变的，只是局部作出了优化。
2.假设dp（i，j）是【nums1前 i 个元素】和【nums2前 j 个元素】的最长公共子序列长度
dp（0，j）和dp（i，0）初始值均为0，因为dp（0，j）代表【nums1前 0 个元素】和【nums2前 j 个元素】的最长公共子序列长度，那肯定是0嘛，此时不存在公共部分。
2.1 如果 nums1【i - 1】== nums2【j - 1】，那么dp（i，j）= dp（i - 1，j - 1）+ 1，因为例如【1，3，5，9，10】和【1，4，9，10】，当遍历到 nums1【3】和 nums2【2】 时，元素9和元素9是相等的，所以不管怎么计算，此时两个数组的最长公共子序列长度肯定确定至少是1了，那么我们还得加上以前的最长公共子序列，也就是dp（i - 1，j - 1），就是此时的最长公共子序列。
2.2 如果 nums1【i - 1】 != nums2【j - 1】，那么dp（i，j）= max{ dp（i - 1，j），dp（i，j - 1）}，max代表取出这个集合的较大值，例如【1，3，5，9，10】和【1，4，9，10】，当遍历到 nums1【2】和 nums2【2】 时，元素5和元素9是不相等的，此时我们确定当前遍历到的两个元素，肯定不是组成最长公共子序列的一部分，所以排除，但是，dp（3，3）总得有值吧，因为这是递推，从底向上层层递推，所以此时dp（3，3）的值就是 dp（i - 1，j）或者dp（i，j - 1），哪个长就取哪个。
我先用递归的方法解决这个问题，如果我有些没写清楚或者写错的，可以评论区或者私信我喔
-
/**
-
* 递归方法实现
-
*/
-
public class LCS {
-
-
public static void main(String[] args) {
-
int[] nums1 = {1,3,4,10};
-
int[] nums2 = {1,2,3,4,10,11};
-
System.out.println(lcs(nums1, nums2));
-
}
-
-
static int lcs(int[] nums1, int[] nums2) {
-
if(nums1 == null || nums1.length == 0) return 0;
-
if(nums2 == null || nums2.length == 0) return 0;
-
//递归调用
-
return lcs1(nums1 , nums1.length,nums2,nums2.length);
-
}
-
-
static int lcs1(int[] nums1 , int i, int[] nums2,int j) {
-
//因为当i或者j等于0，说明已经某一个数组已经比较完了
-
if(i == 0 || j == 0) return 0; //递归基，也就是递归什么时候结束的条件
-
//递归调用
-
//这里类似于dp（i,j） = max{dp(i - 1,j),dp(i,j - 1)}
-
if(nums1[i - 1] != nums2[j - 1]) return Math.max(lcs1(nums1, i - 1, nums2, j), lcs1(nums1, i, nums2, j - 1));
-
//这里类似于dp（i,j） = dp(i - 1，j - 1) + 1
-
return lcs1(nums1,i - 1,nums2,j - 1) + 1;
-
}
-
}
用动态规划的方法解决这个问题，如果我有些没写清楚或者写错的，可以评论区或者私信我喔
-
public class LCS {
-
-
public static void main(String[] args) {
-
// TODO Auto-generated method stub
-
int[] nums1 = {1,3,4,10};
-
int[] nums2 = {1,2,3,4,10,11};
-
System.out.println(lcs(nums1, nums2));
-
}
-
-
static int lcs(int[] nums1, int[] nums2) {
-
if(nums1 == null || nums1.length == 0) return 0;
-
if(nums2 == null || nums2.length == 0) return 0;
-
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
-
//遍历二维数组
-
for (int i = 1; i <= nums1.length; i++) {
-
for (int j = 1; j <= nums2.length; j++) {
-
if(nums1[i - 1] == nums2[j - 1]) { //如果元素相等，就把前面的最长公共子序列 的个数 + 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[nums1.length][nums2.length];
-
}
-
}
都看到这里了，不考虑点个赞再走嘛？如果大家不点赞的话，我的心就是冰冰的了
文章来源: blog.csdn.net，作者：小胖java攻城狮，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq_45798556/article/details/114883828