LeetCode动态规划经典题目（九）：子序列、子数组问题

目录

31. LeetCode674. 最长连续递增序列

32. LeetCode18. 最长重复子数组

33. LeetCode1143. 最长公共子序列

34. LeetCode1035. 不相交的线

35. LeetCode53. 最大子数组和

36. LeetCode392.判断子序列

37. LeetCode115. 不同的子序列

38. LeetCode583. 两个字符串的删除操作

39. LeetCode72. 编辑距离

---

思路：
1.dp含义：
dp[i]：集合nums从下标0到下标i并且以nums[i]结尾的最长递增子序列长度
(1)为什么能够以nums[i]结尾？因为每个递增子序列必定是以集合nums中的其中一个元素结尾。
(2)为什么一定要以nums[i]结尾？因为在递推时，我们需要与前一个递增子序列作比较，而只有知道尾元素大小才能有效地比较。
2.转移方程：
if(nums[j]<nums[i])dp[i]=max(dp[i],dp[j]+1);//j：0~(i-1)
3.初始化dp：
dp[0]=1;方法一：动态规划
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size()<=1)return nums.size();//dp[i]：集合nums从下标0到下标i并且以nums[i]结尾的最长递增子序列长度vector<int>dp(nums.size(),1);//基础长度是1int res=0;//完善dpfor(int i=1;i<nums.size();i++){for(int j=0;j<i;j++){if(nums[j]<nums[i])dp[i]=max(dp[i],dp[j]+1);//保留以nums[i]结尾最大长度}res=max(dp[i],res);//保留整体集合最长递增子序列长度}return res;}
};
时间复杂度：O(n^2)
空间复杂度：O(n)方法二：贪心+动态规划
ends[i]：所有长度为i+1的递增子序列的尾元素最小值，且ends[i]必定小于ends[i+1]
为什么ends[i]<ends[i+1]？设以ends[i]、ends[i+1]结尾的递增子序列分别为subSequence1（长度为i+1），subSequence2（长度为i+2），
假设ends[i]>ends[i+1]，即subSequence1[i]>subSequence2[i+1]，由于递增，
所以subSequence1[i]>subSequence2[i+1]>subSequence2[i] => subSequence1[i]>subSequence2[i]
则 ends[i]=subSequence2[i]，有矛盾，所以假设不成立。class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size()<=1)return nums.size();//ends[i]：所有长度为i+1的递增子序列的尾元素最小值，且ends[i]必定小于ends[i+1]vector<int>ends(nums.size());ends[0]=nums[0];int right=0;for(int i=1;i<nums.size();i++){//长度最长的递增子序列尾元素小于nums[i]，有效区域右移，并记录最小尾元素if(ends[right]<nums[i]){ends[++right]=nums[i];}else{int l=0;while(l<right&&ends[l]<nums[i]){//找到ends最左边比nums[i]大的尾元素l++;}//退出循环有两种情况，只有第二种情况才能赋值if(ends[l]>nums[i])ends[l]=nums[i];}}//ends[right]是"长度为right+1"的递增子序列的最小尾元素return right+1;}
};
时间复杂度：O(n*logn)
空间复杂度：O(n)

31. LeetCode674. 最长连续递增序列

1.dp[i]：以nums[i]结尾的连续递增序列长度
2.if(nums[i]>nums[i-1])dp[i]=dp[i-1]+1：因为是连续的，所以只需要考虑nums[i]是否比nums[i-1]大就行了（贪心）
3.初始化dp：全都初始化成1，因为至少包含nums[i]动态规划：
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if(nums.size()<=1)return nums.size();//dp[i]：以nums[i]结尾的连续递增序列长度vector<int>dp(nums.size(),1);int res=INT_MIN;//完善dpfor(int i=1;i<nums.size();i++){if(nums[i]>nums[i-1])dp[i]=dp[i-1]+1;res=max(res,dp[i]);//记录最长连续递增序列长度}return res;}
};贪心：
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if(nums.size()<=1)return nums.size();int count=1;//记录过程中个递增序列长度int res=INT_MIN;//记录最长递增序列长度for(int i=1;i<nums.size();i++){if(nums[i]>nums[i-1])count++;else count=1;//重新取递增序列头元素res=max(res,count);}return res;}
};与前一题的区别是：
本题dp[i]状态之和dp[i-1]有关，因为是连续的。
而前一题因为是不连续的，所以dp[i]状态和dp[0]/dp[1]/.../dp[i-1]都有关系

