【算法与数据结构】718、1143、1035、392、115、LeetCode最长重复子数组+最长公共子序列+不相交的线+判断子序列+不同的子序列

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、718、最长重复子数组

  思路分析：

• 第一步，动态数组的含义。$dp[i][j]$代表以下标$i-1$为结尾的nums1，和以下标$j-1$为结尾的nums2，最长重复子数组长度为$dp[i][j]$。
• 第二步，递推公式。根据$dp[i][j]$的定义，$dp[i][j]$的状态只能由$dp[i-1][j-1]$推导出来。

	if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;

• 第三步，元素初始化。dp数组中的所有元素都初始化为0。
• 第四步，递归顺序。一共有两层循环，先遍历nums1或者先遍历nums2都可以。
• 第五步，打印结果。题目要求长度最长的子数组的长度。所以在遍历的时候顺便把$dp[i][j]$的最大值记录下来。
    程序如下：

// 718、最长重复子数组
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > result) result = dp[i][j];}}return result;}
};

复杂度分析：

• 时间复杂度： $O(n\ast m)$，$n$和$m$分别是两个数组的长度。
• 空间复杂度：$O(n\ast m)$。

二、1143、最长公共子序列

  思路分析：

1. 第一步，动态数组的含义。$dp[i][j]$代表以下标$i-1$为结尾的text1，和以下标$j-1$为结尾的text2，最长公共子序列长度为$dp[i][j]$。
2. 第二步，递推公式。$dp[i][j]$可以由两种情况推导出来：

• $text1[i-1]$与 $text2[j-1]$相同：那么找到一个公共元素，$dp[i][j]=dp[i-1][j-1]+1$。
• $text1[i-1]$ 与 $text2[j-1]$不相同：那么$text1[0,i-2]$与$text2[0,j-1]$的最长公共子序列和$text1[0,i-1]$与$text2[0,j-2]$的最长公共子序列，取最大的。

	if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

3. 第三步，元素初始化。dp数组中的所有元素都初始化为0。
4. 第四步，递归顺序。一共有两层循环，从前往后进行遍历。
5. 第五步，打印结果。题目要求最长公共子序列的长度。所以在遍历的时候顺便把$dp[i][j]$的最大值记录下来。
     程序如下：

// 1143、最长公共子序列
class Solution2 {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));int result = 0;for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if(dp[i][j] > result) result = dp[i][j];}}return result;}
};

复杂度分析：

• 时间复杂度： $O(n\ast m)$，$n$和$m$分别是两个序列的长度。
• 空间复杂度：$O(n\ast m)$。

三、1035、不相交的线

  思路分析：本题要求绘制的最大连线数，实际上就是求两个字符串的最长公共子序列的长度，即1143、最长公共子序列这道题。我们将字符串改成数组，代码完全一样，直接copy过来。
  程序如下：

// 1035、不相交的线
class Solution3 {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if (dp[i][j] > result) result = dp[i][j];}}return result;}
};

复杂度分析：

• 时间复杂度： $O(n\ast m)$，$n$和$m$分别是两个数组的长度。
• 空间复杂度：$O(n\ast m)$。

四、392、判断子序列

  思路分析：本题的思路和1143、最长公共子序列的分析思路差不多，主要区别在于本题判断的是“ 最长公共子序列是不是另一个字符串的子串”。那么我们找到二者的最长公共子串，判断其长度是否等于s的长度即可。

1. 第一步，动态数组的含义。$dp[i][j]$代表以下标$i-1$为结尾的s，和以下标$j-1$为结尾的t，最长公共子序列长度为$dp[i][j]$。
2. 第二步，递推公式。$dp[i][j]$可以由两种情况推导出来：

• $s[i-1]$与 $t[j-1]$相同：那么找到一个公共元素，$dp[i][j]=dp[i-1][j-1]+1$。
• $s[i-1]$ 与 $t[j-1]$不相同：那么$dp[i][j]$等于$s[0,i-1]$与$t[0,j-2]$的最长公共子序列。

	if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = dp[i][j - 1];		// 与1143不同的地方

3. 第三步，元素初始化。dp数组中的所有元素都初始化为0。
4. 第四步，递归顺序。一共有两层循环，从前往后进行遍历。
5. 第五步，打印结果。题目要求最长公共子序列的长度。所以在遍历的时候顺便把$dp[i][j]$的最大值记录下来，在用三目运算符返回。

	return result == s.size() ? true : false;	// 与1143不同的地方

  程序如下：

// 392、判断子序列-动态规划
class Solution4 {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));int result = 0;for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = dp[i][j - 1];		// 与1143不同的地方if (dp[i][j] > result) result = dp[i][j];}}return result == s.size() ? true : false;	// 与1143不同的地方}
};

复杂度分析：

• 时间复杂度： $O(n\ast m)$，$n$和$m$分别是两个字符串的长度。
• 空间复杂度：$O(n\ast m)$。

