【序列DP】最长递增子序列的个数 / 最长定差子序列 / 等差数列划分 II - 子序列
【序列DP】最长递增子序列的个数 / 最长定差子序列 / 等差数列划分 II - 子序列
子序列vs子数组：
- 子序列：不连续，顺序不变，适合动态规划问题；
- 子数组：连续，顺序不变，适合滑动窗口或 Kadane 算法。
最长递增子序列
dp[i] 表示以i位置的元素为 开头 的所有子序列中，最长递增子序列的长度。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size(), ret = 0;;
vector<int> dp(n, 1);
for (int i = n - 1; i >= 0; i--)
{
for (int j = i + 1; j < n; j++)
{
if (nums[j] > nums[i])
dp[i] = max(dp[i], dp[j] + 1);
}
ret = max(ret, dp[i]);
}
return ret;
}
};dp[i] 表示以i位置的元素为 结尾 的所有子序列中，最长递增子序列的长度。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size(), ret = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
if (nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
ret = max(ret, dp[i]);
}
return ret;
}
};摆动序列
定义状态表示：f[i] 为以i位置元素为结尾的所有子序列中，最后呈 “上升” 状态的最长子序列的长度；g[i] 为以i位置元素为结尾的所有子序列中，最后呈 “下降” 状态的最长子序列的长度。
固定某个位置为i，让j在[0, i-1]中搜索，当nums[j]>nums[i]时呈现下降状态，则g[i] = max(f[j] + 1, g[i])。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
vector<int> f(n, 1), g(n, 1);
int ret = 1;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (nums[i] > nums[j]) f[i] = max(g[j] + 1, f[i]);
else if (nums[i] < nums[j]) g[i] = max(f[j] + 1, g[i]);
}
ret = max(ret, max(f[i], g[i]));
}
return ret;
}
};最长递增子序列的个数 *
定义状态 len[i] 为以i位置元素为结尾的最长递增子序列的长度，count[i] 为以i位置元素为结尾的最长子序列出现的个数。
统计出i位置的len[i]和count[i]后，如果最长长度不变，则增加之前的技术；如果变长，则刷新最长子序列出现的个数；如果变短，则不用处理。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> len(n, 1), count(n, 1);
int retlen = 1, retcount = 1;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (nums[j] < nums[i])
{
if (len[i] == len[j] + 1) count[i] += count[j];
else if (len[i] < len[j] + 1)
{
count[i] = count[j];
len[i] = len[j] + 1;
}
}
}
if (retlen == len[i]) retcount += count[i];
else if (retlen < len[i])
{
retlen = len[i];
retcount = count[i];
}
}
return retcount;
}
};最长数对链
定义状态 dp[i] 表示以i位置元素为结尾的所有数对列中的最长长度，对于dp[i] ，遍历所有[0, i - 1] 区间内数对用j 表示下标，找出所有满足pairs[j][1] < pairs[i][0] 的j ，找出其中最大的dp[j] ，然后加上1 ，就是以i 位置为结尾的最长数对链。
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end());
int n = pairs.size();
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[j] + 1, dp[i]);
}
ret = max(ret, dp[i]);
}
return ret;
}
};最长定差子序列
定义状态 dp[i] 表示以i 位置的元素为结尾所有的子序列中，最长的等差子序列的长度。 对于dp[i] ，上一个定差子序列的取值定为arr[i] - difference 。只要找到以上一个数 字为结尾的定差子序列长度的dp[arr[i] - difference] ，然后加上1 ，就是以i 为结尾的定差子序列的长度。因此，这里可以选择使用哈希表做优化。我们可以把「元素， dp[j] 」绑定，放进哈希表中。甚至不用创建dp 数组，直接在哈希表中做动态规划。
class Solution {
public:
int longestSubsequence(vector<int>& arr, int d) {
unordered_map<int, int> hash;
hash[arr[0]] = 1;
int ret = 1;
for (int i = 1; i < arr.size(); i++)
{
hash[arr[i]] = hash[arr[i] - d] + 1;
ret = max(ret, hash[arr[i]]);
}
return ret;
}
};最长的斐波那契子序列的长度
定义状态 dp[i][j] 表示以i、j位置元素为结尾的所有子序列中，最长的斐波那契子序列的长度。
则构成斐波那契序列的条件为：arr[j] - arr[i] 的值在数组中存在，并且其位置在j前面。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
unordered_map<int, int> hash;
// 将元素和其下标绑定
for (int i = 0; i < n; i++) hash[arr[i]] = i;
vector<vector<int>> dp(n, vector<int>(n, 2));
int ret = 2;
for (int i = 2; i < n; i++)
{
for (int j = 1; j < i; j++)
{
int k = arr[i] - arr[j];
if (k < arr[j] && hash.count(k))
dp[j][i] = dp[hash[k]][j] + 1;
ret = max(ret, dp[j][i]);
}
}
return ret < 3 ? 0 : ret;
}
};最长等差数列
定义状态 dp[i][j] 表示以i、j位置为结尾的所有子序列中，最长等差子序列的长度。
用哈希表，一遍遍历一遍填表，可以节省时间。
class Solution {
public:
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 a = 2 * nums[i] - nums[j];
if (hash.count(a))
dp[i][j] = dp[hash[a]][i] + 1;
ret = max(ret, dp[i][j]);
}
hash[nums[i]] = i;
}
return ret;
}
};等差数列划分 II - 子序列 *
定义状态 dp[i][j] 表示以i、j位置元素为结尾的所有组序列中，等差子序列的个数。
之所以用两个维度进行状态表示，是因为等差子序列我们需要知道其中的两个元素才能推出第三个元素。
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
unordered_map<long, vector<int>> hash;
for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);
vector<vector<int>> dp(n, vector<int>(n));
int ret = 0;
for (int i = 2; i < n; i++)
{
for (int j = 1; j < i; j++)
{
long k = (long)2 * nums[j] - nums[i];
for (int e : hash[k])
{
if (e < j) dp[j][i] += dp[e][j] + 1;
}
ret += dp[j][i];
}
}
return ret;
}
};本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
腾讯云开发者
