我要评论
算法沉淀 —— 动态规划（子序列问题（上））
前言
几乎所有的动态规划问题大致可分为以下5个步骤，后续所有问题分析都将基于此
-
1.、状态表示：通常状态表示分为以下两种，其中更是第一种为主。
以i为结尾，dp[i] 表示什么，通常为代求问题（具体依题目而定）以i为开始，dp[i]表示什么，通常为代求问题（具体依题目而定）
-
2、状态转移方程
- 以上述的dp[i]意义为根据， 通过
最近一步来分析和划分问题，由此来得到一个有关dp[i]的状态转移方程。
- 以上述的dp[i]意义为根据， 通过
-
3、dp表创建，初始化
- 动态规划问题中，如果直接使用状态转移方程通常会伴随着
越界访问等风险，所以一般需要初始化。而初始化最重要的两个注意事项便是：保证后续结果正确，不受初始值影响；下标的映射关系。 - 而
初始化一般分为以下两种：直接初始化开头的几个值。一维空间大小+1，下标从1开始；二维增加一行/一列。
- 动态规划问题中，如果直接使用状态转移方程通常会伴随着
-
4、填dp表、填表顺序：根据状态转移方程来确定填表顺序。
-
5、确定返回值
一、最长递增子序列
【题目链接】：300. 最长递增子序列
【题目】：
【示例】：
【分析】：
我们可以定义dp[i]表示以i位置为结尾的最长递增子序列。由于每一个数字均可单独构成一个递增子序列，所以我们在创建dp表时，可以将dp表中的值全部初始化为1.
状态转移方程推导:
如果dp[i]所表示的递增子序列大于1，此时在i之前一定存在某些元素和nums[i]构成递增子序列。而这些元素我们可以用dp[j[表示（0 <= j <i）,并且nums[j] < nums[i]。
但j到底在什么位置呢？我们无从而知，需要依次遍历i前的数据。来查找符合要求的最大dp[j]。所以状态转移方程为：
for(int j = i - 1; j >= 0; j--)
{
if(nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
【其他】：
最后只需将dp[i]的最终值累加即可！！
【代码编写】：
class solution {
public:
int lengthoflis(vector<int>& nums) {
int n = nums.size();
int ret = 1;
vector<int> dp(n, 1);
for(int i = 1; i < n; i++)
{
for(int j = i - 1; j >= 0; j--)
{
if(nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
ret = max(dp[i], ret);
}
return ret;
}
};
二、摆动序列
【题目链接】：376. 摆动序列
【题目】：
【分析】：
我们可以定义dp[i]表示以i位置为结尾的最大摆动序列。但我们发现i位置的状态还可以细分为上升和下降。所以我们重新定义:
- f[i]表示以i位置为结尾，且最后呈 ”上升“ 趋势的最大摆动序列。
- g[i]表示以i位置为结尾，且最后呈 ”趋势“ 的最大摆动序列。
状态转移方程推导:
- f[i]：最大摆动序列的长度可能为1，也可能大于1。对于大于1的情况，由于f[i]表示最后位置是呈上升趋势的摆动序列，所以
nums[i] > nums[i - 1]。此时在i-1位置一定是呈下降的，即g[i-1]。所以状态转移方程如下：
- 对于g[i]来说，同理可得状态转移方程如下：
细节处理：
不管是f表还是g表，以i位置为结尾的摆动序列的最小长度一定为1，即nums[i]本身。所以我们可以直接将f表和g表中的数据的初始值设为1。后续填表过程中，仅需考虑长度大于1的情况即可！！
【代码编写】：
class solution {
public:
int wigglemaxlength(vector<int>& nums) {
int n = nums.size(), ret = 1;
vector<int> f(n, 1), g(n, 1);
for(int i = 1; i < n ; i++)
{
for(int j = i - 1; j >= 0; 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;
}
};
三、 最长递增子序列的个数
【题目链接】：673. 最长递增子序列的个数
【题目】：
【示例】：
【分析】：
我们先定义dp[i]表示以i位置为结尾的最长递增子序列的个数。但我们发现dp[i]表示两个状态：最长递增、个数。所以我们需要将dp[i]状态细分：
- 我们定义len[i]表示以i位置为结尾的最长递增子序列的长度。
- 定义count[i]表示以i位置为结尾的最长递增子序列的个数。
显然len[i]、count[i]最小为1，即nums[i]本身单独构成一个递增子序列。所以我们在创建len表和count表时，我们可以将初始值设为1。
如果最大递增子序列长度大于1时，这也意味着在i前就已经存在一个递增子序列（设该子序列以j下标为结尾）。并且满足nums[i] > nums[j]，此时该递增子序列（以j下标结尾，0 <= j < i）和nums[i]构成了一个新的递增子序列。
如果最长递增子序列大于1，此时最终结果不仅要保证nums[i] > nums[j]，还需保证以j位置结尾的子序列最大（即len[j]在0 ~ i-1中最大）。所以我们需要依次遍历0 ~ i-1之间len表中的左右值！！
那count[i]的值如何更新呢？
我们可以在求len[i]的过程中，更新count[i]的值。具体如下：
- 如果
len[i] + 1 == len[j]，此时count[i] += count[j]。 - 如果
len[i] + 1 > len[j]，此时len[i]和count[i]的需要重新更新。即len[i] = len[j] + 1, count[i] = count[j] - 如果
len[i] + 1 < len[j]，此时count[j]是无效次数。我们直接忽略这种情况。
细节处理：
通过上述过程我们可以的以i位置为结尾的最大递增序列和次数。所以最终整个数组中，构成的最大递增序列的次数求解可以采用和上述类型的思想。（具体查看代码）
【代码编写】：
class solution {
public:
int findnumberoflis(vector<int>& nums) {
int n = nums.size();
vector<int> len(n, 1), count(n, 1);
int maxlen = 1, maxcount = 1;
for(int i = 1; i < n; i++)
{
for(int j = i - 1; j >= 0; j--)
{
if(nums[i] > nums[j])
{
if(len[j] + 1 == len[i])
count[i] += count[j];
else if(len[j] + 1 > len[i])
len[i] = len[j] + 1, count[i] = count[j];
}
}
if(len[i] == maxlen)
maxcount += count[i];
else if(len[i] >maxlen)
maxlen = len[i], maxcount = count[i];
}
return maxcount;
}
};
四、最长数对链
【题目链接】：646. 最长数对链
【题目】：
【分析】：
由于题目中明确表示可以任意选择数组中的数来构造数对链。所以我们可以先对数组进行排序。此时我们可以定义dp[i[表示以i位置为结尾的最长数对链。
状态转移方程推导分析:
显然dp[i]的最小值为1，即[pair[i][0], pair[i][1]]本身构成数对链。
如果以i位置为结尾的数对链的长度大于1，此时i位置之前一定存在数对链（下标设为j，0 <= j <i）和当前元素构成一个数对链。该情况的出现需满足pairs[i][0] > pairs[j][1]。但我们最终的结果是要得到dp[j]中的最大值。我们可以直接从后往前遍历，只要查找到第一个满足条件的dp[j]即可。（原因在于我们已经对原数组进行排序）
所以状态转移方程为:
for(int j = i -1; j >= 0; j--)
{
if(pairs[i][0] > pairs[j][1])
{
dp[i] = max(dp[i], dp[j] + 1);
break;
}
}
【代码编写】：
class solution {
public:
int findlongestchain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end());
int n = pairs.size(), ret = 1;
vector<int> dp(n, 1);
for(int i = 1; i < n; i++)
{
for(int j = i -1; j >= 0; j--)
{
if(pairs[i][0] > pairs[j][1])
{
dp[i] = max(dp[i], dp[j] + 1);
break;
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};
发表评论