当前位置:网站首页>最长不下降子序列(LIS)(动态规划)
最长不下降子序列(LIS)(动态规划)
2022-07-06 23:08:00 【疯疯癫癫才自由】
- 状态设计:dp[i]表示以str[i]结尾的最长不下降子序列长度
- 状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i]);
- 当然,后面我们还可以输出这个最长不下降子序列的内容,只需要从后面开始枚举dp的值进行递减,只要dp的值与temp(最长子序列长度递减)相等, 就把str[i]的值加到lis中,直到temp==0为止。
- 输出第一个最长不下降子序列的内容呢:不过是从前面开始枚举罢了。
/**
2)状态设计:dp[i]表示以str[i]结尾的最长不下降子序列长度
状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i]);
当然,后面我们还可以输出这个最长不下降子序列的内容,只需要从后面
开始枚举dp的值进行递减,只要dp的值与temp(最长子序列长度递减)相等,
就把str[i]的值加到lis中,直到temp==0为止。
输出第一个最长不下降子序列的内容呢:不过是从前面开始枚举罢了。
*/
/**
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cout << "input a string:\n";
cin >> str;
int len=str.size();
int dp[len],ans=0; //dp[i]表示以str[i]结尾的最长不下降子序列长度
dp[0]=1; //状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i])
for(int i=1;i<len;++i)
{
dp[i]=1;
for(int j=0;j<i;++j)
{
if(str[j]<=str[i]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
ans=max(ans,dp[i]);
}
string lis; //lis输出最长不下降子序列
int temp=ans;
for(int i=len-1;i>=0;--i)
{
if(dp[i]==temp)
{
lis=str[i]+lis; temp从后开始往前寻找结果,当最长不下降序列
--temp; 不止一个结果时,得到的序列是最后一组
}
}
cout << ans << endl;
for(auto a:str)
cout << a << ' ';
cout << endl;
for(auto a:dp)
cout << a << ' ';
cout << endl;
cout << lis << endl;
string first;
temp=1;
for(int i=0;i<len;++i)
{
if(dp[i]==temp)
{
first+=str[i];
++temp;
}
}
cout << "first substr:\n";
cout << first << endl;
return 0;
}
*/
3)为了后续不下降子序列的内容进行输出,也可开一个result数组,result[i]
表示str[i]的前继结点,一个序列的首结点设置为-1,与其他节点进行区分,
其实和第一个程序利用dp的值进行输出内容是一样的。
/**
3)为了后续不下降子序列的内容进行输出,也可开一个result数组,result[i]
表示str[i]的前继结点,一个序列的首结点设置为-1,与其他节点进行区分,
其实和第一个程序利用dp的值进行输出内容是一样的
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cout << "input a string:\n";
cin >> str;
int len=str.size();
int dp[len]; //dp[i]表示以str[i]结尾的最长不下降子序列长度
dp[0]=1; //状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i])
int result[len]; //result[i]表示str[i]的前继结点
result[0]=-1; //一个序列的首结点设置为-1,与其他节点进行区分
for(int i=1;i<len;++i)
{
dp[i]=1;
result[i]=-1;
for(int j=0;j<i;++j)
{
if(str[j]<=str[i]&&dp[j]+1>dp[i])
{
dp[i]=dp[j]+1;
result[i]=j;
}
}
}
int p=0,imax=0;
for(int i=0;i<len;++i)
{
if(dp[i]>imax)
{
imax=dp[i];
p=i;
}
}
string lis;
for(;p!=-1;)
{
lis=str[p]+lis;
p=result[p];
}
cout << imax << endl;
cout << lis << endl;
cout << "调试:\n";
for(auto a:str)
cout << a << ' ';
cout << endl;
for(auto a:dp)
cout << a << ' ';
cout << endl;
for(auto a:result)
cout << a << ' ';
cout << endl;
return 0;
}
边栏推荐
- 全国气象数据/降雨量分布数据/太阳辐射数据/NPP净初级生产力数据/植被覆盖度数据
- Comparison between thread and runnable in creating threads
- 当 Knative 遇见 WebAssembly
- Techniques d'utilisation de sublime
- 一个酷酷的“幽灵”控制台工具
- Talk about the importance of making it clear
- A simple and beautiful regression table is produced in one line of code~
- NiO related knowledge points (I)
- A line of R code draws the population pyramid
- 最全常用高数公式
猜你喜欢
Basic knowledge of road loss of 3GPP channel model
U++ metadata specifier learning notes
装饰器基础学习02
Techniques d'utilisation de sublime
U++ 游戏类 学习笔记
Weebly mobile website editor mobile browsing New Era
《五》表格
- [email protected] Mapping relatio"/>
Why JSON is used for calls between interfaces, how fastjson is assigned, fastjson 1.2 [email protected] Mapping relatio
If you‘re running pod install manually, make sure flutter pub get is executed first.
Flask项目使用flask-socketio异常:TypeError: function() argument 1 must be code, not str
随机推荐
JS variable
CentOS 7.9安装Oracle 21c历险记
U++ 游戏类 学习笔记
[practice leads to truth] is the introduction of import and require really the same as what is said on the Internet
SQL injection HTTP header injection
Tree map: tree view - draw covid-19 array diagram
Why JSON is used for calls between interfaces, how fastjson is assigned, fastjson 1.2 [email protected] Mapping relatio
PLC模拟量输出 模拟量输出FB analog2NDA(三菱FX3U)
Analysis -- MySQL statement execution process & MySQL architecture
MySQL数据库(基础篇)
U++ metadata specifier learning notes
记录一次压测经验总结
JS also exports Excel
【QT】自定义控件-Loading
《五》表格
vector和类拷贝构造函数
AttributeError: module ‘torch._ C‘ has no attribute ‘_ cuda_ setDevice‘
高数中值定理总结
Can I specify a path in an attribute to map a property in my class to a child property in my JSON?
2. Overview of securities investment funds