当前位置:网站首页>最长回文子串(动态规划)
最长回文子串(动态规划)
2022-07-06 23:08:00 【疯疯癫癫才自由】
最长回文子串:
状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,是表示为1,不是表示为0;
状态转移方程:dp[i][j]=dp[i-1][j-1](str[i]==str[j])
= 0 (str[i]!=str[j]); 但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的, 而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的,(脑补一下,就能想出来这个逻了);
边界:dp[i][i]=1, dp[i][i+1]=1(str[i]==str[i+1]);
/**
最长回文子串:
状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,是表示为1,不是表示为0;
状态转移方程:dp[i][j]=dp[i-1][j-1](str[i]==str[j])
= 0 (str[i]!=str[j]);
但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的,
而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,
需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的
(脑补一下,就能想出来这个逻辑了);
边界:dp[i][i]=1, dp[i][i+1]=1(str[i]==str[i+1]);
*/
/**
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >>str;
int len=str.size();
int dp[len][len]={0},ans=1;
memset(*dp,0,sizeof dp);
for(int i=0;i<len;++i)
{
dp[i][i]=1;
if(i<len-1&&str[i]==str[i+1])
{
dp[i][i+1]=1;
ans=2;
}
}
for(int l=3;l<len;++l)
{
for(int i=0,j=0;i+l-1<len;++i)
{
j=i+l-1;
if(str[i]==str[j]&&dp[i+1][j-1]==1)
{
dp[i][j]=1;
ans=l;
}
}
}
cout << ans << endl;
return 0;
}
*/
然而,我们还可以把dp[i][j]表示的状态修改一下,以至于我们可以输出最长回文子串的内容。
状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,若是则这个值为此回文子串的长度,
不是表示为0;
状态转移方程:dp[i][j]=dp[i-1][j-1]+2 (str[i]==str[j])
= 0 (str[i]!=str[j]);
但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的,
而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,
需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的
(脑补一下,就能想出来这个逻辑了);
边界:dp[i][i]=1, dp[i][i+1]=2(str[i]==str[i+1]);
/**
然而,我们还可以把dp[i][j]表示的状态修改一下,以至于我们可以输出最长回文子串的内容。
状态设计:dp[i][j]表示str[i]到str[j]的字串是否为回文子串,若是则这个值为此回文子串的长度,
不是表示为0;
状态转移方程:dp[i][j]=dp[i-1][j-1]+2 (str[i]==str[j])
= 0 (str[i]!=str[j]);
但此处又须注意,dp的值是以字符串的子串长度(1...len)进行递增枚举的,
而不是以字符下标i为基点,j=i+k(k=1...len),因为在算后面的dp[i][j]时,
需要把dp[i-1][j-1]的值算出来,然而此时dp[i-1][j-1]时=是还没有算出来的
(脑补一下,就能想出来这个逻辑了);
边界:dp[i][i]=1, dp[i][i+1]=2(str[i]==str[i+1]);
*/
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >>str;
int len=str.size();
int dp[len][len]={0},ans=1;
memset(dp,0,sizeof(dp));
for(int i=0;i<len;++i)
{
dp[i][i]=1;
if(i<len-1&&str[i]==str[i+1])
{
dp[i][i+1]=2;
ans=2;
}
}
for(int l=3;l<=len;++l)
{
for(int i=0,j=0;i+l-1<len;++i)
{
j=i+l-1;
if(str[i]==str[j]&&dp[i+1][j-1]!=0)
{
dp[i][j]=dp[i+1][j-1]+2;
ans=l;
}
}
}
int l=0,r=0,imax=0;
for(int i=0;i<len;++i)
for(int j=0;j<len;++j)
{
if(dp[i][j]>imax)
{
imax=dp[i][j];
l=i;
r=j;
}
}
cout << ans << endl;
cout <<imax << endl;
for(;l<=r;++l)
cout << str[l];
return 0;
}
更高效的应当是二分加字符串hash的做法,这个写完,等明天有时间再温习一遍字符串hash,已是有点模糊了。
在写这个代码的时候,发现了一个跟好玩的事情:
即当数组不是全局变量时:
如果数组大小是变量,则数组初始化为0时,元素的值也许不是0;
如果数组大小是常量,则数组初始化为0时,元素的值是0;
/**
当数组不是全局变量时:
如果数组大小是变量,则数组初始化为0时,元素的值也许不是0;
如果数组大小是常量,则数组初始化为0时,元素的值是0;
*/
/**
#include <iostream>
using namespace std;
const int maxn=10;
int main()
{
cout << "数组大小是变量:\n";
cout << "输入两个值:\n";
int n, m;
cin >> n >> m;
int temp[n][m]={0};
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cout << temp[i][j] << ' ';
cout << "\n数组大小是const 类型的常量:\n";
int matr[maxn][maxn]={0};
for(int i=0;i<maxn;++i)
for(int j=0;j<maxn;++j)
cout << matr[i][j] << ' ';
cout << "\n数组大小就是 common 常量:\n";
int a[10][10]={0};
for(int i=0;i<10;++i)
for(int j=0;j<10;++j)
cout << a[i][j] << ' ';
}
*/
下面是这个程序的运行结果:
边栏推荐
- JS variable case
- A row of code r shows the table of Cox regression model
- Analysis -- MySQL statement execution process & MySQL architecture
- Understand common network i/o models
- U++ 元数据说明符 学习笔记
- How to design API interface and realize unified format return?
- HarmonyOS第四次培训
- Weebly mobile website editor mobile browsing New Era
- NiO related knowledge points (I)
- 一个酷酷的“幽灵”控制台工具
猜你喜欢
Ansible概述和模块解释(你刚走过了今天,而扑面而来的却是昨天)
Analysis -- MySQL statement execution process & MySQL architecture
offer如何选择该考虑哪些因素
U++ game learning notes
Operand of null-aware operation ‘!‘ has type ‘SchedulerBinding‘ which excludes null.
为什么很多人对技术债务产生误解
Salesforce 容器化 ISV 场景下的软件供应链安全落地实践
JDBC link Oracle reference code
ThinkPHP关联预载入with
指针与数组在函数中输入实现逆序输出
随机推荐
npm ERR! 400 Bad Request - PUT xxx - “devDependencies“ dep “xx“ is not a valid dependency name
Servicemesh mainly solves three pain points
JS variable case output user name
JS variable case
JDBC link Oracle reference code
Inventory host list in ansible (I wish you countless flowers and romance)
Basic knowledge of road loss of 3GPP channel model
高数中值定理总结
Addressable 预下载
当 Knative 遇见 WebAssembly
Why do many people misunderstand technical debt
2.证券投资基金的概述
Stm32f103ze+sht30 detection of ambient temperature and humidity (IIC simulation sequence)
Time complexity & space complexity
Salesforce 容器化 ISV 场景下的软件供应链安全落地实践
指针与数组在函数中输入实现逆序输出
Flask project uses flask socketio exception: typeerror: function() argument 1 must be code, not str
When knative meets webassembly
Weebly移动端网站编辑器 手机浏览新时代
Using thread class and runnable interface to realize the difference between multithreading