当前位置:网站首页>最长不下降子序列(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;
}
边栏推荐
- Why is the salary of test and development so high?
- Weebly移动端网站编辑器 手机浏览新时代
- Analysis -- MySQL statement execution process & MySQL architecture
- STM32F103实现IAP在线升级应用程序
- 【opencv】图像形态学操作-opencv标记不同连通域的位置
- 高数中值定理总结
- SQL injection HTTP header injection
- U++4 interface learning notes
- Salesforce 容器化 ISV 场景下的软件供应链安全落地实践
- Leetcode(46)——全排列
猜你喜欢
Vscode automatically adds a semicolon and jumps to the next line
使用知云阅读器翻译统计遗传学书籍
A simple and beautiful regression table is produced in one line of code~
Salesforce 容器化 ISV 场景下的软件供应链安全落地实践
offer如何选择该考虑哪些因素
Techniques d'utilisation de sublime
If you‘re running pod install manually, make sure flutter pub get is executed first.
When knative meets webassembly
Error: No named parameter with the name ‘foregroundColor‘
Read of shell internal value command
随机推荐
National meteorological data / rainfall distribution data / solar radiation data /npp net primary productivity data / vegetation coverage data
【ArcGIS教程】专题图制作-人口密度分布图——人口密度分析
01 machine learning related regulations
PLC Analog output analog output FB analog2nda (Mitsubishi FX3U)
使用Thread类和Runnable接口实现多线程的区别
ThinkPHP关联预载入with
U++ 游戏类 学习笔记
指针与数组在函数中输入实现逆序输出
基于Bevy游戏引擎和FPGA的双人游戏
Addressable 预下载
DBSync新增对MongoDB、ES的支持
U++4 接口 学习笔记
批量归一化(标准化)处理
01机器学习相关规定
为什么很多人对技术债务产生误解
Leetcode(46)——全排列
一个酷酷的“幽灵”控制台工具
How to choose an offer and what factors should be considered
LabVIEW在打开一个新的引用,提示内存已满
深入解析Kubebuilder