动态规划：子序列问题
- 前言
- 子序列问题
- 1.最长递增子序列（中等）
- 2.摆动序列（中等）
- 3.最长递增子序列的个数（中等）
- 4.最长数对链（中等）
- 5.最长定差子序列（中等）
- 6.最长的斐波那契子序列的长度（中等）
- 7.最长等差序列（中等）
- 8.等差数列划分II – 子序列（困难）
前言
动态规划往期文章:
- 动态规划入门：斐波那契数列模型以及多状态
- 动态规划：路径和子数组问题
子序列问题
1.最长递增子序列（中等）
链接：最长递增子序列
-
题目描述
-
做题步骤
-
状态表示
对于线性dp，我们通常采用下面两种表示:
(1)以某个位置为结尾，……
(2)以某个位置为起点，……
这两种方式我们通常采用第一种，以某个位置为结尾，再结合题目要求，我们可以定义状态表示为dp[i]：以i位置为结尾的所有子序列中，最长递增子序列的长度。 -
状态转移方程
对于以i位置为结尾的子序列，一共有两种可能：
(1)不接在别人后面，就自己一个，dp[i] = 1
(2)接在[0，1，2，……，i – 1]这些位置后面，设0 <= j <= i – 1，能保持子序列递增（nums[j] < nums[i]）就可以接在该位置后面。
从0~i – 1枚举j，看接在那个位置后面长度最大：
即dp[i] = max(dp[i], dp[j] + 1) -
初始化
每个位置最小都为1，全都初始化为1。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序为从左往右。 -
返回值
没法直接确定最长子序列的结尾位置，一边dp一边更新最大值。
- 代码实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
//dp[i]表示以i位置为结尾的最长递增子序列
vector<int> dp(n, 1);
int ret = 1;
for(int i = 1; i < n; i++)
{
//从[0, i-1]看一圈，找接在那个符合条件的位置后面可以让子序列最长
for(int j = 0; j < i; j++)
if(nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
//看看能不能更新最大
ret = max(ret, dp[i]);
}
return ret;
//时间复杂度：O(N ^ 2)
//空间复杂度：O(N)
}
};
2.摆动序列（中等）
链接：摆动序列
-
题目描述
-
做题步骤
-
状态表示
依据前面的经验，我们依据可以定义状态表示为dp[i]：以i位置为结尾的所有摆动序列中的最大长度。 -
状态转移方程
对于长度大于1的摆动序列，其有两种情况：
(1)处于上升状态，比如(1, 7, 4, 9)。
(2)处于下降状态，比如(1, 17, 10)。
因此我们需要同时记录两种状态，其中f[i]表示以i位置为结尾并处于上升状态的最长摆动序列长度，g[i]表示处于下降状态。
摆动序列分析完了，我们再来分析单个位置，一共有两种可能：
(1)不接在别人后面，自己玩，dp[i] = 1
(2)接在[0，1，2，……，i – 1]这些位置后面，设0 <= j <= i – 1。
①如果接在j位置后处于上升状态(nums[i] – nums[j] > 0)，需要以j位置为结尾并处于下降状态的状态，即f[i] = g[j] + 1。
②如果接在j位置后处于下降状态(nums[i] – nums[j] < 0)，需要以j位置为结尾并处于上升状态的状态，即g[i] = f[j] + 1。 -
初始化
序列长度最小为1，所有位置全都初始化为1。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序为从左往右。 -
返回值
没法直接确定最长摆动序列的结尾，所以一边dp一边更新最大值。
- 代码实现
class Solution {
public:
int wiggleMaxLength(vector<int>& nums)
{
//dp[i]表示以i位置为结尾的最长摆动序列长度
int n = nums.size();
vector<int> f(n, 1);//处于上升状态
vector<int> g(n, 1); //处于下降状态
int ret = f[0]; //记录最终结果
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
int gap = nums[i] - nums[j];
//处于上升
if(gap > 0)
f[i] = max(f[i], g[j] + 1);
//处于下降
else if(gap < 0)
g[i] = max(g[i], f[j] + 1);
//相同的情况为1不用处理
}
ret = max({ret, f[i], g[i]});
}
return ret;
//时间复杂度：O(N ^ 2)
//空间复杂度：O(N)
}
};
3.最长递增子序列的个数（中等）
链接：最长递增子序列的个数
-
题目描述
-
做题步骤
-
状态表示
依据前面的经验，我们可以定义状态表示dp[i]：以i位置为结尾的最长递增子序列个数。 -
状态转移方程
要更新当前位置的最长递增子序列个数，无非是看接在那几个位置后面长度最大，但问题就在于现在只有前面位置的序列个数，没有长度，所以我们需要再加一个表来记录长度：
(1)count[i]：以i位置为结尾的最长递增子序列个数
(2)len[i]：以i位置为结尾的最长递增子序列长度
len[i]前面已经讲过，我们分析count[i]：
(1)不接在别人后面，最大长度就为1，count[i] = 1
(2)接在[0，1，2，……，i – 1]这些位置后面，设0 <= j <= i – 1，能保持子序列递增（nums[j] < nums[i]）就可以接在该位置后面。
从0~i – 1枚举j，依据接在那个位置后面的长度进行分析：
①比原来长度小(len[i] > len[j] + 1)，不用管。
②比原来长度大(len[i] < len[j] + 1)，原来的序列个数无论多少都必须狠狠切割了，个数更新为更长的，即count[i] = count[j]。
③和原来长度一样(len[i] == len[j] + 1)，计数增加，即count[i] += count[j]。 -
初始化
序列长度最小为1，全都初始化为1。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序为从左往右。 -
返回值
(1)完成了前面的工作，我们知道以每一个位置为结尾的最长递增子序列长度和个数，但是并不知道以那几个位置为结尾的序列最长，所以我们需要一边dp一边更新最大长度max_length。
(2)知道了最大长度，我们只需要遍历一次count表，把长度为max_length的序列统计出来即可。
- 代码实现
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> count(n, 1); //f[i]表示以i位置为结尾的最长子序列个数
auto len = count; //g[i]表示以i位置为结尾的最长递增子序列长度
int max_length = len[0];
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if(nums[i] > nums[j])
{
//找到了更加长的
if(len[i] < len[j] + 1)
{
len[i] = len[j] + 1;
count[i] = count[j];
}
else if(len[i] == len[j] + 1) //长度相同
count[i] += count[j];
}
}
max_length = max(max_length, len[i]);
}
int ret = 0; //返回值
//遍历一次，计算最长序列个数
for(int i = 0; i < n; i++)
if(len[i] == max_length)
ret += count[i];
return ret;
//时间复杂度：O(N ^ 2)
//空间复杂度：O(N)
}
};
4.最长数对链（中等）
链接：最长数对链
-
题目描述
-
做题步骤
-
状态表示
依据前面经验，我们定义状态表示dp[i]：以i位置为结尾最长数对链长度。 -
状态转移方程
这个题目的分析其实和前面的最长递增子序列基本一致。
(1)不接在别人后面，自己玩，dp[i] = 1
(2)接在[0，1，2，……，i – 1]这些位置后面，设0 <= j <= i – 1，满足数对链要求（pairs[j][1] < pairs[i][0]）就可以接在该位置后面。
从0~i – 1枚举j，看接在那个位置后面长度最大：
即dp[i] = max(dp[i], dp[j] + 1) -
初始化
长度最小为1，全都初始化为1。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序为从左往右。 -
返回值
没法直接确定最长数对链的结尾，所以一边dp一边更新最大值。
- 代码实现
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end()); //先排序
int n = pairs.size();
//dp[i]表示以i位置为终点的最长长度
vector<int> dp(n, 1);
int ret = 1; //记录最长
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
if(pairs[j][1] < pairs[i][0]) //如果可以接在后面
dp[i] = max(dp[i], dp[j] + 1);
ret = max(ret, dp[i]);
}
return ret;
//时间复杂度：O(N ^ 2)
//空间复杂度：O(N)
}
};
5.最长定差子序列（中等）
链接：最长定差子序列
-
题目描述
-
做题步骤
-
状态表示
依据前面的经验，我们定义状态表示dp[i]：以下标i位置为结尾的最长等差子序列长度。 -
状态转移方程
这个题目最好想的做法就是递增子序列的做法，但这样写会超时，我们可以分析一下原因：
(1)递增子序列可以接在很多位置的后面。
(2)等差子序列只能接在固定的位置后面，比如(1, 2, 3, 4)，difference为1，里面的4只能接在3后面，其它的判断都是多余的。
那我们就换一种思路，还是(1, 2, 3, 4)，difference为1这个例子，我们在填4位置的时候，如果能够直接找到以3(arr[i] – difference)为结尾的最长递增子序列就好了。
我们可以把元素arr[i]与dp[i]绑定，创建一个哈希表hash，我们可以直接在这个哈希表中做动态规划，那状态转移方程就为：
hash[i] = hash[arr[i] – difference] + 1。 -
初始化
在填表的时候，如果前置状态不存在，我们不单独处理(0加1变成1刚好对应自己一个的情况)。因此我们只需要把第⼀个元素放进哈希表中， hash[arr[0]] = 1即可。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序为从左往右。 -
返回值
不确定最长等差子序列的结尾，所以一边dp一边更新最大值。
- 代码实现
class Solution
{
public:
int longestSubsequence(vector<int>& arr, int difference)
{
// 创建⼀个哈希表
unordered_map<int, int> hash; // {arr[i], dp[i]}
hash[arr[0]] = 1; // 初始化
int ret = 1;
for(int i = 1; i < arr.size(); i++)
{
hash[arr[i]] = hash[arr[i] - difference] + 1;
ret = max(ret, hash[arr[i]]);
}
return ret;
//时间复杂度：O(N)
//空间复杂度：O(N)
}
};
6.最长的斐波那契子序列的长度（中等）
链接：最长的斐波那契子序列的长度
-
题目描述
-
做题步骤
-
状态表示
依据经验我们可能会定义状态表示为以i位置为结尾的最长斐波那契序列的长度，但这样定义有一个致命的问题：不知道接在某一个位置后能否构成斐波那契序列。
一个元素无法确定，但如果我们知道斐波那契序列的后两个元素，我们就可以推导出前一个元素，从而解决前面的问题。
所以定义一个二维表dp[i][j]：以i，j位置为后两个元素的最长斐波那契序列的长度。 -
状态转移方程
规定 i 比 j 小，其中j从[2, n – 1]开始枚举，i从[1, j – 1]开始枚举。
设 nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是 a = c – b ，我们根据 a 的情况讨论：
(1)a存在，设其下标为k，并且 a < b，这个时候c可以接在以a、b为结尾的斐波那契序列后面，则dp[i][j] = dp[k][i] + 1。
(2)a存在，但是 b < a < c，这个时候只能b和c两个自己构成，dp[i][j] = 2。
(3)a不存在，这个时候只能b和c两个自己构成，dp[i][j] = 2。
我们发现，在状态转移⽅程中，我们需要确定 a 元素的下标。因此我们可以在 dp 之前，将所有的「元素 + 下标」绑定在⼀起，放到哈希表中。 -
初始化
长度最小为2，全都初始化为2。 -
填表顺序
固定最后一个数，枚举倒数第二个数。 -
返回值
不确定最长斐波那契子序列的结尾，所以一边dp一边更新最大值。
- 代码实现
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr)
{
int n = arr.size();
//i->j
dp[i][j]表示以i,j为后两个的斐波那契数列最长长度
vector<vector<int>> dp(n, vector<int>(n, 2));
unordered_map<int, int> hash;
for(int i = 0; i < n; i++) hash[arr[i]] = i;
int ret = 2;
for (int j = 2; j < n; j++)
{
for (int i = 1; i < j; i++)
{
int former = arr[j] - arr[i];
//a b c，a < b 并且a存在
if (former < arr[i] && hash.count(former))
{
dp[i][j] = dp[hash[former]][i] + 1;
}
ret = max(ret, dp[i][j]);
}
}
//斐波那契序列最小为3，为2的情况返回0
return ret > 2 ? ret : 0;
//时间复杂度：O(N)
//空间复杂度：O(N ^ 2)
}
};
7.最长等差序列（中等）
链接：最长等差序列
-
题目描述
-
做题步骤
-
状态表示
和前面一道题类似，只有一个元素无法确定等差序列的样子，我们需要有后面两个元素才能确定，故定义一个二维表dp[i][j]：以i，j为后两个元素的最长等差子序列的长度。 -
状态转移方程
规定 i 比 j 小，设 nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是 a = 2 * nums[i] – nums[j] (等差序列的性质捏) ，我们根据 a 的情况讨论：
(1)a存在，设其下标为k，这个时候c可以接在以a、b为结尾的序列后面，则dp[i][j] = dp[k][i] + 1。
(2)a不存在，这个时候只能b和c两个自己构成，dp[i][j] = 2。
我们发现，在状态转移方程中，我们需要确定 a 元素的下标。因此我们可以将所有的「元素 + 下标」绑定在⼀起，放到哈希表中。对于这个题目哈希表有两种方案：
(1)在dp前就直接放入哈希表，可能出现重复的元素（这个题目是乱序的，前面一题严格递增），要记录这些重复元素，需要让它们的下标形成一个数组，填表前要先遍历数组找到需要的下标，时间消耗很大，这个方案通过不了。
(2)只能采取一边dp一边存入哈希表的方式，在i位置使用完后存入哈希表中，但填表顺序必须固定倒数第二，枚举倒数第一，不能采用上一题固定倒一，枚举倒二的填表方式。我们看这个例子：【0，2，4，4，4，6，8，4，9，4，4】，最后一个4固定，第一个4为倒数第二时，应该去找之前4的下标（这里前面是[0,2],没有4，意味着这个数不应该在哈希表中，但固定倒一，枚举倒二的填表方式使得哈希表中是有保存的，这个时候就完全乱了） -
初始化
长度最小为2，全部初始化为2。 -
填表顺序
填表顺序为固定倒数第二，枚举倒数第一。 -
返回值
不确定最长等差序列的结尾，所以一边dp一边更新最大值。
- 代码实现
class Solution {
public:
//dp[i][j]表示以i，j为结尾的最长等差数列长度
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> hash;
hash[nums[0]] = 0;
vector<vector<int>> dp(n, vector<int>(n, 2));
int ret = 2;
for (int i = 1; i < n; i++) //倒数第二个
{
for (int j = i + 1; j < n; j++)
{
int former = 2 * nums[i] - nums[j];
if (hash.count(former))
dp[i][j] = dp[hash[former]][i] + 1;
ret = max(ret, dp[i][j]);
}
hash[nums[i]] = i;
}
return ret;
//时间复杂度：O（N ^ 2）
//空间复杂度：O（N ^ 2）
}
};
8.等差数列划分II – 子序列（困难）
链接：等差数列划分II – 子序列
-
题目描述
-
做题步骤
-
状态表示
和前面一道题一致，只有一个元素无法确定等差序列的样子，我们需要有后面两个元素才能确定，故定义一个二维表dp[i][j]：以i，j为后两个元素的等差子序列个数。 -
状态转移方程
首先，这个题目不存在重复的等差子序列，只要组成的元素位置不同就视为不同子序列，比如[7,7,7,7,7]这个数组等差子序列个数高达16个。
规定 i 比 j 小，设 nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是 a = 2 * nums[i] – nums[j] ，我们根据 a 的情况讨论：
(1)a存在，这个时候c可以接在以a、b为结尾的序列后面。设a下标为k，这里下标情况就和前面不同了，因为可能存在多个a，我们需要用一个下标数组来记录不同位置的a下标，当k < i时(a在i的前面)，dp[i][j] += dp[k][i] + 1，这里的+1表示[a,b,c]这一组，把满足条件的a全部加起来即可。
(2)a不存在，这个时候只能b和c两个自己构成，dp[i][j] = 2。
我们发现，在状态转移方程中，我们需要确定 a 元素的下标。因此我们可以将所有的「元素 + 下标数组」绑定在⼀起，放到哈希表中。 -
初始化
无需初始化，默认为0。 -
填表顺序
填表顺序为固定倒一，枚举倒二。 -
返回值
定义变量sum，一边dp一边累加。
- 代码实现
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
//dp[i][j]表示以i,j为结尾的等差数列个数，规定j > i
//前置可能有存在多个，需要一一加起来
vector<vector<int>> dp(n, vector<int>(n));
unordered_map<long long, vector<int>> hash; //数据和下标数组绑定
for(int i = 0; i < n; i++)
hash[nums[i]].push_back(i);
int sum = 0;
for(int j = 2; j < n; j++)
{
for(int i = 1; i < j; i++)
{
long long former = (long long)nums[i] * 2 - nums[j]; //处理数据溢出
if(hash.count(former))
{
for(auto k : hash[former])
{
//former必须在左边
if(k < i)
dp[i][j] += dp[k][i] + 1; //这里的1表示[a,b,c]单独一组
else //当前a下标不满足，后面的也一定不满足，可以直接跳出
break;
}
}
sum += dp[i][j];
}
}
return sum;
//相同数据不多的情况下
//时间复杂度：O(N ^ 2)
//空间复杂度：O(N ^ 2)
}
};
文章出处登录后可见！