五、115、不同的子序列

  思路分析：本题的思路和1143、最长公共子序列的分析思路差不多。本题统计字符串t在字符串s中出现的次数，我们可以理解为删除掉字符串s中的部分字符使得字符串s和字符串t相同的方法数量。

1. 第一步，动态数组的含义。$dp[i][j]$代表以下标$j-1$为结尾的t在以下标$i-1$为结尾的s中出现的次数为$dp[i][j]$，即$t[0,j-1]$在$s[0,i-1]$中出现的次数。

2. 第二步，递推公式。$dp[i][j]$可以由两种情况推导出来：

• $s[i-1]$与$t[j-1]$相同：此时的$dp[i][j]$由两部分组成。一部分是用$s[i-1]$来匹配：相当于在$s[0,i-2]$中寻找$t[0,j-2]$的个数（剩下一个字符$s[i-1]$与 $t[j-1]$已经匹配了），即$dp[i-1][j-1]$；另一部分是不用$s[i-1]$来匹配，相当于在$s[0,i-2]$中寻找$t[0,j-1]$的个数，即$dp[i-1][j]$。
• $s[i-1]$ 与 $t[j-1]$不相同：那么$s[0,i-2]$中，$t[0,j-1]$的数量和 $s[0,i-1]$中，$t[0,j-1]$的数量相同。$dp[i][j]=dp[i-1][j]$

	if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];	else dp[i][j] = dp[i - 1][j];

  例子：s=“bageg”,t=“bag”。那么用s[4]="g"组成bag的方法数量，相当于在s[0, 3]="bage"中寻找中t[0, 1]="ba"的个数，只有s[0]s[1]s[4]这一种。而不用s[4]="g"组成bag的方法数量，相当于在s[0,3] ="bage"中，寻找t[0,2]="bag"的个数，即dp[4, 3]，只有s[0]s[1]s[2]这一种。（说明：dp[4,2]=1代表在s[0,3] ="bage"中，t[0,1]="ba"的个数为1。）

3. 第三步，元素初始化。$dp[i][0]$（第一列）表示字符串$s[0,i-1]$中可以随便删除元素，出现空字符串的个数。$dp[0][j]$（第一行）表示空字符串$s$，出现字符串$t[0,j-1]$的个数。其中，空字符串s中空字符串t的个数为1。那么$dp[0][0]=1,dp[i][0]=1,dp[0][j]=0$。
4. 第四步，递归顺序。一共有两层循环，从前往后进行遍历。
5. 第五步，打印结果。
     程序如下：

// 115、不同的子序列-动态规划
class Solution5 {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;		// 第一列初始化为1, dp[0][0]为1for (int j = 1; j <= t.size(); j++) dp[0][j] = 0;		// 第一行初始化为0, 可以省略for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];	else dp[i][j] = dp[i - 1][j];}}return dp[s.size()][t.size()];}
};

复杂度分析：

• 时间复杂度： $O(n\ast m)$，$n$和$m$分别是两个字符串的长度。
• 空间复杂度：$O(n\ast m)$。

六、完整代码

# include <iostream>
# include <vector>
# include <string>
using namespace std;// 718、最长重复子数组
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > result) result = dp[i][j];}}return result;}
};// 1143、最长公共子序列
class Solution2 {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));int result = 0;for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if (dp[i][j] > result) result = dp[i][j];}}return result;}
};// 1035、不相交的线-动态规划
class Solution3 {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if (dp[i][j] > result) result = dp[i][j];}}return result;}
};// 392、判断子序列-动态规划
class Solution4 {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));int result = 0;for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = dp[i][j - 1];		// 与1143不同的地方if (dp[i][j] > result) result = dp[i][j];}}return result == s.size() ? true : false;	// 与1143不同的地方}
};// 115、不同的子序列-动态规划
class Solution5 {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;		// 第一列初始化为1, dp[0][0]为1for (int j = 1; j <= t.size(); j++) dp[0][j] = 0;		// 第一行初始化为0, 可以省略for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];	else dp[i][j] = dp[i - 1][j];}}return dp[s.size()][t.size()];}
};int main() {//vector<int> nums1 = { 1, 2, 3, 2, 1 }, nums2 = { 3, 2, 1, 4, 7 };		// 测试案例//Solution s1;//int result = s1.findLength(nums1, nums2);//string text1 = "abcde", text2 = "ace";		// 测试案例//Solution2 s1;//int result = s1.longestCommonSubsequence(text1, text2);//vector<int> nums1 = { 1, 4, 2 }, nums2 = { 1, 2, 4 };		// 测试案例//Solution3 s1;//int result = s1.maxUncrossedLines(nums1, nums2);//string s = "abc", t = "ahbgdc";			// 测试案例//Solution4 s1;//int result = s1.isSubsequence(s, t);string s = "babgbag", t = "bag";		// 测试案例Solution5 s1;int result = s1.numDistinct(s, t);cout << result << endl;system("pause");return 0;
}

end