04子序列问题
# 04 子序列问题
对于子序列问题，第一种动态规划方法是，定义一个 dp 数组，其中 dp[i]表示以 i 结尾的子序列的性质。在处理好每个位置后，统计一遍各个位置的结果即可得到题目要求的结果。第二种动态规划方法是，定义一个 dp数组，其中 dp[i] 表示到位置 i 为止的子序列的性质，并不必须以 i 结尾。这样 dp 数组的最后一位结果即为题目所求，不需要再对每个位置进行统计。
# 300 最长递增子序列 (opens new window)
给定一个未排序的整数数组，求最长的递增子序列。
输入是一个一维数组，输出是一个正整数，表示最长递增子序列的长度。
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
解析:
设置状态：使用一个一维数组dp[i] 可以表示以 i 结尾的、最长子序列长度。
状态转移方程：对于每一个位置 i，如果其之前的某个位置 j 所对应的数字小于位置 i 所对应的数字，则可以获得一个以 i 结尾的、长度为 dp[j] + 1 的子序列，即dp[i] = max(dp[i],dp[j]+1)。为了遍历所有情况，我们需要 i 和 j 进行两层循环，并记录最大值。
初始情况：dp[0] = 0, dp[1] = 1
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
// 将所有位置初始化为 1, 因为len>=1,所以最短递增子序列就是 1
vector<int> dp(len,1);
int ans = 1;
// i 控制每一个记录位置
for(int i=1;i<len;++i){
// j 扫描 i 之前的子序列
for(int j=0;j<i;++j){
// 如果出现递增情况，判断是否增加的子序列长度
if(nums[i]>nums[j]){
dp[i] = max(dp[i],dp[j]+1);
}
}
// 完成一个位置的记录之后，判断是否是较大长度
ans = max(ans,dp[i]);
}
return ans;
}
};
# 646 最长数对链 (opens new window)
给出 n 个数对，在每一个数对中，第一个数字总是比第二个数字小。对于数对(a,b),(c,d)如果 b < c则这两个数对可以构成数对链
输入一个数对集合，输出一个整数表示能够形成的最长数对链的长度。
输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4]
解析:
本题和300题本质上是一样的，不同在于递增序列由数对构成。另外需要考虑数对出现的次序并不影响它是否能够加入数对链，所以在使用类似于300题的动态规划方法计算最长数对链长度之前需要对其进行排序，简化元素选择。本题中以区间（数对）结尾排序。
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
int len = pairs.size();
if(len < 1) return 0;
sort(pairs.begin(),pairs.end(),[](vector<int> a, vector<int> b){ return a[1]<b[1];});
vector<int> dp(len,1);
int ans = 1;
for(int i=1;i<len;++i){
for(int j=0;j<i;++j){
if(pairs[j][1]<pairs[i][0]){
dp[i] = max(dp[i],dp[j]+1);
}
}
ans = max(ans,dp[i]);
}
return ans;
}
};
# 376 摆动序列 (opens new window)
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
输入是一个一维数组，输出是一个正整数，表示作为摆动序列的最长子序列的长度。
输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
解析:
本题和递增子序列的差别在于摆动序列的元素选择取决于前一个被选元素的大小，既可以上升也可以下降。
设置状态：使用一个二维数组dp[i][j]表示前 i 个元素中的某一个为结尾的最长摆动序列长度，其中 j 取值为 0 和 1分别表示上升摆动序列和下降摆动序列。上升摆动序列是指最后一个元素是呈上升趋势的摆动序列，下降摆动序列同理。d[i][0]表示以前 i 个元素中的某一个为结尾的最长的上升摆动序列的长度；dp[i][1]以前 i 个元素中的某一个为结尾的最长的下降摆动序列的长度。
状态转移方程：考虑第 i 个元素，如果nums[i] > nums[i-1]，则该元素可以加入下降摆动序列形成上升摆动序列dp[i][0] = max(dp[i-1][0],dp[i-1][1] + 1)，但是该元素加入上升摆动序列并不会形成下降摆动序列dp[i][1] = dp[i-1][1]；如果nums[i] < nums[i-1]，则该元素可以加入上升摆动序列形成下降摆动序列dp[i][1] = max(dp[i-1][1],dp[i-1][0] + 1)，如果该元素加入下降摆动序列并不会形成上升摆动序列所以dp[i][0] = dp[i-1][0]；如果nums[i] == nums[i-1]那么可以直接跳过该元素dp[i][0] = dp[i-1][0], dp[i][1] = dp[i-1][1]。
初始情况：当只有一个元素时，该元素既是上升摆动序列也是下降摆动序列，dp[0][j] = 1;
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int len = nums.size();
if(len < 2) return len;
vector<vector<int>> dp(len,vector<int>(2,1));
int ans = 1;
for(int i=1;i<len;++i){
if(nums[i] < nums[i-1]){
dp[i][0] = dp[i-1][0];
dp[i][1] = max(dp[i-1][1],dp[i-1][0] + 1);
}else if(nums[i] > nums[i-1]){
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + 1);
dp[i][1] = dp[i-1][1];
}else{
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][1];
}
ans = max(ans,max(dp[i][0],dp[i][1]));
}
return ans;
}
};
本题也可以采用贪心策略解决，使用极值构成最长摆动序列。
# 1143 最长公共子序列 (opens new window)
给定两个字符串，求它们最长的公共子序列长度。
输入是两个字符串，输出是一个整数，表示它们满足题目条件的长度。
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
解析:
设置状态：建立一个二维数组 dp，其中 dp[i][j] 表示到第一个字符串位置 i 为止、到第二个字符串位置 j 为止、最长的公共子序列长度。
状态转移方程：从1开始计算字符串位置，那么当text1 的第 i 个字符与 text2 的第 j 个字符相等时，其最长公共子串长度为前一状态加1，即 dp[i][j] = dp[i-1][j-1] + 1；如果不相等，dp[i][j] 不会比dp[i-1][j] 和dp[i][j-1] 两者之中任何一个小，也不会比两者都大，即 dp[i][j] = max(dp[i-1][j],dp[i][j-1])
初始情况：任一个字符串为空串则最长公共子序列的长度都为0，即dp[0][j] = dp[i][0] = 0
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.length(), len2 = text2.length();
// 创建len+1行len2+1列的二维数组 dp，其中 dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度
vector<vector<int>> dp(len1+1,vector<int>(len2+1));
for(int i=1;i<=len1;++i){
for(int j=1;j<=len2;++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]);
}
}
}
return dp[len1][len2];
}
};
# 583 两个字符串的删除操作 (opens new window)
给定两个字符串，求它们通过删除操作变成相同的最小步骤。
输入是两个字符串，输出是一个整数，表示它们通过删除操作变成相同的最小步骤数。
输入: "sea", "eat" 输出: 2 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
解析:
本题是最长公共子序列的一种变种题，可以直接求出最长公共子序列后用较长一个字符串的长度减去最长公共子序列的长度。
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.length(), n = word2.length();
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(word1[i-1] == word2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
int LCS = dp[m][n];
return m+n-2*LCS;
}
};