32. LeetCode18. 最长重复子数组

1.dp[i][j]：以nums1[i]结尾的nums1和以nums2[j]结尾的nums2的重复子数组长度
2.if(nums1[i]==nums[j])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=0;
3.初始化dp普通动态规划二维表：
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {//长度是1，看唯一元素是否相同if(nums1.size()==1&&nums2.size()==1)return nums1[0]==nums2[0]?1:0;//dp[i][j]：以nums1[i]结尾的nums1和以nums2[j]结尾的nums2的重复子数组长度vector<vector<int>>dp(nums1.size(),vector<int>(nums2.size()));//记录最长重复子数组长度int res=0;//初始化dpfor(int i=0;i<nums1.size();i++){if(nums1[i]==nums2[0])dp[i][0]=1;res=max(res,dp[i][0]);}for(int j=0;j<nums2.size();j++){if(nums2[j]==nums1[0])dp[0][j]=1;res=max(res,dp[0][j]);}//完善dpfor(int i=1;i<nums1.size();i++){for(int j=1;j<nums2.size();j++){if(nums1[i]==nums2[j]){dp[i][j]=dp[i-1][j-1]+1;}else{//如果nums1[i]!=nums2[j]，那必不可能重复，因为子数组一定要包含nums1[i]和nums2[j]dp[i][j]=0;}res=max(res,dp[i][j]);}}return res;}
};观察上方代码，发现不仅要额外判断数组长度为1时的情况，还要在初始化dp时更新res，代码略显臃肿。
再看转移方程，我们可以多一行一列，基础值为0，但也因此有额外空间开销
1.dp[i][j]：以nums1[i-1]结尾的nums1和以nums2[j-1]结尾的nums2的重复子数组长度
2.if(nums1[i]==nums[j])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=0;
3.初始化dp
改良动态规划二维表（代码行数更少）：
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {//dp[i][j]：以nums1[i-1]结尾的nums1和以nums2[j-1]结尾的nums2的重复子数组长度vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1));//记录最长重复子数组长度int res=0;//完善dpfor(int i=1;i<nums1.size()+1;i++){for(int j=1;j<nums2.size()+1;j++){if(nums1[i-1]==nums2[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=0;res=max(res,dp[i][j]);}}return res;}
};滚动数组：
观察转移方程，dp是一行一行更新，并且是从左到右
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<int>dp(nums2.size()+1);int res=0;for(int i=1;i<nums1.size()+1;i++){for(int j=nums2.size();j>=1;j--){//滚动数组应当优先更新那些不用来递推其他dp值的if(nums1[i-1]==nums2[j-1])dp[j]=dp[j-1]+1;else dp[j]=0;res=max(res,dp[j]);}}return res;}
};总结：
实现出动态规划二维表后，观察转移方程，看是否能够利用滚动数组实现，一般来说一行一行遍历的都可以转成一维数组。

33. LeetCode1143. 最长公共子序列

1.dp[i][j]：text1[0,i-1]和text2[0,j-1]的最长公共子序列长度
2.if(text[i]==text[j])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);class Solution {
public:int longestCommonSubsequence(string text1, string text2) {//dp[i][j]：text1[0,i-1]和text2[0,j-1]的最长公共子序列长度vector<vector<int>>dp(text1.length()+1,vector<int>(text2.length()+1));//完善dpfor(int i=1;i<text1.length()+1;i++){for(int j=1;j<text2.length()+1;j++){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{//text1[i-1]!=text2[j-1]//1.text1[i-2]和text[j-1]比较//2.text1[i-1]和text[j-2]比较//上述两种情况已经涵盖了所有可能性：text1[i-2]子序列涵盖了text1[i-3]所有子序列//text1[i-1]和text2[j-1]是新出现的字符，所以必须带着dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//记忆化搜索}}}return dp[text1.length()][text2.length()];}
};

34. LeetCode1035. 不相交的线

思路：
线只要在连接nums1和nums2的元素时按照相对同样的顺序就不会相交，所以本质上是求nums1和nums2最长公共子序列长度。1.dp[i][j]：nums1[0,i-1]和nums2[0,j-1]的公共子序列长度
2.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]);class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {//dp[i][j]：nums1[0,i-1]和nums2[0,j-1]的公共子序列长度vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1));//完善dpfor(int i=1;i<nums1.size()+1;i++){for(int j=1;j<nums2.size()+1;j++){if(nums1[i-1]==nums2[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}return dp[nums1.size()][nums2.size()];}
};

