24年收尾之作------动态规划＜六＞ 子序列问题(含对应LeetcodeOJ题)
目录
引例
经典LeetCode OJ题
1.第一题
2.第二题
3.第三题
4.第四题
5.第五题
6.第六题
7.第七题
引例
OJ传送门 LeetCode<300>最长递增子序列
画图分析:
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的子序列中，最长递增子序列的长度
2.状态表示 对于子数组/子序列的问题都可以划分为长度为1，长度大于1两种情况
3.初始化 可以将dp表中的值初始化为最差的情况，即单个值构成子序列，初始化为1
4.填表顺序 从左往右
5.返回值 因为子序列的结束位置是任意的，所以返回值是dp表中的最大值
具体代码:
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;
}经典LeetCode OJ题
1.第一题
OJ传送门 LeetCode<376>摆动序列
画图分析:
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的所有子序列中，最长摆动子序列的长度
但在分析时，会发现结尾位置会出现两种情况
因此对于摆动的子序列或子数组，在状态表示时，是需要使用两个状态来表示的
f[i]表示以i位置元素为结尾的所有子序列中，最后一个位置呈现"上升"趋势的最长摆动序列的长度
f[i]表示以i位置元素为结尾的所有子序列中，最后一个位置呈现"下降"趋势的最长摆动序列的长度
2.状态转移方程----根据子序列构成来分析
3.初始化
可以将f,g表中的值先初始化为最差的情况，即1
4.填表顺序 从左往右两个表一起填
5.返回值 两个表中的最大值
具体代码:
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)//填f[i],g[i]
{
for(int j=0;j<i;++j)
{
if(nums[j]<nums[i]) 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;
}2.第二题
OJ传送门 LeetCode<673>最长递增子序列的个数
画图分析:
在使用动态规划解决该题之前，先介绍一个一次遍历求最大值及出现次数的小算法
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的所有子序列中，最长递增子序列的个数
但此时如果直接使用此状态表示求解状态转移方程的话，开始就会发现最长的递增子序列的长度是未知的，不能求解其次数，因此得使用两个状态表示来解决
len[i]表示以i位置元素为结尾的所有子序列中，最长递增子序列的长度
count[i]表示以i位置元素为结尾的所有子序列中，最长递增子序列的个数
2.状态转移方程
3.初始化 两个表都初始化为1
4.填表顺序 从左往右
5.返回值 使用小算法找到最长的子序列及出现次数
具体代码：
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])
{
//说明是第二次出现，统计以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(retlen==len[i]) retcount+=count[i];
else if(retlen<len[i]) retlen=len[i],retcount=count[i];
}
return retcount;
}3.第三题
OJ传送门 LeetCode<646> 最长数对链
画图分析:
使用动态规划解决
在使用动态规划解决之前，当以某个位置为结尾来研究问题时，是研究前面位置的状态，填表顺序是从左往右，但示例二在研究[7,8]进行填表时，会发现既可以跟在[1,2]后面，也可以跟在[4,5]后面，在填表时前后都会对其产生影响，因此要做预处理------排序
在做完排序后，就可以正常完成填表
1.状态表示
dp[i]表示以i位置元素为结尾的所有数对链中，最长数对链的长度
2.状态转移方程
3.初始化
一般将子序列或子数组问题dp表中的值，初始化为最差的情况，此题即1
4.填表顺序 从左往右
5.返回值 返回dp表中的最大值
具体代码:
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;
}4.第四题
OJ传送门 LeetCode<1218> 最长定差子序列
画图分析:
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的所有子序列中，最长的等差子序列的长度
2.状态转移方程
3.初始化
初始化第一个位置的值 hash[arr[0]]=1
4.填表顺序 从左往右
5.返回值 dp表中的最大值
具体代码:
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;
}5.第五题
OJ传送门 LeetCode<1218> 最长的斐波那契子序列的长度
画图分析:
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的所有子序列中，最长的斐波那契子序列的长度
如果使用此状态表示来研究状态转移方程的话，会发现i前面的j位置的dp[j]对应的arr[j]是可能跟在某个值后面的，就不能贸然使用dp[j]来更新dp[i],可以使用二维来确定
dp[i][j]表示以i位置及j位置元素为结尾的所有子序列中，最长的斐波那契额子序列的长度(i<j)
2.状态转移方程
3.初始化 表中所有值都初始化为2
此时可能会想，对于dp[0][0]初始化为2的话，根据状态表示是不正确的，但i<j,这就说明在填表时，只会用到上三角区域的值，因此这些值初始化为多少都不重要，是使用不到的
4.填表顺序 从上往下
5.返回值 dp表中的最大值 但此时得判断若数组是[1,2,4]是没有斐波那契子序列的，此时返回值ret的结果为2，根据题意是要为0的，因此需要做 ret<3? 0:ret;
具体代码:
int lenLongestFibSubseq(vector<int>& arr)
{
int n=arr.size();
//预处理使值与下标绑定
unordered_map<int,int> hash;//<value,index>
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 j=2;j<n;++j)//固定最后一个位置
{
for(int i=1;i<j;++i)//固定倒数第二个位置
{
int a=arr[j]-arr[i];
if(a<arr[i] && hash.count(a)) dp[i][j]=dp[hash[a]][i]+1;
ret=max(ret,dp[i][j]);
}
}
return ret<3? 0:ret;
}6.第六题
OJ传送门 LeetCode<1218> 最长等差数列
画图分析:
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的所有子序列中，最长的等差子序列的长度
但在研究状态转移方程时，使用i位置前面的状态(dp[j])填dp[i]时，就会发现，我们只知道dp[j]是一个长度值，并不知道其具体的子序列的情况，可能在其后面跟nums[i]的话，构不成等差子序列，因此可以使用二维的来处理
dp[i][j]表示以i位置及j位置元素为结尾的所有子序列中，最长的等差序列的长度
2.状态转移方程
3.初始化
4.填表顺序
5.返回值 整个dp表中的最大值
具体代码:
int longestArithSeqLength(vector<int>& nums)
{
//优化
unordered_map<int,int> hash;
hash[nums[0]]=0;
int n=nums.size();
vector<vector<int>> dp(n,vector<int>(n,2));//创建dp表+初始化
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) && hash[a]<i) dp[i][j]=dp[hash[a]][i]+1;
ret=max(ret,dp[i][j]);
}
hash[nums[i]]=i;
}
return ret;
}7.第七题
OJ传送门 LeetCode<1218> 等差数列划分 II - 子序列
画图分析:
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的所有子序列中，等差子序列的个数
dp[i][j]表示以i位置及j位置元素为结尾的所有子序列中，等差子序列的个数(i<j)
2.状态转移方程
3.初始化
可以先全部初始化为最差的情况，即i,j单独构成一个子序列，但这不是一个等差序列，结果为0，因此可以先全部初始化为0
4.填表顺序
先固定倒数第一个数，再枚举倒数第二个数
5.返回值 整个dp表的和
具体代码:
int numberOfArithmeticSlices(vector<int>& nums)
{
//优化
int n=nums.size();
unordered_map<long long,vector<int>> hash;
for(int i=0;i<n;++i) hash[nums[i]].push_back(i);
int sum=0;
vector<vector<int>> dp(n,vector<int>(n));
for(int j=2;j<n;++j)//固定倒数第一个数，要使其有意义的话，从2开始
{
for(int i=1;i<j;++i)//固定倒数第二个数
{
long long a=(long long)2*nums[i]-nums[j];
if(hash.count(a))
{
for(auto k:hash[a])
{
if(k<i) dp[i][j]+=dp[k][i]+1;
}
}
sum+=dp[i][j];
}
}
return sum;
}