动态规划之子序列问题(上)
文章目录
- 最长递增子序列
- 摆动序列
- 最长递增子序列的个数
- 最长数对链
最长递增子序列
题目:最长递增子序列
思路
-
状态表示:
dp[i]
表示以i
位置为结尾的所有子序列中最长递增子序列的长度 -
状态转移方程:
- 长度为
1
,此时dp[i] = 1
- 长度大于
1
,对于i
前面的所有元素j(0 <= j < i - 1)
,我们考虑nums[j] < nums[i]
是否成立,如果成立,则说明i
位置和j
位置构成递增子序列,因为不清楚是哪个j
,所以我们统计其最大值dp[i] = max(dp[j] + 1, dp[i])
- 长度为
-
初始化:每个位置都可以构成长度为
1
的递增子序列,因此将dp
数组初始化为1
-
填表顺序:从左到右
-
返回值:
dp
表中的最大值
C++代码
class Solution
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);int ret = 1;for(int i = 1; i < n; i++){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;}
};
摆动序列
题目:摆动序列
思路
-
状态表示:以
i
位置为结尾的所有子序列中摆动序列
的最长子序列的长度
f
表示:以第i
个位置元素为结尾的所有的子序列中,第i
个位置呈现上升趋势
的最长摆动序列的长度g
表示:以第i
个位置元素为结尾的所有的子序列中,第i
个位置呈现下降趋势
的最长摆动序列的长度
-
状态转移方程:
f[i]
- 长度为
1
时,f[i] = 1
- 长度大于
1
,对于i
前面的所有元素j(0 <= j < i - 1)
,我们考虑nums[j] < nums[i]
是否成立,如果成立,则说明i
位置和j
位置构成递增子序列,则在满足这个条件下,要使j
结尾呈现下降状态
,因为不清楚是哪个j
,所以我们统计其最大值f[i] = max(g[j] + 1, f[i])
- 长度为
g[i]
- 长度为
1
时,f[i] = 1
- 长度大于
1
,对于i
前面的所有元素j(0 <= j < i - 1)
,我们考虑nums[j] > nums[i]
是否成立,如果成立,则说明i
位置和j
位置构成递减子序列,则在满足这个条件下,要使j
结尾呈现上升状态
,因为不清楚是哪个j
,所以我们统计其最大值g[i] = max(f[j] + 1, g[i])
- 长度为
-
初始化:每个位置都可以构成长度为
1
的递增子序列,因此将f、g
数组初始化为1
-
填表顺序:从左到右两个表一起填
-
返回值:
f、g
表中的最大值
C++代码
class Solution
{
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();vector<int> f(n, 1);vector<int> 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[j] > nums[i]) {g[i] = max(f[j] + 1, g[i]);}}ret = max(ret, max(f[i], g[i]));}return ret;}
};
最长递增子序列的个数
题目:最长递增子序列的个数
思路
-
状态表示:
len[i]
表示以i
位置为结尾的所有子序列中最长递增子序列的长度count[i]
表示以i
位置为结尾的所有子序列中最长递增子序列的个数
-
状态转移方程:
len[i]
- 长度为
1
,此时len[i]= 1
- 长度大于
1
,对于i
前面的所有元素j(0 <= j < i - 1)
,我们考虑nums[j] < nums[i]
是否成立,如果成立,则说明i
位置和j
位置构成递增子序列,因为不清楚是哪个j
,所以我们统计其最大值len[i] = max(len[j] + 1, len[i])
- 长度为
count[i]
,使用j
表示[0, i - 1]
区间上的下标- 当
nums[j] < nums[i]
时,如果len[j] + 1 == len[i]
,此时count[i] += count[j]
- 当
nums[j] < nums[i]
时,如果len[j] + 1 < len[i]
,此时无视
- 当
nums[j] < nums[i]
时,如果len[j] + 1 > len[i]
,此时更新len[i] = len[j] + 1, count[i] = count[j]
- 当
-
初始化:
len[i]
,每个位置都可以构成长度为1
的递增子序列,因此将len
数组初始化为1
count[i]
,初始化为1
-
填表顺序:从左到右两个表一起填
-
返回值:最长递增子序列的个数
C++代码
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[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(retlen == len[i]) retcount += count[i];else if(retlen < len[i]) retlen = len[i], retcount = count[i];}return retcount ;}
};
最长数对链
题目:最长数对链
思路
-
排序: 首先,对数对数组按照每个数对的第一个元素进行升序排序。这是为了方便后续动态规划的处理
-
状态表达:
dp[i]
表示以第i
个数对为结尾的所有数对链
,最长数对链的长度
-
状态转移方程:
- 长度为
1
,此时1
- 长度大于
1
, 对于i
前面的所有元素j(0 <= j < i - 1)
,若有p[j][1] < p[i][0]
,则说明i
位置和j
位置构成递增数对链,因为不清楚是哪个j
,所以我们取其最大值dp[i] = max(dp[j] + 1, dp[i])
,其中0 <= j < i
- 长度为
-
初始化: 全部初始化为
1
-
填表顺序: 从左往右
-
返回值: 根据状态表达,返回整个
dp
数组中的最大值
C++代码
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[i], dp[j] + 1);}ret = max(ret, dp[i]);}return ret;}
};