35. LeetCode53. 最大子数组和

1.dp[i]：以nums[i-1]结尾的最大子数组和
2.if(dp[i-1]>0)dp[i]=dp[i-1]+nums[i];else dp[i]=nums[i-1];class Solution {
public:int maxSubArray(vector<int>& nums) {//dp[i]：以nums[i]结尾的最大子数组和vector<int>dp(nums.size()+1);int res=INT_MIN;//完善dpfor(int i=1;i<nums.size()+1;i++){//只有前面子数组和为正，才对自己有帮助，才能够获取最大子数组和if(dp[i-1]>0)dp[i]=dp[i-1]+nums[i-1];else dp[i]=nums[i-1];res=max(res,dp[i]);}return res;}
};dp[i]只与dp[i-1]有关，与dp[i-1]前的元素都无关，所以我们只需一个值即可
class Solution {
public:int maxSubArray(vector<int>& nums) {int cur=0;int res=INT_MIN;for(int i=0;i<nums.size();i++){if(cur>=0){cur=cur+nums[i];}else{//cur<0，只会减少后续子数组和cur=nums[i];}res=max(res,cur);}return res;}
};

36. LeetCode392.判断子序列

1.dp含义：
dp[i][j]：以s[i-1]结尾的字符串s，和以t[j-1]结尾的字符串t，相同子序列长度
注意：是判断s是否为t的子序列，所以t.length()>=s.length()；s一定要包含s[i-1]，t不一定要包含t[j-1]2.转移方程：
只需要考虑删除字符串t的元素即可
if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;//t中新出现的字符能够和s[i-1]匹配
else dp[i][j]=dp[i][j-1];//无法匹配，t删除元素，继续匹配，然前一个字符去处理3.初始化dp：
//初始化二维数组dp时就已经完成了
dp[0][j]=0;
dp[i][0]=0;4.遍历顺序：
dp值从左上角递推而得
i：从上到下
j：从左至右class Solution {
public:bool isSubsequence(string s, string t) {//dp[i][j]：以s[i-1]结尾的字符串s，和以t[j-1]结尾的字符串t，相同子序列长度vector<vector<int>>dp(s.length()+1,vector<int>(t.length()+1));//完善dpfor(int i=1;i<s.length()+1;i++){for(int j=i;j<t.length()+1;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];}}return dp[s.length()][t.length()]==s.length();}
};双指针法：
创建两个索引指针sIndex、tIndex分别指向s和t，如果t[tIndex]==s[sIndex]，那么两根指针同时后移；否则tIndex后移，直到sIndex扫完s
，恰好也符合子序列顺序。
class Solution {
public:bool isSubsequence(string s, string t) {int sIndex=0;//指向s字符的指针int tIndex=0;//指向t字符的指针while(sIndex<s.length()&&tIndex<t.length()){if(s[sIndex]==t[tIndex]){sIndex++;tIndex++;}else{tIndex++;}}//sIndex扫过的区域都是在t中以同样的顺序出现过的return sIndex==s.length();}
};

37. LeetCode115. 不同的子序列

解读题意：从s中可以找出几个子序列恰好和t相同。s如何删除元素可以变成t
1.dp含义：
dp[i][j]：以s[i-1]结尾的字符串s中，以t[j-1]结尾的字符串t个数2.转移方程：
只有出现新字符时（下一轮循环）才会有未考虑的情况，对于新出现字符只有两种考虑（使用或不使用）
if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j];//s[i-1]可使用也可不使用(模拟删除)，两种情况总和。t无法删除元素
else dp[i][j]=dp[i-1][j];//不匹配，不用考虑s[i-1]3.初始化dp：
dp[0][j]=0;
dp[i][0]=1;
dp[0][0]=1;4.遍历顺序：
i：从上到下
j：从左到右class Solution {
public:int numDistinct(string s, string t) {//dp[i][j]：以s[i-1]结尾的字符串s中，以j[i-1]结尾的字符串t个数vector<vector<uint64_t>>dp(s.length()+1,vector<uint64_t>(t.length()+1));//初始化dpfor(int i=0;i<s.length()+1;i++){dp[i][0]=1;}for(int j=1;j<t.length()+1;j++){dp[0][j]=0;}//完善dpfor(int i=1;i<s.length()+1;i++){for(int j=1;j<t.length()+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];}}return dp[s.length()][t.length()];}
};

38. LeetCode583. 两个字符串的删除操作

思路：
二维数组，因为需要操作两个字符串1.dp含义：
dp[i][j]：让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数
2.转移方程：
对于新字符word1[i-1]和word2[j-1]只有相同和不相同两种情况
if(word1[i-1]==word[j-1])dp[i][j]=dp[i-1][j-1];//保留这两字符可以减少两步删除操作
else dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2);//二者选一个删除或都删除，取最小操作数
3.遍历顺序：
i：从上到下
j：从左到右
4.初始化dp：
dp[0][j]=j;//word1是空字符，word2必须删掉所有字符才能相同
dp[i][0]=i;class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]：让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数vector<vector<int>>dp(word1.length()+1,vector<int>(word2.length()+1));//初始化dpfor(int i=0;i<=word1.length();i++){dp[i][0]=i;}for(int j=0;j<=word2.length();j++){dp[0][j]=j;}//完善dpfor(int i=1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];else dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+2));}}return dp[word1.length()][word2.length()];}
};也可以求最长公共子序列长度，然后经过计算得出结果。

39. LeetCode72. 编辑距离

思路：
虽然题目说让word1变成word2，但也可以让word2变成word1。因为删除word1的字符，等效于在word2中添加字符，所以删除操作包含了添加操作1.dp含义：
dp[i][j]：让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数
2.转移方程：
if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];
else{dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//删除，这二者已经包含了dp[i-1][j-1]+2dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);//替换
}
3.遍历顺序：
i：从上到下
j：从左到右
4.初始化dp：
dp[0][j]=j;
dp[i][0]=i;class Solution {
public:int minDistance(string word1, string word2) {//dp[i][j]：让以word1[i-1]结尾的字符串word1和以word2[j-1]结尾的字符串word2相同的最少操作数vector<vector<int>>dp(word1.length()+1,vector<int>(word2.length()+1));//初始化dpfor(int i=0;i<=word1.length();i++){dp[i][0]=i;}for(int j=0;j<=word2.length();j++){dp[0][j]=j;}//完善dpfor(int i=1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];else{dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//删除，这二者已经包含了dp[i-1][j-1]+2dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);//替换}}}return dp[word1.length()][word2.length()];}
};